54
правки
Изменения
Нет описания правки
== Идея ==
При работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить <tex>O(\log n)</tex>. В Scapegoat Tree используется следующая идея ==== Степень сбалансированности ====Будем считать, что дерево является сбалансированным, если выполняются следующее: введем Введем коэффициент <tex>\alpha</tex>, который показывает, насколько дерево может быть несбалансированным. Математически это выглядит следующим образом:
<tex> 1/2 \leqslant \alpha \leqslant 1 </tex>;
<tex> size(left[x]) \leqslant \alpha \cdot size(x) </tex>;
<tex> size(right[x]) \leqslant \alpha \cdot size(x) </tex>, где <tex>size(left[x])</tex> и <tex>size(right[x])</tex> - размер левого и правого поддерева вершины <tex>x</tex>.
=== Плюсы ===
Пока дерево остается <tex>\alpha</tex>-сбалансированным, выполняем модифицированную вставку элемента в дерево, которая аналогична обычной вставке в двоичное дерево, но операция <tex>InsertKey(k)</tex> будет возвращать глубину данной вершины. В тот момент, когда дерево стало несбалансированным, надо начать поиск вершины, которая нарушает условие сбалансированности. Для этого надо пройти по дереву вверх. Только что вставленная вершина ей быть не может. После нахождения этой вершины надо запустить операцию перебалансировки.
Нам нужна специальная функция <tex>FindScapegoat(n)</tex>, которая позволяет найти тот элемент дерева, который испортил баланс (именно из-за этой процедуры дерево так называется. Scapegoat - "козел отпущения", который испортил баланс).
