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

40 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
Пример.
E
C
A
G B D
H F
Рис. 35. Сбалансированное дерево
Удаляем В: дерево теряет лист.
Удаляем А ( В осталось): А=В, при удалении А (не является листом), дерево
теряет лист.
Удаляем E (имеет двух сыновей): F переставляем на место Е; дерево
потеряло лист.
Очевидно, всегда при удалении дерево теряет лист.
На следующих шагах для балансировки проходим путь от этого листа к
корню дерева.
На каждом шаге возможны следующие варианты:
1.
1
A
Рис. 36. Дерево, оставшееся сбалансированным
после удаления вершины
Очевидно, поддерево А осталось сбалансированным, его балансировать не
надо. Поскольку высота поддерева А не изменилась, остались
сбалансированными все деревья, включающие А. Следовательно, конец работы.