Scapegoat Tree

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].

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

Свойства

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

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

Операции

Поиск

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

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

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

Пока дерево остается [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