Процедура включения элемента в дерево
Для включения новой записи в дерево прежде всего нужно найти тот его узел, к которому можно "подвесить" (присоединить) новый элемент. Алгоритм поиска нужного узла тот же самый, что и при поиске узла с заданным ключом. Этот узел будет найден в тот момент, когда в качестве очередной ссылки, определяющей ветвь дерева, в которой надо продолжить поиск, окажется ссылка NIL.
Однако непосредственно использовать описанную выше процедуру поиска нельзя, потому что по окончании вычисления ее значения не фиксируется тот узел, из которого была выбрана ссылка NIL.
Модифицируем описание процедуры поиска так, чтобы в качестве ее побочного эффекта фиксировалась ссылка на узел, в котором был найден заданный ключ (в случае успешного поиска), или ссылка на узел, после обработки которого поиск прекращен (в случае неуспешного поиска). И опишем процедуру включения элемента в дерево, учитывая, что в дереве нет узла с тем же ключом, что и у включаемого элемента.
q=nil
p=tree
WHILE p<>nil DO
q=p
IF key=k (p)
THEN search=p
RETURN
END IF
IF key<k (p)
THEN p=left (p)
ELSE p=right (p)
END IF
END WHILE
{Узел с заданным ключом не найден, требуется вставка элемента. На узел предполагаемого отца указывает q.}
V=maketree (key, rec)
{Нужно выяснить, левым или правым сыном будет вставляемый элемент V.}
IF key<k (q)
THEN left (q)=V
ELSE right (q)=V
END IF
search=V
RETURN
