Scapegoat Tree

Пример дерева с [math]\alpha[/math] = 0.6

Scapegoat Tree — структура данных, представляющая собой частично сбалансированное дерево поиска (степень сбалансированности может быть настроена), такое что операции поиска, вставки и удаления работают за O(log n), при этом скорость одной операции может быть улучшена в ущерб другой.

Идея

При работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить [math]O(\log n)[/math].

Степень сбалансированности

Будем считать, что дерево является сбалансированным, если выполняются следующее: Введем коэффициент [math]\alpha[/math], который показывает, насколько дерево может быть несбалансированным. Математически это выглядит следующим образом: [math] 1/2 \leqslant \alpha \leqslant 1 [/math]; [math] size(left[x]) \leqslant \alpha \cdot size(x) [/math]; [math] size(right[x]) \leqslant \alpha \cdot size(x) [/math], где [math]size(left[x])[/math] и [math]size(right[x])[/math] — размер левого и правого поддерева вершины [math]x[/math].

Плюсы

• Данное дерево позволяет ускорить одни операции взамен на ускорение других, что отличает его от других (простое бинарное дерево, красно-черное дерево, splay-дерево). Результаты исследований показывают, что Scapegoat tree работает на случайных данных быстрее, чем красно-черное.
• Требует меньше памяти, так как не надо хранить дополнительную информацию в вершине для балансировки.
• Настройки скорости можно менять в процессе выполнения программы.

Минусы

• Данное дерево сложно для написания.
• В случае неправильной настройки скорости работы дерево будет проигрывать по скорости работы другим.

Если условие нарушается, запускается операция перебалансировки дерева. Заметим, что при [math]\alpha = 1[/math] деревом будет считаться даже линейная структура.

Примечание: Существует два подхода к балансу дерева, которые дают похожий результат. Первый — задавать [math]\alpha[/math]. Второй — задать ограничение [math]q[/math], большее чем число элементов в дереве (чем больше ограничение, тем более несбалансированным может быть дерево), и следить, чтобы [math]\log_{3/2}(q)[/math] был больше максимальной глубины дерева. В противном случае, необходимо произвести перебалансировку дерева.

Свойства

Данная структура обладает следующими свойствами:

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

Структура

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

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

Структура дерева T

T.root — ссылка на корень дерева
T.size — число вершин в дереве
T.maxSize — максимальное число вершин в дереве после последней перебалансировки
T.hα — вспомогательное значение, вычисляется как: [math]T.hα = ⌊log1/α (T.size)⌋[/math]
T.height — высота дерева 

Операции

Поиск

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

Search(root, k):
  if  root = null or root.key = k:
     return  root
  else if  k ≤ root.left.key:
     return  Search(root.left, k)
  else:
     return  Search(root.right, k)

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

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

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

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

Пока дерево остается [math]\alpha[/math]-сбалансированным, выполняем модифицированную вставку элемента в дерево, которая аналогична обычной вставке в двоичное дерево, но операция [math]InsertKey(k)[/math] будет возвращать глубину данной вершины. В тот момент, когда дерево стало несбалансированным, надо начать поиск вершины, которая нарушает условие сбалансированности. Для этого надо пройти по дереву вверх. Только что вставленная вершина ей быть не может. После нахождения этой вершины надо запустить операцию перебалансировки.

Нам нужна специальная функция [math]FindScapegoat(n)[/math], которая позволяет найти тот элемент дерева, который испортил баланс (именно из-за этой процедуры дерево так называется. Scapegoat - "козел отпущения", который испортил баланс).

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

FindScapegoat(n):
  size = 1
  height = 0
  while (n.parent <> null):
     height = height + 1
     totalSize = 1 + size + n.sibling.size()
     if height > ⌊log1/α(totalSize)⌋:
        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

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

Сначала надо удалить вершину, как в обычном двоичном дереве. Потом надо проверить дерево на сбалансированность. Если дерево осталось сбалансированным, ничего делать не надо. В противном случае надо начать перебалансировку дерева.

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

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

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

Перебалансировка дерева

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

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

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

FlattenTree(root, head):
  if root = null:
     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, null)
  BuildHeightBalancedTree(size, head)
  while head.parent!=null do
     head = head.parent
  return head