Изменения

Перейти к: навигация, поиск

Взвешенное дерево

1315 байт добавлено, 16:27, 21 июня 2017
Тривиальный способ перебалансировки
# Для «левого» и «правого» поддерева рекурсивно повторяется та же операция.
Данный способ требует <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>.
96
правок

Навигация