Предполагается, что новая вершина вставляется на уровне листьев, или терминальных вершин (как левое или правое поддерево). При такой вставке показатели сбалансированности могут изменится только у тех вершин, которые лежат на пути между корнем дерева и вновь вставляемым листом.
Алгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева. Определение типа узла имеет вид:
TYPE ref=^node; { указатель }
node=record
key:integer; { ключ узла }
left,right:ref; { указатели на ветви }
bal:-1..+1; { флаг сбалансированности }
end;
Процесс включения узла состоит из последовательности таких трех этапов:
· 1. Следовать по пути поиска, (по ключу), пока не будет найден ключ или окажется,что ключа нет в дереве.
· 2. Включить новый узел и определить новый показатель сбалансированности.
· 3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.
На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому можно ввести в список параметров переменную h, означающую "высота поддерева увеличилась".
Необходимые операции балансировки полностью заключаются в обмене значениями ссылок. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному "повороту" двух или трех узлов.