Для включения записи в дерево прежде всего нужно найти в дереве ту вершину, к которой можно "подвести" (присоединить) новую вершину, соответствующую включаемой записи. При этом упорядоченность ключей должна сохраняться.
Алгоритм поиска нужной вершины, вообще говоря, тот же самый, что и при поиске вершины с заданным ключом. Эта вершина будет найдена в тот момент, когда в качестве очередного указателя, определяющего ветвь дерева, в которой надо продолжить поиск, окажется указатель 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 }