Операция вставки вершины в сбалансированное дерево

Предполагается, что новая вершина вставляется на уровне листьев, или терминальных вершин (как левое или правое поддерево). При такой вставке показатели сбалансированности могут изменится только у тех вершин, которые лежат на пути между корнем дерева и вновь вставляемым листом.

Алгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева. Определение типа узла имеет вид:

TYPE ref=^node; { указатель }

node=record

key:integer; { ключ узла }

left,right:ref; { указатели на ветви }

bal:-1..+1; { флаг сбалансированности }

end;

Процесс включения узла состоит из последовательности таких трех этапов:

· 1. Следовать по пути поиска, (по ключу), пока не будет найден ключ или окажется,что ключа нет в дереве.

· 2. Включить новый узел и определить новый показатель сбалансированности.

· 3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.

На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому можно ввести в список параметров переменную h, означающую "высота поддерева увеличилась".

Необходимые операции балансировки полностью заключаются в обмене значениями ссылок. Фактически ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному "повороту" двух или трех узлов.