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

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

Операции

Операции	Insert		Delete		Search		Память
	Среднее	Худшее	Среднее	Худшее	Среднее	Худшее	Среднее	Худшее
Scapegoat-tree	[math]O(log\ n)[/math]	Амортизировано [math]O(log\ n)[/math]	[math]O(log n)[/math]	Амортизировано [math]O(log\ n)[/math]	[math]O(log\ n)[/math]		[math]O(n)[/math]

Обозначения и Определения

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

[math]\mathtt{T}[/math] — обозначение дерева,

[math]\mathtt{root[T]}[/math] — корень дерева [math]T[/math],

[math]\mathtt{left[x]}[/math] — левый сын вершины [math]x[/math],

[math]\mathtt{right[x]}[/math] — правый сын вершины [math]x[/math],

[math]\mathtt{brother(x)}[/math] — брат вершины [math]x[/math] (вершина, которая имеет с [math]x[/math] общего родителя),

[math]\mathtt{depth(x)}[/math] — глубина вершины [math]x[/math] (количество рёбер от нее до корня),

[math]\mathtt{height(T)}[/math] — глубина дерева [math]T[/math] (глубина самой глубокой вершины дерева [math]T[/math]),

[math]\mathtt{weight(x)}[/math] — вес вершины [math]x[/math] (количество всех её дочерних вершин плюс [math]1[/math] — она сама),

[math]\mathtt{weight[T]}[/math] — размер дерева [math]T[/math] (количество вершин в нём),

[math]\mathtt{maxweight[T]}[/math] — максимальный размер дерева (максимальное значение, которое параметр [math]\mathtt{weight[T]}[/math] принимал с момента последней перебалансировки, то есть если перебалансировка произошла только что, то [math]\mathtt{maxweight[T]} = \mathtt{weight[T]}[/math]

Синим цветом обозначены глубины вершин, а красным — их веса. Считается вес вершины следующим образом: для новой вершины вес равен [math]1[/math]. Для её родителя [math]\mathtt{weight} = 1[/math] (вес новой вершины) [math]+ 1[/math] (вес самого родителя) [math]+ \mathtt{weight(brother(x))}[/math]. Возникает вопрос — как посчитать [math]\mathtt{weight(brother(x))}[/math]? Делается это рекурсивно. Это займёт время [math]O\mathtt{(weight(brother(x)))}[/math]. Понимая, что в худшем случае придётся посчитать вес половины дерева — здесь появляется та самая сложность [math]O(N)[/math] в худшем случае, о которой говорилось в начале. Но поскольку совершается обход поддерева [math]\alpha[/math]-сбалансированного по весу дерева можно показать, что амортизированная сложность операции не превысит [math]O(\log N)[/math]. В данном Scapegoat-дереве [math]weight[T] = 4[/math], [math]\mathtt{maxweight[T]} \geqslant 4[/math]

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

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

Некоторая вершина [math]x[/math] называется [math]\alpha[/math]-сбалансированной по весу, если [math]\mathtt{weight(left[x])} \leqslant \alpha \cdot \mathtt{weight(x)}[/math] и [math]\mathtt{weight(right[x])} \leqslant \alpha \cdot \mathtt{weight(x)}[/math].

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

Структура вершины n

n.key                      //значение в вершине 
n.left                     //левый ребенок вершины 
n.right                    //правый ребенок вершины 
n.height                   //высота поддерева данной вершины 
n.depth                    //глубина вершины 
n.parent                   //ссылка на родителя 
n.sibling                  //ссылки на "братьев" данной вершины 

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

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

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

• [math]root[/math] — корень дерева или поддерева, в котором происходит поиск.
• [math]k[/math] — искомый ключ в дереве.

Search(root, k):
  if  root = [math]\varnothing[/math] or root.key = k:
     return  root
  else if  k [math]\leqslant[/math] root.left.key:
     return  Search(root.left, k)
  else:
     return  Search(root.right, k)

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

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

Тривиальный способ перебалансировки

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

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

Получение списка

• [math]root[/math] — корень дерева, которое будет преобразовано в список.

FlattenTree(root, head):
  if root = [math]\varnothing[/math]:
     return head
  root.right = FlattenTree(root.right, head)
  return FlattenTree(root.left, root)

Построение дерева

• [math]size[/math] — число вершин в списке.
• [math]head[/math] — первая вершина в списке.

BuildHeightBalancedTree(size, head):
  if size = 1 then:
     return head
  else if size = 2 then:
     (head.right).left = head
     return head.right
  root = (BuildHeightBalancedTree(⌊(size − 1)/2⌋, head)).right
  last = BuildHeightBalancedTree(⌊(size − 1)/2⌋, root.right)
  root.left = head
  return last

Перестроение дерева

• [math]size[/math] — число вершин в поддереве.
• [math]scapegoat[/math] — вершина, которая испортила баланс.

RebuildTree(size, scapegoat):
  head = FlattenTree(scapegoat, [math]\varnothing[/math])
  BuildHeightBalancedTree(size, head)
  while head.parent [math]\ne \varnothing [/math]
     head = head.parent
  return head

Более сложный способ перебалансировки

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

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

Вставка без нарушения баланса 1

Вставка без нарушения баланса 2

Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка

Псевдокод

• [math]n[/math] — узел дерева. Обычно, процедура вызывается от только что добавленной вершины.

FindScapegoat(n):
  size = 1
  height = 0
  while n.parent [math]\ne \varnothing[/math]:
     height = height + 1
     totalSize = 1 + size + n.sibling.size()
     if height [math] \gt  \lfloor \log_\frac{1}{\alpha} (totalSize) \rfloor[/math]:
        return n.parent
     n = n.parent
     size = totalSize

Сама вставка элемента:

• [math]k[/math] — ключ, который будет добавлен в дерево.

Insert(k):
  height = InsertKey(k)
  if height = −1:
     return false;
  else if height > T.hα:
     scapegoat = FindScapegoat(Search(T.root, k))
     RebuildTree(n.size(), scapegoat)
  return true

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

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

[math]\mathtt {weight[T]} \lt \alpha \cdot \mathtt {maxweight[T]}[/math];

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

[math]\mathtt {maxweight[T]} = \mathtt {weight[T]}[/math];

Псевдокод

Функция [math]Delete(k)[/math] удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.

• [math]k[/math] — ключ, который будет удален.

Delete(k): 
  deleted = DeleteKey(k)
  if deleted:
     if T.size < (T.α · T.maxSize):
        RebuildTree(T.size, T.root)

Сравнение с другими деревьями

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

• По сравнению с такими структурами, как Красно-черное дерево, АВЛ-дерево и Декартово дерево, нет необходимости хранить какие-либо дополнительные данные в вершинах (а значит появляется выигрыш по памяти).
• Отсутствие необходимости перебалансировать дерево при операции поиска (а значит гарантируется максимальное время поиска [math]O(\log N)[/math], в отличии от структуры данных Splay-дерево, где гарантируется только амортизированное [math]O(\log N)[/math])
• При построении дерева выбирается некоторый коэффициент [math]\alpha[/math], который позволяет улучшать дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.

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

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

См. также

• Поисковые структуры данных
• АВЛ-дерево
• Декартово дерево
• Splay-дерево
• Красно-черное дерево

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

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