Добавление узлов к АVL-дереву

 

Каждый раз при добавлении узла к AVL-дереву необходимо проверять, соблюдаются ли условия, описывающие AVL-дерево. После вставки узла следует исследовать узлы в обратном порядке - к корню, проверяя, чтобы глубина поддеревьев отличалась не более чем на единицу. Если найдена ячейка, где это условие не выполняется, необходимо сдвинуть элементы, чтобы сохранить выполняемость условия AVL-дерева.

 

Вращение AVL-деревьев

 

При вставке узла в AVL-дерево в зависимости от того, в какую часть дерева добавляется узел, существует четыре варианта балансировки. Методы перебалансирования называют правым и левым вращением, вращением влево-вправо и вправо-влево. Сокращенно они обозначаются R, L, LR и RL.

Предположим, что происходит добавление нового узла к AVL-дереву и оно теперь разбалансировано в узле X, как показано на рис. 12. На рисунке изображены только узел X и два его дочерних узла, остальные части дерева обозначены треугольниками, так как нет необходимости их рассматривать. Новый узел может быть вставлен в любое из этих четырех поддеревьев, изображенных в виде треугольников ниже узла X. В зависимости от этого происходит соответствующий вид вращения. Однако следует помнить, что вращение следует применять только в случае, если вставляемый узел нарушает упорядоченность AVL-дерева.

 

 

Рис. 12. Анализ разбалансированного AVL-дерева

Правое вращение

 

Предположим, что новый узел добавляется к поддереву R на рис. 12. В этом случае поддеревья RL и L изменяться не будут, поэтому их можно сгруппировать в один треугольник, как показано на рис. 13. Новый узел был добавлен к дереву Т₁, при этом поддерево Т_A с корнем в узле А становится по крайней мере на два уровня длиннее, чем поддерево Т₃.[11] Механизм правого вращения представлен на рис. 13. Это вращение называется правым, поскольку узлы А и X сдвигаются на одну позицию вправо.

 

Рис. 13. Механизм правого вращения AVL-деревьев

 

После добавления узла и применения правого вращения глубина поддерева не увеличивается. Любая часть дерева, лежащая выше узла X, при этом остается сбалансированной, поэтому дальнейшая балансировка не нужна.

Левое вращение

Левое вращение аналогично правому. Оно используется с целью перебалансировки дерева, когда новый узел добавляется к поддереву L, показанному на рис. 12. На рис. 14. изображено AVL-дерево до и после левого вращения.

 

Рис. 14. Механизм левого вращения AVL-деревьев

Вращение влево-вправо

Когда узел добавляется в поддерево LR (см. рис. 12), необходимо рассмотреть еще один нижележащий уровень. На рис. 15 показано дерево, в котором новый узел вставляется в левую часть Т₂ поддерева LR. В данном случае поддеревья Т_А и Т_С удовлетворяют свойству AVL, а поддерево Т_X - нет.

 

 

Рис. 15. Механизм вращения AVL-деревьев влево-вправо

 

Перебалансировка деревьев по принципу влево-вправо показана на рис. 15. Данный случай называется вращением влево-вправо, потому что узлы А и С сдвигаются на одну позицию влево, а узлы С и X - на одну позицию вправо.

 

Вращение вправо-влево

Вращение вправо-влево аналогично вращению влево-вправо. Оно используется для балансировки дерева после вставки узла в поддерево RL, изображенное на рис. 12. На рис. 16 показано AVL-дерево до и после вращения вправо-влево.

 

Рис. 16. Механизм вращения AVL-деревьев вправо-влево