96
правок
Изменения
м
→Обозначения и Определения
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.
<tex>\mathtt{T}</tex> — обозначение дерева,
<tex>\mathtt{root[T]}</tex> — корень дерева <tex>T</tex>,
<tex>\mathtt{left[x]}</tex> — левый сын вершины <tex>x</tex>,
<tex>\mathtt{right[x]}</tex> — правый сын вершины <tex>x</tex>,
<tex>\mathtt{brother(x)}</tex> — брат вершины <tex>x</tex> (вершина, которая имеет с <tex>x</tex> общего родителя),
Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>\mathtt {weight[T]}</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их.
=== Поиск элемента ===
