Включение в дерево поиска

Поиск в дереве поиска.

Procedure Dpoisk (root:pNode;x:tInfo;var pt:pNode;var found:boolean);

Begin

found:=false;

pt:=root;

while not found and (pt<>nil) do

begin

if pt^.info=x then found:=true

else

if pt^.info>x then pt:=pt^.left

else pt:=pt^.right;

end;

end;

Замечание. Данный поиск будет действительно дихотомическим, если исходное дерево полное (идеально сбалансированное).

Включим 13 в дерево.

procedure Vstavka(var root:pNode;x:tInfo);

var found:boolean;

pt, ptpred:pNode;

begin

pt:=root;

found:=false;

while not found and (pt<>nil) do

begin

if pt^.info=x then found:=true

else if x>pt^.info then pt:=pt^.right

else pt:=pt^.left;

end;

if not found then

begin

new(ptpred);

ptpred^.info:=pt^.info;

if x<pred^.info then pred:=pt^.left

else pred:=pt^.right;

end;

end;

Аналогична задаче поиска, но сохраняет ссылку на предыдущую вершину ptpred:pNode. Как только pt=nil – ptpred – ссылка на вершину, после которой надо вставить данное значение.

Завести дополнительную ссылку ptpred, указывающую на последнюю пройденную вершину.

ptpred:=pt;

Когда pt=nil ptpred указывает на нужный элемент, то есть ptpred указывает на вершину, после которой нужно вставить вершину.

Упражнение: завершить реализацию вставки в дерево поиска. Построить дерево поиска.

Тривиальное решение: создать из первого элемента входной последовательности корень, затем, пока не кончилась входная последовательность, включать очередной элемент в построенное к этому шагу дерево.

К сожалению, предыдущее решение не строит сбалансированное дерево. Вставка с сохранением сбалансированности – сложная задача (в этом случае используются специальные типы деревьев). Хотя задача построения сбалансированного дерева не столь сложна:

1) Найти среднее значение во входной последовательности и сделать его корнем дерева.

2) Сделать то же для всех элементов, меньших корня (левое поддерево) и больших корня (правое поддерево).

Формулировка алгоритма рекурсивная. (см. Рекурсия)

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