54
правки
Изменения
→Операции
'''return''' false;
'''else if''' height > T.hα:
scapegoat = '''FindScapegoat'''(Search(T.root, k)) '''RebuildTree'''(n.size(), scapegoat)
'''return''' true
=== Удаление элемента элемента ===
Функция DeleteKey(k) удаляет элемент, аналогично удалению в бинарном дереве, и возвращает глубину удаленного элемента.
*<tex>k</tex> {{---}} ключ, который будет удален.
'''Delete'''(k):
deleted = '''DeleteKey'''(k)
'''if''' deleted:
'''if''' T.size < (T.α · T.maxSize):
'''RebuildTree'''(T.size, T.root)
=== Перебалансировка дерева ===
Общая идея процедуры выглядит следующим образом: сначала из исходного дерева мы получаем список вершин в неубывающем порядке, при этом вершина стоит в списке перед детьми. После этого мы создаем новое дерево из списка.
==== Получение списка ====
*<tex>root</tex> {{---}} корень дерева, которое будет преобразовано в список.
'''FlattenTree'''(root, head):
'''if''' root = null:
'''return''' head
root.right = FlattenTree(root.right, head)
'''return''' FlattenTree(root.left, root)
==== Построение дерева ====
*<tex>size</tex> {{---}} число вершин в списке.
*<tex>head</tex> {{---}} первая вершина в списке.
BuildHeightBalancedTree(size, head):
'''if''' size = 1 then:
return head
'''else if''' size = 2 then:
(head.right).left = head
'''return''' head.right
root = (BuildHeightBalancedTree(⌊(size − 1)/2⌋, head)).right
last = BuildHeightBalancedTree(⌊(size − 1)/2⌋, root.right)
root.left = head
'''return''' last
==== Перестроение дерева ====
*<tex>size</tex> {{---}} число вершин в поддереве.
*<tex>scapegoat</tex> {{---}} вершина, которая испортила баланс.
'''RebuildTree'''(size, scapegoat):
head = '''FlattenTree'''(scapegoat, null)
'''BuildHeightBalancedTree'''(size, head)
'''while''' head.parent!=null do
head = head.parent
'''return''' head
== Оценка времени работы ==
