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^ }
|
