Стр. 35 - Основы алгоритмов и структур данных
Упрощенная HTML-версия
33
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
i
k
z
Рис. 23. Удаление узла, имеющего одного сына
4)
z
имеет двух сыновей.
i
b
z
a
c
d
Рис 24 Удаление узла z, имеющего двух сыновей
Достаточно просто заменить
z
его непосредственным последователем, то
есть ближайшим к нему большим ключом. Очевидно, непосредственный
последователь является самым левым ключом в правом поддереве
z
(в нашем
случае
c
).
(Алгоритм поиска непосредственного последователя от
z
один шаг вправо,
затем все время влево).
Непосредственного последователя со старого места приходится удалять по
варианту (2) или (1).
Вместо непосредственного последователя, можно – использовать
непосредственного предшественника (один шаг влево, потом все время вправо).
