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

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

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

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

• · выделение памяти для новой вершины
• · формирование информационной составляющей
• · формирование двух пустых ссылочных полей на будущих потомков
• · формирование в родительской вершине левого или правого ссылочного поля — адреса новой вершины

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

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 {просто продолжаем поиск в левом или правом поддереве}.

if x < 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;