Изменения
→Структура вершины n
Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <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> общего родителя),
Коэффициeнт <tex>\alpha</tex> — это число в диапазоне от <tex>[0.5; 1)</tex>, определяющее требуемую степень качества балансировки дерева.
{{Определение
|definition=Некоторая вершина <tex>x</tex> называется '''<tex>\alpha</tex>-сбалансированной по весу''', если <tex>\mathtt{weight(left[x]) } \leqslant \alpha \cdot \mathtt{weight(x)}</tex> и <tex>\mathtt{weight(right[x]) } \leqslant \alpha \cdot \mathtt{weight(x)}</tex>.}}
Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>\mathtt {weight[T]}</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их. === Структура вершины === '''struct''' Node: '''T''' key <font color=green> //значение в вершине </font> '''Node''' left <font color=green> //левый ребенок вершины </font> '''Node''' right <font color=green> //правый ребенок вершины </font> '''Node''' height <font color=green> //высота поддерева данной вершины </font> '''Node''' depth <font color=green> //глубина вершины </font> '''Node''' parent <font color=green> //ссылка на родителя </font> '''Node''' sibling <font color=green> //ссылки на "братьев" данной вершины </font>
=== Поиск элемента ===
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).
Далее следует проверка выполнения условия:
:<tex>\mathtt {weight[T] } < \alpha \cdot \mathtt {maxweight[T]}</tex>;
Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
:<tex>\mathtt {maxweight[T]} = \mathtt {weight[T]}</tex>;
====Псевдокод====
