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