Сбалансированные двоичные деревья

 

После каждой операции изменения дерева можно проводить балансировку дерева, которая позволяет минимизировать его высоту. При этом поиск по двоичному дереву будет требовать минимального времени. Балансировка позволяет также ускорить операции вставки и удаления узлов, которые тоже требуют проведения поиска.

К сожалению, пока нет способа проведения быстрой балансировки дерева до его минимальной высоты. Тем не менее, балансировка является очень эффективным методом. Мы не можем провести балансировку дерева до его минимальной высоты, но, задав критерий "разбалансированности" дерева перед проведением очередной балансировки, можно приблизиться к этой минимальной высоте. В этом случае, хотя мы и не получаем дерева с минимально возможной высотой в каждый момент времени, тем не менее, находимся близко к минимуму.

Алгоритм балансировки состоит из двух частей:

1. Дерево преобразуется в лозу.

2. Лоза перестраивается в сбалансированное дерево.

Лоза (vine) — это левоассоциативное двоичное дерево. Она имеет следующий вид:

Рис.1. Левоассоциативное двоичное дерево – лоза.

 

Главная лоза (рис.2) (main vine) — это левоассоциативное поддерево двоичного дерева.

Рис.2. Левоассоциативное поддерево двоичного дерева.

 

На рисунке вершины главной лозы окрашены в белый цвет.