1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Идея ==
При работе необходимо поддерживать состояние сбалансированного дерева, иначе время работы операции поиска может превысить <tex>O(\log n)</tex>. В Scapegoat Tree используется следующая идея ==== Степень сбалансированности ====Будем считать, что дерево является сбалансированным, если выполняются следующее: введем Введем коэффициент <tex>\alpha</tex>, который показывает, насколько дерево может быть несбалансированным. Математически это выглядит следующим образом:
<tex> 1/2 \leqslant \alpha \leqslant 1 </tex>;
<tex> size(left[x]) \leqslant \alpha \cdot size(x) </tex>;
<tex> size(right[x]) \leqslant \alpha \cdot size(x) </tex>, где <tex>size(left[x])</tex> и <tex>size(right[x])</tex> {{- --}} размер левого и правого поддерева вершины <tex>x</tex>. === Плюсы ===* Данное дерево позволяет ускорить одни операции взамен на ускорение других, что отличает его от других (простое бинарное дерево, красно-черное дерево, splay-дерево). Результаты исследований показывают, что Scapegoat tree работает на случайных данных быстрее, чем красно-черное.* Требует меньше памяти, так как не надо хранить дополнительную информацию в вершине для балансировки.* Настройки скорости можно менять в процессе выполнения программы. === Минусы === * Данное дерево сложно для написания.* В случае неправильной настройки скорости работы дерево будет проигрывать по скорости работы другим.
Если условие нарушается, запускается операция перебалансировки дерева. Заметим, что при <tex>\alpha = 1</tex> деревом будет считаться даже линейная структура.
Примечание:
Существует два подхода к балансу дерева, которые дают похожий результат. Первый {{- --}} задавать <tex>\alpha</tex>. Второй {{--- }} задать ограничение <tex>q</tex>, большее чем число элементов в дереве (чем больше ограничение, тем более несбалансированным может быть дерево), и следить, чтобы <tex>\log_{3/2}(q)</tex> был больше максимальной глубины дерева. В противном случае, необходимо произвести перебалансировку дерева.
== Свойства ==
* В некоторых случаях операции модификации занимают <tex>O(n)</tex>, хотя из амортизированная сложность - <tex>O(\log n)</tex>.
* За счет отсутствия необходимости хранить дополнительные данные в вершинах данное дерево оптимальнее остальных по памяти.
== Структура ==
=== Структура вершины n ===
'''n.key''' {{---}} значение в вершине
'''n.left''' {{---}} левый ребенок вершины
'''n.right''' {{---}} правый ребенок вершины
'''n.height''' {{---}} высота поддерева данной вершины
'''n.depth''' {{---}} глубина вершины
'''n.parent''' {{---}} ссылка на родителя
'''n.sibling''' {{---}} ссылки на "братьев" данной вершины
=== Структура дерева T ===
'''T.root''' {{---}} ссылка на корень дерева
'''T.size''' {{---}} число вершин в дереве
'''T.maxSize''' {{---}} максимальное число вершин в дереве после последней перебалансировки
'''T.hα''' {{---}} вспомогательное значение, вычисляется как: <tex>T.hα = ⌊log1/α (T.size)⌋</tex>
'''T.height''' {{---}} высота дерева
== Операции ==
Пока дерево остается <tex>\alpha</tex>-сбалансированным, выполняем модифицированную вставку элемента в дерево, которая аналогична обычной вставке в двоичное дерево, но операция <tex>InsertKey(k)</tex> будет возвращать глубину данной вершины. В тот момент, когда дерево стало несбалансированным, надо начать поиск вершины, которая нарушает условие сбалансированности. Для этого надо пройти по дереву вверх. Только что вставленная вершина ей быть не может. После нахождения этой вершины надо запустить операцию перебалансировки.
Нам нужна специальная функция <tex>FindScapegoat(n)</tex>, которая позволяет найти тот элемент дерева, который испортил баланс (именно из-за этой процедуры дерево так называется. Scapegoat - "козел отпущения", который испортил баланс).
=== Удаление элемента элемента ===
Сначала надо удалить вершину, как в обычном двоичном дереве. Потом надо проверить дерево на сбалансированность. Если дерево осталось сбалансированным, ничего делать не надо. В противном случае надо начать перебалансировку дерева.
Функция DeleteKey(k) удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.
