Алгоритм Т. (Поиск с вставкой по дереву.)
Дана таблица записей, образующих бинарное дерево.
Производится поиск заданного аргумента К.
Если его нет в таблице, то в подходящем месте в дерево вставляется новый узел, содержащий К.
Предполагается, что узлы дерева содержат по крайней мере следующие поля:
КЕY(Р) = ключ, хранящийся в узле NODE(P);
LLINK(P) = указатель на левое поддерево узла NODE(P);
RLINK(P) = указатель на правое поддерево узла NODE(P).
Пустые поддеревья представляются пустыми указателями Л. Переменная ROOT указывает на корень дерева. Для удобства предполагается, что дерево не пусто
(ROOT != Л), так как при ROOT = Л операции становятся тривиальными.
Т1. [Начальная установка.] Установить Р = ROOT. (Указатель Р будет продвигаться вниз по дереву.) ,
Т2. [Сравнение.] Если К < KEY(P), то перейти на ТЗ;
если K>KEY(P), то перейти на Т4;
если K=KEY(P), поиск завершен удачно.
ТЗ. [Шаг влево.] Если LLINK(P) != Л, установить Р = LLINK(P) и вернуться на Т2.
В противном случае перейти на Т5.
Т4. [Шаг вправо.] Если RLINK(P) != Л, установить Р = RLINK(P) и вернуться на Т2.
Т5, [Вставка в дерево.] (Поиск неудачен; теперь мы поместим К в дерево.)
Выполнить Q = AVAIL; Q теперь указывает на новый узел. Установить KEY(Q) = K, LLINK(Q) = RLINK(Q) = Л. (На самом деле нужно произвести началь-, ную установку и других полей нового узла.) Если К было меньше KEY(P), установить LLINK(P) = Q; в противном случае установить RLINK(P) = Q. (В этот момент мы могли бы присвоить Р = Q и удачно завершить работу алгоритма.).