Добавление элемента.
Процедурадобавляет заданный элемент в подходящее место дерева . Параметром процедуры является указатель на новую вершину, в которую помещены значения,и . В ходе работы процедура изменяет дерево и (возможно) некоторые поля вершины , после чего новая вершина с данным значением ключа оказывается вставленной в подходящее место дерева:
Подобно процедурами , процедурадвигается вниз по дереву, начав с его корня. При этом в вершине сохраняется указатель на родителя вершины . Сравниваяс , процедура решает куда идти — налево или направо. Процесс завершается, когда становится равным . Этот стоит как раз там, куда надо поместить , что и делается. Очевидно, добавление требует временидля дерева высоты .
