Процедура удаления элемента из бинарного дерева
Удаление узла не должно нарушать упорядоченность дерева. При удалении элемента из бинарного дерева с заданным ключом различают три случая :
1) удаляемый узел является листом, в этом случае он просто удаляется, не нарушая этим упорядоченность дерева ;
2) если удаляемый узел имеет только одного сына, то сын перемещается на место удаляемого отца ;
4) если у удаляемого узла 2 сына. В этом случае на место удаляемого отца помещается либо его предшественник в симметричном обходе (обход слева направо), либо его последователь.
Разработаем алгоритм для 3-его случая (вершина-узел имеет 2-х сыновей), вместо удаляемого узла поставим его приемника в симметричном обходе. Предшественником удаляемого узла 12 является самый правый узел левого поддерева - узел 11, а приемником или последователем при симметричном обходе (обход слева направо) является самый левый узел правого поддерева - узел 13.
Будем использовать следующие указатели :
p - рабочий указатель;
q - отстает на один шаг от p;
v - указывает приемника;
t - отстает от v на один шаг;
s - опережает v на один шаг.
1) Процедурой поиска элемента находим удаляемый элемент. Указатель p указывает на удаляемый элемент.
2) Установим указатель v на узел, который будет замещать удаляемый элемент.
IF left (p)=nil
THEN v=right (p)
ELSE IF right (p)=nil
THEN v=left (p)
ELSE t=p
v=right (p)
s=left (v)
WHILE s<>nil
t=v
v=s
s=left (v)
END WHILE
IF t<>p
THEN WRITE (v не является сыном p)
left (t)=right (v)
right (v)=right (p)
END IF
left (v)=left (p)
IF q=nil
THEN WRITE (v корень)
tree=v
RETURN
END IF
IF p=left (q)
THEN left (q)=v
ELSE right (q)=v
END IF
END IF
END IF
FREENODE (p) (процедура создает свободный узел, т.е. очищает ячейку памяти, в которой находится удаленный элемент)
RETURN
