Scapegoat Tree

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

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

Идея

При работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить [math]O(\log n)[/math]. В Scapegoat Tree используется следующая идея: введем коэффициент [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 — ссылки на "братьев" данной вершины

Операции

Поиск

• [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