Структура данных Scapegoat Tree

Разработана Arne Andersson, Igal Galperin, Ronald L. Rivest в 1962г.
Ronald L. Rivest
Arne Andersson

Определение

Понятия, необходимые для работы с данным деревом:
?−дерево
????[?]−корень дерева ?
????[?],???ℎ?[?]−левые и правый "сын" вершины
????ℎ??(?)− брат вершины (имеет общего родителя)
????ℎ(?)−глубина вершины (расстояние от вершины до корня)
ℎ???ℎ?(?)−глубина дерева ?
????(?)−вес вершины ? (кол−во всех ее дочерних вершины+1)
????[?]−размер дерева ? (вес корня)
???_size[T] – максимальный размер дерева T.

Примеры

Плюсы и минусы Scapegoat дерева
Плюсы
Скорость одних операций возможно улучшить за счет других операций.
Scapegoat tree работает быстрее, чем красно-черное дерево и декартово.
Требуется меньше памяти (не надо хранить информацию для балансировки).
Настройки скорости меняются в процессе выполнения.
Не требуется перебалансировать дерево при поиске.

Минусы
В худшем случае операции модификации дерева могут занять ?(?) времени.
В случае неправильного выбора парметра ???ℎ? часто используемые операции будут работать долго, а редко используемые – быстро. При этом дерево будет уступать остальным по скорости

Поиск

Вставка
Начинается вставка нового элемента в Scapegoat-дерево классически: поиском ищем место, куда бы подвесить новую вершину и подвешиваем.
Легко понять, что это действие могло нарушить α-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название структуре данных: мы ищем «козла отпущения» (Scapegoat-вершину) — вершину, для которой потерян α-баланс и её поддерево должно быть перестроено.
Сама только что вставленная вершина, хотя и виновата в потере баланса, «козлом отпущения» стать не может — у неё ещё нет «детей», а значит её баланс идеален.
Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Если на этом пути встретится вершина, для которой критерий α-сбалансированности по весу нарушился — мы полностью перестраиваем соответствующее ей поддерево так, чтобы восстановить α-сбалансированность по весу.

Перебалансировка
Обходим всё поддерево Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получаем отсортированный список (свойство In-order обхода бинарного дерева поиска).
Находим медиану на этом отрезке, подвешиваем её в качестве корня поддерева.
Для «левого» и «правого» поддерева рекурсивно повторяем ту же операцию.

if start > ends then
begin
result := Nil;
exit;
end;
mid := ceil((start + ends) / 2.0);
d := nodesList[mid];
p := Node.Create(d.key);
leftNode := self.buildTreeFromSortedList(nodesList, start, mid-1);
p.left := leftNode;
rightNode := self.buildTreeFromSortedList(nodesList, mid+1, ends);
p.right := rightNode;
result := p;

7
3
8
1
10
2
9
1
3
5
Пример:
α = 0.5
Верхний индекс – вес вершины
(количество всех ее потомков + 1)

8
1
Вычислив медиану (2) (start = 0, ends = 4), подвешиваем 8 в качестве корня поддерева (в данном случае корень самого дерева)
Пример:
α = 0.5
Верхний индекс – вес вершины
(количество всех ее потомков + 1)

8
7
1
2
Далее, рекурсивно проходим влево, выполняем туже функцию, уменьшая параметр ends.
В левое поддерево подвешиваем 7
Пример:
α = 0.5
Верхний индекс – вес вершины
(количество всех ее потомков + 1)

8
7
2
3
Далее, рекурсивно проходим влево, выполняем туже функцию, уменьшая параметр ends.
В левое поддерево подвешиваем 3
Пример:
α = 0.5
Верхний индекс – вес вершины
(количество всех ее потомков + 1)
3
1

8
7
2
4
Далее, рекурсивно проходим вправо, выполняем туже функцию, увеличивая параметр ends.
В правое поддерево подвешиваем 10
Пример:
α = 0.5
Верхний индекс – вес вершины
(количество всех ее потомков + 1)
3
1
10
2

8
7
2
5
Далее, рекурсивно проходим вправо, выполняем туже функцию, увеличивая параметр ends.
В левое поддерево вершины 10 подвешиваем 9
Выходим из рекурсии
Дерево имеет α-балансировку
Пример:
α = 0.5
Верхний индекс – вес вершины
(количество всех ее потомков + 1)
3
1
10
2
9
1