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>.
=== Плюсы ===
Примечание:
Существует два подхода к балансу дерева, которые дают похожий результат. Первый {{- --}} задавать <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) удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.
