96
правок
Изменения
м
====== Получение списка ======
====== Построение дерева ======
====== Перестроение дерева ======
Нет описания правки
'''Scapegoat-tree''' {{---}} сбалансированное [[Дерево поиска, наивная реализация | двоичное дерево поиска]], обеспечивающее наихудшее время поиска {{---}} <tex>O(\log N)</tex>, и амортизирующее время вставки и удаления элемента {{---}} <tex>O(\log N)</tex>.
В отличие от большинства других самобалансирующихся бинарных деревьев поиска , которые обеспечивают худшем случае <tex>O(\log N)</tex> время поиска, Scapegoat деревья не требуют дополнительной памяти в узлах по сравнению с обычным двоичным деревом поиска: узел хранит только ключ и два указателя на своих потомков.
== Операции ==
'''if ''' root = null or root.key = k:
'''return ''' root
'''else if ''' k ≤ <tex>\leqslant</tex> root.left.key:
'''return ''' Search(root.left, k)
'''else''':
Классический алгоритм вставки нового элемента: поиском ищем место, куда бы подвесить новую вершину, ну и подвешиваем. Легко понять, что это действие могло нарушить <tex>\alpha</tex>-балансировку по весу для одной или более вершин дерева. И вот теперь начинается то, что и дало название нашей структуре данных: требуется найти Scapegoat-вершину — вершину, для которой потерян <tex>\alpha</tex>-баланс и её поддерево должно быть перестроено. Сама только что вставленная вершина, хотя и виновата в потере баланса, Scapegoat-вершиной стать не может — у неё ещё нет потомков, а значит её баланс идеален. Соответственно, нужно пройти по дереву от этой вершины к корню, пересчитывая веса для каждой вершины по пути. Может возникнуть вопрос - нужно ли хранить ссылки на родителей? Поскольку к месту вставки новой вершины пришли из корня дерева — есть стек, в котором находится весь путь от корня к новой вершине. Берутся родители из него. Если на этом пути от нашей вершины к корню встретится вершина, для которой критерий <tex>\alpha</tex>-сбалансированности по весу нарушился — тогда полностью перестраивается соответствующее ей поддерево так, чтобы восстановить <tex>\alpha</tex>-сбалансированность по весу.
Сразу появляется вопрос {{---}} как делать перебалансировку найденной Scapegoat-вершины?
Есть <tex>2 </tex> способа перебалансировки, {{---}} тривиальный и чуть более сложный.
====Тривиальный способ перебалансировки====
# совершается обход всего поддерева Scapegoat-вершины (включая её саму) с помощью in-order обхода — на выходе получается отсортированный список (свойство In-order обхода бинарного дерева поиска).
Данный способ требует <tex>O\mathtt{(weight(Scapegoat-root))}</tex> времени и столько же памяти.
*<tex>root</tex> {{---}} корень дерева, которое будет преобразовано в список.
'''return''' FlattenTree(root.left, root)
*<tex>size</tex> {{---}} число вершин в списке.
'''return''' last
*<tex>size</tex> {{---}} число вершин в поддереве.
head = '''FlattenTree'''(scapegoat, null)
'''BuildHeightBalancedTree'''(size, head)
'''while''' head.parent!=<tex>\ne null </tex> do
head = head.parent
'''return''' head
====Более сложный способ перебалансировки====
Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на <tex>1 </tex> способ алгоритма внимательнее. Выбирается медиана, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. Т.е. То есть для некоторого списка вершин, отсортированных в возрастающем порядке, будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(weight(N))</tex>, а всего лишь <tex>O(\log N)</tex>.
Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. Т.е. То есть расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>\log(3)</tex>.Таким образом, если нужно сэкономить память, то <tex>2 </tex> способ перебалансировки дерева {{---}} лучший вариант.
<gallery align="center" mode="packed" heights="160px">
size = 1
height = 0
'''while''' (n.parent <tex>\ne</tex> null):
height = height + 1
totalSize = 1 + size + n.sibling.size()
'''if''' height <tex> ⌊log1/α> \lfloor \log_\frac{1}{\alpha} (totalSize)⌋\rfloor</tex>:
'''return''' n.parent
n = n.parent
====Псевдокод====
Функция <tex>Delete(k) </tex> удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.
*<tex>k</tex> {{---}} ключ, который будет удален.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Деревья поиска]]
