При вставке узла в AVL-дерево в зависимости от того, в какую часть дерева до-
бавляется узел, существует четыре варианта балансировки. Методы перебаланси-
рования называются правым и левым вращением, вращением влево-вправо и впра-
во-влево. Сокращено они обозначаются R, L, LR и RL.
Предположим, что вы добавляете новый узел к AVL-
дереву и оно теперь разбалансировано в узле X, как по-
казано на рис. 7.4. На рисунке изображены только узел X
и два его дочерних узла, остальные части дерева обозначе-
ны треугольниками, так как нет необходимости их рассмат-
ривать.
Новый узел может быть вставлен в любое из этих че-
тырех поддеревьев, изображенных в виде треугольников
ниже узла X. Когда вы помещаете новый узел в один из
этих треугольников, необходимо использовать соответ-
ствующий сдвиг для перебалансирования дерева. Но если
вставка нового узла не нарушает упорядоченность дере-
ва, балансировка не нужна.
Рис. 7.4. Анализ разбалансированного AVL-дерева
AVL-деревья
Добавление узлов к AVL-дереву
Вращение AVL-деревьев для добавления узла
Правое вращение
Левое вращение
Вращение влево-вправо
Вращение вправо-влево
Вращение влево-вправо
Вращение вправо-влево