Сначала предположим, что новый узел добавляется к поддереву R на рис. 7.4.
В этом случае два правых поддерева узла X изменяться не будут, поэтому их мож-
но сгруппировать в один треугольник, как показано на рис. 7.5. Новый узел был
добавлен к дереву Т1, при этом поддерево ТА с корнем в узле А становится по край-
ней мере на два уровня длиннее, чем поддерево Т3.
Так как дерево перед добавлением узла было AVL-деревом, ТА должно быть мак-
симум на один уровень длиннее поддерева Т3. Вы добавили всего один узел к дереву,
поэтому ТА должно быть ровно на два уровня выше, чем поддерево Т3.
Также известно, что поддерево Т1, не более чем на один уровень выше поддере-
ва Т2. В противном случае узел X не был бы самым низким узлом в дереве с разба-
лансированными поддеревьями. Если бы поддерево Т1, было на два уровня выше
Т2, дерево было бы разбалансировано в узле А.
Вы можете поменять узлы местами с помощью правого вращения (right rotation),
как показано на рис. 7.6. Это вращение называется правым, поскольку узлы А и X
как бы сдвинуты на одну позицию вправо.
Рис. 7.5. Добавление нового узла в поддерево R
Рис. 7.6. Правое вращение
Обратите внимание, что это вращение сохраняет порядок расположения эле-
ментов дерева «меньше чем».Симметричный обход любого из этих деревьев про-
исходит таким образом: Т1, А, Т2, X, Т3.
Поскольку обход обоих деревьев происходит одинаково, то и порядок распо-
ложения элементов в них будет идентичным.
Также необходимо обратить внимание, что глубина поддерева, с которым вы
работаете, осталась той же самой. Перед добавлением нового узла глубина подде-
рева была равна глубине поддерева Т2 плюс 2. После добавления узла и примене-
ния правого вращения глубина поддерева не увеличивается. Любая часть дерева,
лежащая выше узла X, при этом остается сбалансированной, поэтому дальнейшая
балансировка не нужна.
AVL-деревья
Добавление узлов к AVL-дереву
Вращение AVL-деревьев для добавления узла
Правое вращение
Левое вращение
Вращение влево-вправо
Вращение вправо-влево