Стр. 36 - Основы алгоритмов и структур данных

34 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
i
b
c
a
d
Рис. 25. Состояние дерева после удаления узла z
?Алгоритм удаления записать самостоятельно?
Очевидно, после выполнения многочисленных включений и исключений,
дерево бинарного поиска может стать существенно асимметричным, или
разбалансированным.
Следовательно, необходима дополнительная операция балансировки
дерева. Выгоднее выполнять балансировку после каждого включения или
исключения.
4.4.1.3. Балансировка по высоте
Балансировка по высоте означает, что при проверке баланса учитываются
только высоты поддеревьев и не учитываются частоты обращения к ним.
Для учета частот достаточно применить те же алгоритмы, что и без учета,
изменив лишь правила проверки баланса.
Определение. Бинарное дерево Т сбалансировано по высоте тогда и только
тогда, когда его левое и правое поддеревья r l TT , удовлетворяют следующим
условиям:
1. Разность высот ( ) ( ) 1l r h T h T− ≤ .
2. Оба r l TT , сбалансированы по высоте.
Пример сбалансированных деревьев.
Пустое дерево, из 1-й вершины, из двух вершин.