Добавление вершины в дерево поиска

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

· найдена вершина с заданным значением ключа, и в этом случае просто увеличивается счетчик

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

Само добавление включает следующие шаги:

· выделение памяти для новой вершины

· формирование информационной составляющей

· формирование двух пустых ссылочных полей на будущих потомков

· формирование в родительской вершине левого или правого ссылочного поля – адреса новой вершины

Здесь только последняя операция вызывает некоторую сложность, поскольку для доступа к ссылочному полю родительской вершины надо знать ее адрес. Ситуация аналогична добавлению элемента в линейный список перед заданным, когда для отслеживания элемента-предшественника при проходе по списку использовался дополнительный указатель. Этот же прием можно использовать и для деревьев, но есть более элегантное решение – рекурсивный поиск с добавлением новой вершины при необходимости. Каждый рекурсивный вызов отвечает за обработку очередной вершины дерева, начиная с корня, а вся последовательность вложенных вызовов позволяет автоматически запоминать путь от корня до любой текущей вершины. Процедура поиска должна иметь формальный параметр-переменную ссылочного типа, который отслеживает адрес текущей вершины дерева и как только этот адрес становится пустым, создается новая вершина и ее адрес возвращается в вызвавшую процедуру, тем самым автоматически формируя необходимую ссылку в родительской вершине.

Procedure AddNode ( var pCurrent : Tp);

begin

if pCurrent = nil then{место найдено, создать новую вершину}

begin

New ( pCurrent ); {параметр pCurrent определяет адрес новой вершины}

pCurrent^.inf := “необходимое значение”;

pCurrent^.left := nil; pCurrent^.right := nil;

“установка значения поля счетчика в 1 “;

end

else {просто продолжаем поиск в левом или правом поддереве}

ifx < pCurrent^.inf then AddNode (pCurrent^.left)

else if x > pCurrent^.inf then AddNode (pCurrent^.right)

else “увеличить счетчик”

end;

Запуск процедуры выполняется в главной программе вызовом AddNode(pRoot). Если дерево пустое, т.е. pRoot = nil, то первый вызов процедуры создаст корневую вершину дерева, к которой потом можно аналогичными вызовами добавить любое число вершин.

Рассмотрим нерекурсивный вариант процедуры добавления вершины в ДП. Необходимо объявить две ссылочные переменные для отслеживания адреса текущей вершины и адреса ее родителя:

pCurrent, pParent : Tp;

Удобно отдельно рассмотреть случай пустого дерева и дерева хотя бы с одной корневой вершиной:

if pRoot = nil then

Begin

New (pRoot); pRoot^.left := nil; pRoot^.right := nil;

“заполнение остальных полей”;

End

Else

Begin

pCurrent := pRoot; {начинаем поиск с корня дерева}

while (pCurrent <> nil ) do

Begin

pParent := pCurrent; {запоминаем адрес родительской вершины}

if ( x < pCurrent^.inf) then pCurrent := pCurrent^.left

else if ( x > pCurrent^.inf) then pCurrent := pCurrent^.right

else begin {вершина найдена, добавлять не надо, закончить цикл}

pCurrent := nil;

“увеличить счетчик”;

end;

end;

if ( x < pParent^.inf) then

begin {добавляем новую вершину слева от родителя}

New (pCurrent);

“заполнить поля новой вершины”;

pParent^.left := pCurrent;

End

Else

if ( x > pParent^.inf) then

begin {добавляем новую вершину справа от родителя}

New (pCurrent);

“заполнить поля новой вершины”;

pParent^.right := pCurrent;

End

end;