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

Вначале предположим, что новый узел вставляется в поддерево R на рис. 7.4. В этом случае не нужно изменять два правых поддерева узла X, поэтому их можно объединить, изобразив одним треугольником, как показано на рис. 7.5. Новый узел вставляется в дерево T₁, при этом поддерево T_A с корнем в узле A становится не менее, чем на два уровня выше, чем поддерево T₃.

На самом деле, поскольку до вставки нового узла дерево было АВЛ‑деревом, то T_A должно было быть выше поддерева T3 не больше, чем на один уровень. После вставки одного узла T_A должно быть выше поддерева T₃ ровно на два уровня.

Также известно, что поддерево T₁ выше поддерева T₂ не больше, чем на один уровень. Иначе узел X не был бы самым нижним узлом с несбалансированными поддеревьями. Если бы T₁ было на два уровня выше, чем T₂, то дерево было бы несбалансированным в узле A.

@Рис. 7.4. Анализ несбалансированного АВЛ‑дерева

========158

@Рис. 7.5. Вставка нового узла в поддерево R

В этом случае, можно переупорядочить узлы при помощи правого вращения (right rotation), как показано на рис. 7.6. Это вращение называется правым, так как узлы A и X как бы вращаются вправо.

Заметим, что это вращение сохраняет порядок «меньше» расположения узлов дерева. При симметричном обходе любого из таких деревьев обращение ко всем поддеревьям и узлам дерева происходит в порядке T₁, A, T₂, X, T₃. Поскольку симметричный обход обоих деревьев происходит одинаково, то и порядок расположения элементов в них будет одинаковым.

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

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

Левое вращение (left rotation) выполняется аналогично правому. Оно используется, если новый узел вставляется в поддерево L, показанное на рис. 7.4. На рис. 7.7 показано АВЛ‑дерево до и после левого вращения.

@Рис. 7.6. Правое вращение

========159

@Рис. 7.7. До и после левого вращения

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

Если узел вставляется в поддерево LR, показанное на рис. 7.4, нужно рассмотреть еще один нижележащий уровень. На рис. 7.8. показано дерево, в котором новый узел вставляется в левую часть T₂ поддерева LR. Так же легко можно вставить узел в правое поддерево T₃. В обоих случаях, поддеревья T_A и T_C останутся АВЛ‑поддеревьями, но поддерево T_X уже не будет таковым.

Так как дерево до вставки узла было АВЛ‑деревом, то T_A было выше T₄ не больше, чем на один уровень. Поскольку добавлен только один узел, то T_A вырастет только на один уровень. Это значит, что T_A теперь будет точно на два уровня выше T₄.

Также известно, что поддерево T₂ не более, чем на один уровень выше, чем T₃. Иначе T_C не было бы сбалансированным, и узел X не был бы самым нижним в дереве узлом с несбалансированными поддеревьями.

Поддерево T₁ должно иметь ту же глубину, что и T₃. Если бы оно было короче, то поддерево T_A было бы не сбалансировано, что снова противоречит предположению о том, что узел X — самый нижний узел в дереве, имеющий несбалансированные поддеревья. Если бы поддерево T₁ имело большую глубину, чем T₃, то глубина поддерева T₁ была бы на 2 уровня больше, чем глубина поддерева T₄. В этом случае дерево было бы несбалансированным до вставки в него нового узла.

Все это означает, что нижние части деревьев выглядят в точности так, как показано на рис. 7.8. Поддерево T₂ имеет наибольшую глубину, глубина T₁ и T₃ на один уровень меньше, а T₄ расположено еще на один уровень выше, чем T₃ и T₃.

@Рис. 7.8. Вставка нового узла в поддерево LR

==========160

@Рис. 7.9. Вращение влево‑вправо

Используя эти факты, можно сбалансировать дерево, как показано на рис. 7.9. Это называется вращением влево‑вправо (left‑right rotation), так как при этом вначале узлы A и C как бы вращаются влево, а затем узлы C и X вращаются вправо.

Как и другие вращения, вращение этого типа не изменяет порядок элементов в дереве. При симметричном обходе дерева до и после вращения обращение к узлам и поддеревьям происходит в порядке: T₁, A, T₂, C, T₃, X, T₄.

Высота дерево после балансировки также не меняется. До вставки нового узла, правое поддерево имело высоту поддерева T₁ плюс 2. После балансировки дерева, высота этого поддерева снова будет равна высоте T₁ плюс 2. Это значит, что остальная часть дерева также остается сбалансированной, и нет необходимости продолжать балансировку дальше.