Дерево со штрафами (scapegoat tree)

Бинарное дерево поиска называется сбалансированным по весу, если половина узлов находится слева от корня, а вторая - справа. Деревья называются α-weight-сбалансированными, если они отвечают следующим условиям:

Где функция size может быть определена рекурсивно:

function size(node)begin if node = nilreturn 0; else return size(node->left) + size(node->right) + 1;end;

Бинарное дерево поиска, которое является α-weight-сбалансированный также должны быть α-height-сбалансированный, то есть

Деревом со штрафами называют самобалансирующееся бинарное дерево поиска, изобретенное Игалем Гальперини (Igal Galperin), Яковом Tepecом (Jacob Teres) и Рональдом Ривестом (Ronald L. Rivest). Оно обеспечивает в худшем случае время поиска O(log n), и амартизированное время вставки и удаления O(log n).

В отличие от большинства других самобалансирующихся двоичных деревьев поиска, которые обеспечивают наихудшее время поиска O (log n), деревья со штрафами не имеют дополнительных расходов памяти (как, например, цвет или вес) по сравнению с обычными бинарными деревьями поиска: узел хранит только ключ и два указателя на дочерние узлы. Корень дерева имеет только 2 дополнительных значения – число узлов всего дерева и максимальное число узлов в дереве с момента последней перестройки. Это делает деревья со штрафами проще в реализации и может уменьшить накладные расходы узла до одной трети.

Коэффициент 0 < α < 0.5 «жесткости» дерева можно задавать произвольно и высота дерева будет ограничена сверху значением k*log(n)+1, где k=log2(1/α)

Коэффициент жесткости сильно влияет на баланс производительности: чем «жестче» дерево, тем меньше у него будет высота и тем быстрее будет работать поиск, но тем сложнее будет поддерживать порядок в операциях модификации. Например, так как АВЛ-дерево «жестче» красно-черного, поиск в нем работает быстрее, а модификация медленней. Если же пользоваться scapegoat-деревом, баланс между этими операциями можно выбирать в зависимости от специфики применения дерева.

В дереве со штрафами операция балансировки начинают с листа и последовательно рассматривают вверх всех предков до узла (называемого "козлом отпущения" - scapegoat), которое настолько несбалансированное, что все поддерево с корнем в этом узле может быть перестроено по нулевой стоимости, в амортизированной смысле. Отсюда и название.

Деревья со штрафами не гарантирует сохранение α-weight-баланса в любое время, но всегда α-height-баланс, так как

Дерево со штрафами состоит из обычных бинарных деревьев поиска, с двумя дополнительными значениями, хранящимися в корне.

Каждый узел x из дерева «козла отпущения» содержит следующие атрибуты:

key [x] – ключ, хранящийся в узле x.

left [x] – левый потомок x.

right [x] – правый потомок x.

Мы будем также использовать обозначения:

size (x) - размер поддерева с корнем в x (т. е. число ключей, хранящихся в этом поддереве, в том числе ключ, хранящийся в x).

brother (x) - брат узла x (другой потомок предка x или NIL)

h(x) и h(T) - высота узла и дерева соответственно. Высота узла это длина самого длинного пути от этого узла до листьев. Высота дерева это высота его корня.

d(x) - глубина узла x. Глубина узла это длина (число ребер) пути от корня до этого узла (Корневой узел имеет глубину 0).

Обратите внимание, что на самом деле в узлах хранятся первые три параметра: : key, left и right, а остальные данные вычисляются как функции.

Вычисление brother(x) требует знание предков x. Самое главное, size(x) не хранится в x, но может быть вычислено за время O(log n) при необходимости.

Дерево T в целом имеет следующие атрибуты:

root [T] - указатель на корневой узел дерева.

size[T] - количество узлов в дереве. Это тоже самое, что size(root[T]). В нашем анализе мы также будем обозначать size[T] как n.

max_size[T] - максимальное значение size[T] с момента последней перестройки дерева. Если операция удаления не поддерживается, то в атрибуте max_size нет необходимости

Операция поиска в scapegoat-деревьях осуществляется как в обычных деревьях двоичного поиска. Перестройка дерева не выполняется.

Вставляя узел в дерево со штрафами, мы вставляем его как в обычное бинарное дерево, увеличиваем size[T] и устанавливаем max_size[T] как максимум между size[T] и max_size[T]. Далее если нововставленный узел глубокий – мы балансируем дерево следующим образом. Пусть x0 – нововсталенный глубокий узел и обозначим xi+1 как предка xi. Мы поднимаемся по дереву, рассматривая x0, x1, x2, и так далее, пока не найдем узел xi, который не α-weight-сбалансированным. Поскольку x0 является листом, то size(xi)=0. Мы вычисляем size(xj+1), используя формулу

Мы называем xi предком x0, которое было найдено как не α -weight-сбалансированно, узел scapegoat (козел отпущения). Этот узел должен существовать по лемме (*), приведенной ниже.

Когда scapegoat узел xi найден, мы перестраиваем поддерево с корнем в xi. Перестройка поддерева это перемещение его ½-weight-сбалансированным поддеревом, содержащим те же узлы. Это легко осуществляется за время O(size(xi)). Вообще говоря, эта операция может быть осуществлена за время O(log n).

Деревья со штрафами необычны тем, что удаление легче, чем вставка. Удаление осуществляется также как удаление в простых бинарных деревьях поиска - узел просто помечается как удаленный и по нему не происходит поиск, но вместе с этим мы уменьшаем size[T]. Когда size[T] < α * max_size[T] мы перестраиваем все дерево и сбрасываем max_size[T] в size[T]. Удаление происходит в худшем случае за время О(n), однако это амортизируются как O (log n). Фактически удаленные узлы изымаются из дерева со штрафами в момент перестройки дерева.

В большинстве случаев могут быть выполнено n/2 - 1 операций удаления, прежде чем дерево должно быть перестроено. Стоимость каждого из этих удалений равна O(log n) (количество времени для поиска элемента и пометка, что он удален). При количестве операции удаления n/2 следует перестроить дерево. Это занимает О(log n) + O (n) (или просто O (n)) времени. Использование совокупного анализа становится ясно, что амортизированная стоимость удаления равна O (log n).

• Каждый раз, когда происходит полная перестройка дерева max_size[T] устанавливается равным size[T].

• Заметим, что ha(T) легко вычисляется по информации, хранящейся в корне дерева.

• Нам не нужны явные поля предков в узлах дерева со штрафами, так как мы поднимаемся обратно вверх по тропинке, по которой спустились, чтобы вставить новый узел; узлы xi в этом пути можно запомнить в стек.

Если x это узел на глубине, большей чем hα (T), то это α -weight-несбалансированный предок x