Удаление из дерева.

Не так просто как включение.

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

Ясно что такие элементы не могут иметь более одного потомка.

Рекурсивная процедура delete различает три случая:

1. компонента с ключом х – нет;

2. компонента с ключом х – имеет всего одного потомка;

3. компонента с ключом х – имеет более 2 потомка.

procedure delete (x:integer;var p:Link);

var q:Link;

procedure del (var z:Link);

begin

if r^.right<>nil then

del (r^.Right) else

begin

q^.key:=r^.key;

q^.count:=r^.count;

q:=r; r:=f^.Left;

end;

end;

begin {delete}

if p=nil then

wreteln(‘word is not in tree’) else

if x<p^.key then delete (x,p^.Left) else

if x>p^.key then delete (x,p^.Right) else

begin

q:=p;

if q^.Right=nil then p:=q^.Left else

if q^.Left=nil then p:=q^.Right else

del(del^.Left);

end;

Вспомогательная рекурсивная процедура del вызывается только в третьем случае. Она спускается вдоль самой правой ветки левого поддерева удаляемого узла q^ и затем заменяет сущест. инфор. (ключ и счетчик) в q^ соответ. значениями самой правой компоненты r^ этого поддерева, после чего от r^ можно освободиться.

Двоичное дерево поиска представляет собой более удобную структуру для хранения данных, чем массив. При работе с таким деревом необходимо предварительно убедится что данные не поступают в порядке возрастания или убывания т.к. дерево в этом случаи выродится в линейный список. Во многих практических случаях, однако, данные поступают в существенно случайном порядке, что позволяет строить достаточно эффективное дерево, состоящее из n – узлов время необходимое для добавления/исключения узла пропорционально алгоритму n по основанию 2, тогда как линейный поиск пропорционален n.

Не нашли, что искали? Воспользуйтесь поиском: