96
правок
Изменения
→Вставка элемента
Представьте себе в уме дерево, состоящее из трёх вершин — корня и двух подвешенных как «левые» сыновья вершин. In-order обход вернёт нам эти вершины в порядке от самой «глубокой» до корня, но хранить в отдельной памяти по ходу этого обхода нам придётся всего одну вершину (самую глубокую), поскольку когда мы придём во вторую вершину, мы уже будем знать, что это медиана и она будет корнем, а остальные две вершины — её детьми. Т.е. расход памяти здесь — на хранение одной вершины, что согласуется с верхней оценкой для дерева из трёх вершин — <tex>\log(3)</tex>.
Таким образом, если нужно сэкономить память, то 2 способ перебалансировки дерева {{---}} лучший вариант.
<gallery align="center" mode="packed" heights="160px">
Файл:Good_insert_1.png|Вставка без нарушения баланса 1
Файл:Good_insert_2.png|Вставка без нарушения баланса 2
Файл:Bad_insert.png|Вставка с нарушением баланса. Вершина 5 стала Scapegoat, будет запущена перебалансировка
</gallery>
===Псевдокод===
*<tex>n</tex> {{---}} узел дерева. Обычно, процедура вызывается от только что добавленной вершины.
'''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
Сама вставка элемента:
*<tex>k</tex> {{---}} ключ, который будет добавлен в дерево.
'''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
=== Удаление элемента ===
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей).
