Добавление нового узла ( dop ).

ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ).

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

Алгоритм поиска нужной вершины, вообще говоря, тот же самый, что и при поиске вершины с заданным ключом. Эта вершина будет найдена в тот момент, когда в качестве очередного указателя, определяющего ветвь дерева, в которой надо продолжить поиск, окажется указатель NIL ( случай 2 функции Find ). Тогда процедура вставки записывается так, как в программном примере 6.3.

{=== Программный пример 6.3. Добавление звена ===} Procedure Dob (k:KeyType; var d:TreePtr; zap:data); { k - ключ, d - узел дерева, zap - запись } Var r,s: TreePtr; t: DataPtr; Begin if not Find(k,d,r) then begin (* Занесение в новое звено текста записи *) new(t); t^:=zap; new(s); s^.key:=k; s^.ssil:=t; s^.left:=NIL; s^.right:=NIL; if d = NIL then d:=s (* Вставка нового звена *) else if k < r^.key then r^.left:=s else r^.right:=s; end; End; { Dop }