Взвешенное дерево

Определение

Scapegoat-дерево (англ. Scapegoat-Tree) — сбалансированное бинарное дерево поиска, обеспечивающее наихудшее [math]O(log N)[/math] время поиска, и [math]O(log N)[/math] - амортизирующее время вставки и удаления элемента. В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае [math]O(log N)[/math] время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска : узел хранит только ключ и два указателя на своих потомков.

Достоинства Scapegoat дерева

1. Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у таких структур, как Красно-черное дерево, АВЛ-дерево и Декартово дерево)
   
   
2. Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска [math]O(log N)[/math], в отличии от структуры данных Splay-дерево, где гарантируется только амортизированное [math]O(log N)[/math])
   
   
3. Амортизированная сложность операций вставки и удаления [math]O(log N)[/math] — это в общем-то аналогично остальным типам деревьев
   
   
4. При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.
   
   

Недостатки Scapegoat дерева

1. В худшем случае операции модификации дерева могут занять [math]O(N)[/math] времени (амортизированная сложность у них по-прежнему [math]O(log N)[/math], но защиты от плохих случаев нет).
   
   
2. Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что не очень хорошо.
   
   

Операции

Определение:

Бинарное дерево поиска называется сбалансированным по весу, если половина вершин расположены слева от корня, а другая половина справа.

Введем обозначения:

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

• [math]T[/math] — обозначение дерева
  
  
• [math]root[T][/math] — корень дерева [math]T[/math]
  
  
• [math]left[x][/math] — левый сын вершины x
  
  
• [math]right[x][/math] — правый сын вершины x
  
  
• [math]brother(x)[/math] — брат вершины х (вершина, которая имеет с х общего родителя)
  
  
• [math]depth(x)[/math] — глубина вершины х. Это расстояние от неё до корня (количество ребер)
  
  
• [math]height(T)[/math] — глубина дерева T. Это глубина самой глубокой вершины дерева T
  
  
• [math]size(x)[/math] — вес вершины х. Это количество всех её дочерних вершин + 1 (она сама)
  
  
• [math]size[T][/math] — размер дерева T. Это количество вершин в нём (вес корня)
  
  
• [math]maxsize[T][/math] — максимальный размер дерева. Это максимальное значение, которое параметр [math]size[T][/math] принимал с момента последней перебалансировки.
  
  Если перебалансировка произошла только что, то [math]maxsize[T] = size[T][/math]
  
  

Синим цветом обозначены глубины вершин, а красным - их веса.
В данном Scapegoat-дереве [math]size[T] = 4[/math], [math]maxsize[T] \geqslant 4[/math]

• Коэффициeнт α — это число в диапазоне от [math][0.5; 1)[/math], определяющее требуемую степень качества балансировки дерева.

Определение:

Некоторая вершина x называется "α-сбалансированной по весу", если вес её левого сына меньше либо равен [math]\alpha \cdot size(x)[/math] и вес ей правого сына меньше либо равен [math]\alpha \cdot size(x)[/math].

[math]size(left[x]) \leqslant \alpha \cdot size(x)[/math];

[math]size(right[x]) \leqslant \alpha \cdot size(x)[/math];

Перед тем как приступить к работе с деревом, мы выбираем параметр α в диапазоне [math][0.5; 1)[/math]. Также заводим две переменные для хранения текущих значений [math]size[T][/math] и [math]maxsize[T][/math] и обнуляем их.

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

Пусть мы хотим найти в данном Scapegoat дереве какой-то элемент. Применим стандартный алгоритм для двоичного дерева поиска - идем от корня, если значение в вершине равно значению искомого элемента, возвращаем, если значение в вершине меньше, то рекурсивно запускаемся от левого поддерева, если больше, то, соответственно, от левого.

Замечание: Дерево по ходу поиска искомой вершины не изменяется.
Сложность операции поиска зависит от коэффициента [math]\alpha[/math] и выражается формулой — [math]log[/math]_1/α[math](N)[/math]

Таким образом, сложность получается логарифмическая, НО! При [math]\alpha[/math] близком к 0.5 мы получаем двоичный (или почти двоичный) логарифм, что означает практически идеальную скорость поиска. При [math]\alpha[/math] близком к единице основание логарифма стремится к единице, а значит общая сложность стремится к [math]O(N)[/math].

Вставка элемента

Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить [math]\alpha[/math]-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: мы ищем Scapegoat-вершину — вершину, для которой потерян [math]\alpha[/math]-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Если на этом пути встретится вершина, для которой критерий [math]\alpha[/math]-сбалансированности по весу нарушился — мы полностью перестраиваем соответствующее ей поддерево так, чтобы восстановить [math]\alpha[/math]-сбалансированность по весу.

Сразу возникает вопрос — Как делать перебалансировку найденной Scapegoat-вершины?

Есть 2 способа перебалансировки, — ниже подробнее рассказывается о каждом из них.

1 способ перебалансировки

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

Данный способ требует [math]O(size(Scapegoat-root))[/math] времени и столько же памяти.

2 способ перебалансировки

Мы вряд ли улучшим время работы перебалансировки — всё-таки каждую вершину нужно «подвесить» в новое место. Но мы можем попробовать сэкономить память. Давайте посмотрим на 1 способ алгоритма внимательнее. Вот мы выбираем медиану, подвешиваем в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует нас и на каждом из следующих шагов. Т.е. для некоторого списка вершин, отсортированных в возрастающем порядке, у нас будет ровно одно порождённое данным алгоритмом дерево. А откуда же мы взяли отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И мы можем эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — мы ведь этим затираем какую-то (возможно ещё не просмотренную) вершину — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не [math]O(size(N))[/math], а всего лишь [math]O(log N)[/math].

Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. Т.е. расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — [math]log(3)[/math].

Удаление элемента

Удаляем элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей). Далее проверяем выполнение условия:

[math]size[T] \lt \alpha \cdot maxsize[T][/math];

Если оно выполняется — дерево могло потерять α-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить:

[math]maxsize[T] = size[T][/math];

Вопросы

• Как пройти от вершины вверх к корню? Нам нужно хранить ссылки на родителей?

Поскольку мы пришли к месту вставки новой вершины из корня дерева — у нас есть стек, в котором находится весь путь от корня к новой вершине. Берём родителей из него.;

• Как посчитать вес вершины — ведь он не хранится в самой вершине?

Для новой вершины вес = 1. Для её родителя вес = 1 (вес новой вершины) + 1 (вес самого родителя) + [math]size(brother(x))[/math].;

• Как посчитать [math]size(brother(x))[/math]?

Рекурсивно. Это займёт время [math]O(size(brother(x)))[/math]. Понимая, что в худшем случае придётся посчитать вес половины дерева — здесь появляется та самая сложность [math]O(N)[/math] в худшем случае, о которой говорилось в начале. Но поскольку мы обходим поддерево α-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит [math]O(log N)[/math].;

• Что делать, если возникло несколько вершин, для которых нарушился α-балан?

Ответ прост: выбрать можно любую.;

Внешние ссылки

• In-order обход дерева

Источники информации

• Википедия - Scapegoat tree
  
• Хабрахабр - Scapegoat деревья
  
• Scapegoat Tree Applet by Kubo Kovac