Изменения

Квадратные скобки в обозначениях означают, что хранится это значение явно, а значит можно взять за время <tex>O(1)</tex>. Круглые скобки означают, что значение будет вычисляться по ходу дела то есть память не расходуется, но зато нужно время на вычисление.

<tex>T</tex> — обозначение дерева,

<tex>root[T]</tex> — корень дерева <tex>T</tex>,

<tex>left[x]</tex> — левый сын вершины <tex>x</tex>,

<tex>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>weight[T]</tex> принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то <tex>\mathtt{maxweight[T]} = \mathtt{weight[T]}</tex>

Синим цветом обозначены '''глубины''' вершин, а красным {{---}} их '''веса'''.

Перед тем как приступить к работе с деревом, выбирается параметр <tex>\alpha</tex> в диапазоне <tex>[0.5; 1)</tex>. Также нужно завести две переменные для хранения текущих значений <tex>weight[T]</tex> и <tex>\mathtt{maxweight[T]}</tex> и обнулить их.

=== Поиск элемента ===

Пусть требуется найти в данном Scapegoat дереве какой-то элемент. Поиск происходит так же, как и в обычном дереве поиска, поскольку не меняет дерево, но его время работы составляет <tex>O(\log_\frac{1}{\alpha} (N))</tex>.