Поиск по бинарному дереву с удалением

Удаление узла не должно нарушить упорядоченности дерева.

Возможны три варианта.

Найденный узел является листом. Тогда он просто удаляется с помощью обычной процедуры удаления.

Найденный узел имеет только одного сына. Тогда сын перемещается на место отца.

У удаляемого узла два сына. Тогда на место отца помещается либо его предшественник при обходе слева направо, либо его преемник при том же обходе.

Предшественник - это самый правый элемент левого поддерева (для достижения этого элемента необходимо перейти в следующий узел по левой ветви, а затем двигаться только по правой ветви этого узла до тех пор, пока очередная ссылка не будет равна nil.

Преемник - это самый левый элемент правого поддерева (для достижения этого элемента необходимо перейти в следующий узел по правой ветви, а затем двигаться только по левой ветви этого узла до тех пор, пока очередная ссылка не будет равна nil.

Предшественником удаляемого узла (12) является самый правый узел левого поддерева (11). Преемником узла (12) - самый левый узел правого поддерева (13).

Будем разрабатывать алгоритм для преемника (узел 13), который будет поставлен на место удаляемого узла 12.

Введем указатели:

p - рабочий указатель;

q - отстает от р на один шаг;

v - указывает на преемника удаляемого узла;

t - отстает от v на один шаг;

s - на один шаг впереди v (указывает на левого сына или пустое место).

В итоге работы алгоритма на узел 13 должен указывать указатель v, а указатель s - на пустое место (как показано на рисунке).

q = nil

p = tree

while (p <> nil) and (k(p) <> key) do

q = p

if key < k(p) then

p = left(p)

else

p = right(p)

endif

endwhile

if p = nil then ‘ Ключ не найден ’

return

endif

if left(p) = nil then v = right(p)

else if right(p) = nil

then v = left(p)

else

‘ У nod(p) - два сына ’

‘ Введем два указателя (t отстает от v на 1 шаг, s - опережает )’

t = p

v = right(p)

s = left(v)

while s <> nil do

t = v

v = s

s = left(v)

endwhile

if t <> p then

‘v не является сыном p’

left(t) = right(v)

right(v) = right(p)

endif

left(v) = left(p)

endif

endif

if q = nil then ‘p - корень ’

tree = v

else if p = left(q)

then left(q) = v

else right(q) = v

endif

endif

freenode(p)

return