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].
• За счет отсутствия необходимости хранить дополнительные данные в вершинах данное дерево оптимальнее остальных по памяти.