Dispose(q). Внутренняя процедура Del работает в случае 3)

End

end; { Delete }

Внутренняя процедура Del работает в случае 3). Она "спускается" вдоль правой ветви левого поддерева узла q^, который нужно исключить, и заменяет информацию в q^ на информацию из самой правого узла p^ левого поддерева.

На рисунке 6 б) изображено дерево, полученное при удалении из дерева на рисунке 6 а) узла со значением 5.

Можно реализовать удаление узла для случая 3) и другим способом. Удаляемый узел заменяется любым из поддеревьев, например, левым. Оставшееся правое поддерево добавляется в левое так, чтобы сохранилось свойство дерева поиска. При добавлении правого поддерева в левое поддерево используется алгоритм вставки в дерево поиска. Измененный вариант процедуры исключения Delete1 и вспомогательная процедура вставки в дерево поиска Insert для случая, когда добавляемый элемент является уже готовым узлом (в нашем случае – поддеревом), выглядят следующим образом:

procedure Delete1(var T: Tree; x: integer);

var q: Tree;

procedure Insert(var T: Tree; p: Tree);

Begin

if T = nil then T:=p

Else

if p^.inf < T^.inf then Insert(T^.L,p)

else Insert(T^.R,p)

end; { Insert }

Begin

if T = nil then { элемента в дереве нет }

Else

if x < T^.inf then Delete1(T^.L, x)

Else

if x > T^.inf then Delete1(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 begin T:= q^.L;

Insert(T,q^.R)

End;

{ освобождение памяти, выделенной для размещения узла q^ }