Структуры данных. Деревья - 28 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

30
begin
if T = nil then { элемента в дереве нет }
else
if x < T^.inf then Delete(T^.L, x)
else
if x > T^.inf then Delete(T^.R, x)
else
begin { исключение узла T^ }
q:=T;
if q^.R = nil then T:=q^.L
else
if q^.L = nil then T:=q^.R
else Del(q^.L);
{ освобождение памяти, выделенной для размещения узла q^ }
dispose(q)
end
end; { Delete }
Внутренняя процедура Del работает в случае 3). Она "спускается" вдоль
правой ветви левого поддерева узла q^ , который нужно исключить, и заменяет
информацию в q^ на информацию из самой
правого узла p^ левого поддерева.
На рисунке 6 б) изображено дерево, полученное при удалении из дерева на
рисунке 6 а) узла со значением 5.
Можно реализовать удаление узла для случая 3) и другим способом. Уда-
ляемый узел заменяется любым из поддеревьев, например, левым. Оставшееся
правое поддерево добавляется в левое так, чтобы сохранилось свойство дерева
поиска. При
добавлении правого поддерева в левое поддерево используется ал-
горитм вставки в дерево поиска. Измененный вариант процедуры исключения
Delete1 и вспомогательная процедура вставки в дерево поиска Insert для случая,

Страницы