Добавление и удаление

Далее будет рассмотрен нерекурсивный алгоритм добавления элемента в дерево. Сначала надо найти вершину, к которой в качестве потомка необходимо добавить новую вершину (фактически, произвести поиск), а затем присоединить к найденной новую вершину, содержащую значение Item (процедура написана в предположении, что добавляемого элемента в дереве нет).

procedure TreeAdd(Item: TypeElement; var Tree: PTree);

{Добавление в дерево вершины со значением Item}

var

NewNode, Current: PTree;

begin

if Tree = nil then begin {Дерево пустое}

{Создаем корень}

New(Tree);

Tree^.Data := Item;

Tree^.Left := nil;

Tree^.Right := nil;

end else begin

Current := Tree;

{Поиск вершины}

while ((Item > Current^.Data) and (Current^.Right <> nil)) or

((Item < Current^.Data) and (Current^.Left <> nil)) do

if Item > Current^.Data then

Current := Current^.Right

else

Current := Current^.Left;

{Создание новой вершины}

New(NewNode);

NewNode^.Data := Item;

NewNode^.Left := nil;

NewNode^.Right := nil;

If Item > Current^.Data then {Новая вершина больше найденной}

Current^.Right := NewNode {Присоединяем новую справа}

else {Новая вершина меньше найденной}

Current^.Left := NewNode; {Присоединяем новую слева}

end;

end;

Листинг 3.29 – Процедура добавления элемента в двоичное дерево поиска

Листинг 3.30 – Процедура добавления элемента в двоичное дерево поиска

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

Нельзя забывать, что при замене вершина, на которую производится замена, может иметь правое поддерево. Это поддерево необходимо поставить вместо перемещаемой вершины.

procedure TreeDelete(Item: TypeElement; var Tree: PTree);

{Удаление из дерева вершины со значением Item}

var

Parent, Cur, Cur2: PTree;

Direction: (L, R); {направление движения (влево/вправо)}

begin

{Поиск удаляемого элемента}

Parent := nil; {предок удаляемой вершины}

Cur := Tree;

while ((Item > Cur^.Data) and (Cur^.Right <> nil)) or

((Item < Cur^.Data) and (Cur^.Left <> nil)) do begin

Parent := Cur;

if Item > Cur^.Data then begin

Cur := Cur^.Right; Direction := R;

end else begin

Cur := Cur^.Left; Direction := L;

end;

end;

if Cur <> nil then begin {Вершина найдена}

{Анализируем наличие потомков у найденной вершины}

{и удаляем соответствующим образом}

if (Cur^.Left <> nil) and (Cur^.Right <> nil) then begin

{Удаление вершины в случае наличия у нее обоих потомков}

Parent := Cur; Cur2 := Cur^.Right;

{Поиск кандидатуры на замену}

while Cur2^.Left <> nil do begin

Parent := Cur2; Cur2 := Cur2^.Left;

end;

{Заменяем}

Cur^.Data := Cur2^.Data;

{Спасаем правое поддерево вершины, которой заменяем}

if Parent <> Cur then

Parent^.Left := Cur2^.Right

else

Parent^.Right := Cur2^.Right;

Dispose(Cur2);

end else begin

{Удаление вершины в случае наличия у нее}

{не более одного потомка}

if (Cur^.Left = nil) then begin

if Parent <> nil then begin

if Direction = L then

Parent^.Left := Cur^.Right

else

Parent^.Right := Cur^.Right;

end else begin

Tree := Cur^.Right;

end;

end;

if (Cur^.Right = nil) then begin

if Parent <> nil then begin

if Direction = L then

Parent^.Left := Cur^.Left

else

Parent^.Right := Cur^.Left;

end else begin

Tree := Cur^.Left;

end;

end;

Dispose(Cur);

end;

end;

end;

Листинг 3.31 – Процедура удаления элемента из двоичного дерева поиска

Листинг 3.32 – Процедура удаления элемента из двоичного дерева поиска

Рисунок 3.14 – Удаление элемента из двоичного дерева поиска

Удаление вершины z из двоичного дерева поиска. (а) Если вершина z не имеет детей её можно удалить без проблем. (6) Если вершина z имеет одного ребёнка, помещаем его на место вершины z. (в) Если у вершины z двое детей, процесс сводится к предыдущему случаю, т.е. удаляем вместо неё вершину у с непосредственно следующим значением ключа (у этой вершины ребёнок один) и помещая ключ kеу[у] (и связанные с ним дополнительные данные) на место вершины z.

Временная сложность этих алгоритмов (она одинакова для этих алгоритмов, так как в их основе лежит поиск) оценим для наилучшего и наихудшего случая. В лучшем случае, – то есть случае полного двоичного дерева – получаем сложность O_min(log n). В худшем случае дерево может выродиться в список. Такое может произойти, например, при добавлении элементов в порядке возрастания. При работе со списком в среднем придется просмотреть половину списка. Это даст сложность O_max(n).

В процедуре очистки дерева применяется обратный метод обхода дерева. Использование обратного метода обхода гарантирует, что будут сначала посещены и удалены все потомки предка, прежде чем удалится сам предок.

procedure TreeClear(var Tree: PTree);

{Очистка дерева}

begin

if Tree <> nil then begin

TreeClear(Tree^.Left);

TreeClear(Tree^.Right);

Dispose(Tree);

Tree := nil;

end;

end;

Листинг 3.33 – Процедура очистки двоичного дерева поиска

Временная сложность этой операции O(n).