Операция исключения из бинарного дерева

При удалении узла дерево должно оставаться упорядоченным относительно ключа:

а) удаляется лист;

б) удаляется узел с одним потомком (потомок слева или справа);

в) удаляется узел с двумя потомками, но в левом потомке нет правого поддерева;

г) общий случай.

t

Рассмотрим случай б):

t

if g^.L_Son=nil then begin

K

K

g:=t;

t:=t^.R_Son;

g

g

dispose(g);

end;

if g^.R_Son=nil then begin

g:=t;

t:=t^.L_Son;

dispose(g);

end;

Случай а) является частным случаем этого алгоритма.

Случай в): r указывает на элемент, не имеющий правого поддерева.

g:=t;

t

g^.key:=r^.key;

g

К

g:=r;

r

r:=r^.L_Son;

dispose(g);

Мы ищем такой элемент, у которого отсутствует правое поддерево (на такой элемент указывает r). Последовательность операторов та же, т.е. удаляемый элемент нужно заменить самым правым элементом его левого поддерева. Такие элементы не могут иметь более одного потомка.

Случай г):

Procedure Get (x: integer; var t: ElPtr);

var g: ElPtr;

begin

if t=nil then {обработка исключительной ситуации, когда элемента с заданным ключом в дереве нет}

else if x>t^.key then Get(x, t^.R_Son)

else if x<t^.key then Get(x, t^.L_Son)

else begin

g:=t;

if g^.L_Son=nil then t:=g^.R_Son

else if g^.R_Son=nil then t:=g^.R_Son

else D(g^.L_Son); {найти r)

dispose(g);

end;

end;

Дата добавления: 2014-01-07