Оба типа больших вращений являются комбинацией малых вращений (право-левым или лево-правым вращением).

Если добавление нового узла, приводящее к разбалансировке, происходит в левое поддерево левого сына опорного узла или в правое поддерево правого сына опорного узла, т.е. если стороны сына и внука опорного узла одноименны, то необходимо произвести одинарный поворот. Если добавление происходит в правое поддерево левого сына опорного узла или в левое поддерево правого сына опорного узла, т.е. стороны разноименны, то необходимо произвести двойной поворот.

- добавление в левое поддерево левого сына опорного узла – правый (R);

- добавление в правое поддерево левого сына опорного узла – левый-правый (LR);

- добавление в левое поддерево правого сына опорного узла – правый-левый (RL);

- добавление в правое поддерево правого поддерева сына опорного узла – левый (L).

Простой поворот вправо (влево) производит следующую трансформацию дерева:

Рассмотрим теперь ситуацию дисбаланса, когда высота правого поддерева узла p на 2 больше высоты левого поддерева (обратный случай является симметричным и реализуется аналогично). Пусть q — правый дочерний узел узла p, а s — левый дочерний узел узла q.

Анализ возможных случаев в рамках данной ситуации показывает, что для исправления разбалансировки в узле p достаточно выполнить либо простой поворот влево вокруг p, либо так называемый большой поворот влево вокруг того же p. Простой поворот выполняется при условии, что высота левого поддерева узла q больше высоты его правого поддерева: h(s)≤h(D).

Большой поворот применяется при условии h(s)>h(D) и сводится в данном случае к двум простым — сначала правый поворот вокруг q и затем левый вокруг p.

Удаление узла из АВЛ-дерева

Непосредственно удаление узла из АВЛ-дерева происходит так же, как и удаление узла из обычного двоичного дерева поиска. Если у узла менее двух сыновей, то удаляется сам узел, а если два сына, то удаляемым узлом становится его последователь, информация (ключ) из которого предварительно переписывается в удаляемый узел. Чтобы после удаления сохранились свойства АВЛ- дерева, возможно, понадобится выполнить балансировку. Для этого надо подниматься вверх по пути от удаленного узла к корню и проверять в этих узлах баланс. Если в узле баланс нарушен, то надо выполнить соответствующий поворот – одинарный или двойной. Остановить просмотр можно на том узле, в котором показатель баланса не поменялся. Это означает, что высота его поддерева, левого или правого, в котором производилось удаление, не изменилась. При балансировке после удаления используются те же виды поворотов, что и после вставки узла в дерево.

1. Левое поддерево стало ниже правого на 2 уровня.

a. У правого сына (B) высота правого поддерева больше, либо равна высоте левого поддерева (height(T3) ≥ height(T2)), необходимо произвести левый поворот (L): опорный узел (A) поворачивается налево относительно своего правого сына (B).

b. У правого сына (C) высота правого поддерева меньше вы- соты левого поддерева (height(T4) < height(B)). Необходимо произвести двойной поворот — направо, потом налево (RL): сначала правый сын опорного узла (C) поворачивается направо относительно своего левого сына (B), а затем опорный узел (A) поворачивается налево относительно своего нового правого сына (B).

Левое поддерево короче правого и (а) height(T3) > height(T2); (б) height(T3) = height(T2). Балансировка: левый поворот

2. Правое поддерево стало ниже левого на 2 уровня (случай, симметричный случаю 1).

a. У левого сына высота левого поддерева больше, либо равна высоте правого поддерева. Случай, симметричный случаю 1а.

b. У левого сына высота левого поддерева меньше высоты правого поддерева. Случай, симметричный случаю 1b

Правила удаления такие же, как при вставке: если самые глубокие узлы находятся справа или слева, то производится одинарный поворот опорного узла в противоположную сторону, а если они находятся посередине, то производится двойной поворот.