Изменения
→Структура вершины 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> общего родителя),
<tex>\mathtt{depth(x)}</tex> — глубина вершины <tex>x</tex>(количество рёбер от нее до корня),
<tex>\mathtt{height(T)}</tex> — глубина дерева <tex>T</tex>(глубина самой глубокой вершины дерева <tex>T</tex>),
<tex>\mathtt{weight(x)}</tex> — вес вершины <tex>x</tex>(количество всех её дочерних вершин плюс <tex>1</tex> {{---}} она сама),
<tex>\mathtt{weight[T]}</tex> — размер дерева <tex>T</tex>(количество вершин в нём),
<tex>\mathtt{maxweight[T]}</tex> — максимальный размер дерева(максимальное значение, которое параметр <tex>\mathtt{weight[T]}</tex> принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = \mathtt{weight[T]}</tex>
[[Файл:0ce162a62b624da8ba02233b4b254f23.png|380px|right]]
Коэффици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 size\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> {{---}} корень дерева или поддерева, в котором происходит поиск.
'''Search'''(root, k):
'''if ''' root = null <tex>\varnothing</tex> or root.key = k:
'''return ''' root
'''else if ''' k <tex>\leqslant</tex> root.left.key:
=== Вставка элемента ===
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос {{- --}} нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева — есть стек, в котором находится весь путь от корня к новой вершине. Берутся родители из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу.
Сразу появляется вопрос {{---}} как делать перебалансировку найденной Scapegoat-вершины?
Есть <tex>2</tex> способа перебалансировки, {{---}} тривиальный и чуть более сложный.
'''FlattenTree'''(root, head):
'''if''' root = null<tex>\varnothing</tex>:
'''return''' head
root.right = FlattenTree(root.right, head)
*<tex>scapegoat</tex> {{---}} вершина, которая испортила баланс.
'''RebuildTree'''(size, scapegoat):
head = '''FlattenTree'''(scapegoat, null<tex>\varnothing</tex>)
'''BuildHeightBalancedTree'''(size, head)
'''while''' head.parent <tex>\ne null\varnothing </tex> do
head = head.parent
'''return''' head
Таким образом, если нужно сэкономить память, то <tex>2</tex> способ перебалансировки дерева {{---}} лучший вариант.
<gallery align="center" heights>{| cellpadding="260px0">| [[Файл:Good_insert_1.png|400px|thumb|Вставка без нарушения баланса 1]] || [[Файл:Good_insert_2.png|400px|thumb|Вставка без нарушения баланса 2]]|}{| cellpadding="0"|align="center"|[[Файл:Bad_insert.png|595px|thumb|Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка]]|}</gallerycenter>
====Псевдокод====
size = 1
height = 0
'''while''' (n.parent <tex>\ne\varnothing</tex> null):
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>;
====Псевдокод====
