Изменения

Перейти к: навигация, поиск

Взвешенное дерево

898 байт добавлено, 16:14, 22 июня 2017
Структура вершины 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>
=== Поиск элемента ===
Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет <tex>O(\log_\frac{1}{\alpha} (N))</tex>.
Таким образом, сложность получается логарифмическая, '''НОно!''' При <tex>\alpha</tex> близком к <tex>0.5</tex> мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При <tex>\alpha</tex> близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к <tex>O(N)</tex>.
*<tex>root</tex> {{---}} корень дерева или поддерева, в котором происходит поиск.
size = 1
height = 0
'''while''' (n.parent <tex>\ne \varnothing</tex>):
height = height + 1
totalSize = 1 + size + n.sibling.size()
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).
Далее следует проверка выполнения условия:
:<tex>\mathtt {weight[T] } < \alpha \cdot \mathtt {maxweight[T]}</tex>;
Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:
:<tex>\mathtt {maxweight[T]} = \mathtt {weight[T]}</tex>;
====Псевдокод====
Анонимный участник

Навигация