Основы программирования. Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы - 39 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

41
else Result:=Search(x,r.left);
end;
Удаление элемента из БДП
Удаление элемента из БДП является самым сложным из рассматриваемых
алгоритмов. Возможны три случая.
a) Требуется удалить лист.
22 64
41
8 34 50 77
22 64
41
8 50 77
Удаляем лист и указателю, который на него указывал, присваиваем nil.
б) Требуется удалить элемент, который имеет только одно поддерево.
22 64
41
8 50 77
64
41
8 50 77
Запоминаем адрес единственного поддерева этого элемента, удаляем сам элемент,
после чего указателю, который на него указывал, присваиваем адрес поддерева.
Очевидно, при подобном удалении дерево остается БДП.
в) Требуется удалить элемент, у которого есть левое и правое поддеревья.
Вначале найдем этот элемент, используя рекурсию. Он является корнем не-
которого поддерева, и
сам имеет левое и правое поддеревья.
22 64
41
8 34 50 77
28
26 31
22 64
34
8 34 50 77
28
26 31
Пусть в дереве, изображенном на рисунке, требуется удалить элемент со зна-
чением 41. Вначале найдем элемент, значение которого непосредственно предше-
ствует значению корневого элемента. Таковым является самый правый элемент в
левом поддереве корня (на рисунке это элемент со значением 34). Перепишем
значение этого элемента в корневой, после чего удалим этот элемент. Заметим,
что поскольку он – самый правый в левом поддереве, то у него нет правого под-

Страницы