96
правок
Изменения
→Тривиальный способ перебалансировки
# Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.
Данный способ требует <tex>O\mathtt{(weight(Scapegoat-root))}</tex> времени и столько же памяти.
====== Получение списка ======
*<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
====Более сложный способ перебалансировки====
Время работы перебалансировки вряд ли улучшится — всё-таки каждую вершину нужно «подвесить» в новое место. Но можно попробовать сэкономить память. Давайте посмотрим на 1 способ алгоритма внимательнее. Вот выбирается медиану, подвешивается в корень, дерево делится на два поддерева — и делится весьма однозначно. Никак нельзя выбрать «какую-то другую медиану» или подвесить «правое» поддерево вместо левого. Та же самая однозначность преследует и на каждом из следующих шагов. Т.е. для некоторого списка вершин, отсортированных в возрастающем порядке, будет ровно одно порождённое данным алгоритмом дерево. А откуда же берется отсортированный список вершин? Из in-order обхода изначального дерева. То есть каждой вершине, найденной по ходу in-order обхода перебалансируемого дерева соответствует одна конкретная позиция в новом дереве. И можно эту позицию рассчитать и без создания самого отсортированного списка. А рассчитав — сразу её туда записать. Возникает только одна проблема — этим затирается какая-то (возможно ещё не просмотренная) вершина — что же делать? Хранить её. Где? Ответ прост: выделять для списка таких вершин память. Но этой памяти нужно будет уже не <tex>O(weight(N))</tex>, а всего лишь <tex>O(\log N)</tex>.
