На этом шаге мы рассмотрим еще один двухкратный поворот.

    Этот алгоритм ничем не отличается от рассмотренного на предыдущем шаге, только поворот осуществляется в другую сторону.

    Приведем текст алгоритма:

    p1 =(*p).Right;  p2 = (*p1).Left; 
    (*p1).Left = (*p2). Right; (*p2). Right = p1;
    (*p).Right = (*p2). Left; (*p2). Left = *p;
    p = p2; 

    Рассмотрим его использование на конкретном примере.

    Пусть дано следующее дерево:

Рис.1. Исходное дерево

    Иллюстрируем алгоритм с помощью схем "до и после" Д.Кнута:

1. Определим p1 как указатель на правое поддерево, а p2 как указатель на левое поддерево дерева p1:

       p1 = (*p).Right; p2 = (*p1).Left;
   

   
   Рис.2. Определение p1 и p2

2. Переприкрепляем правое поддерево дерева p2 на место левого поддерева дерева p1:

       (*p1).Left = (*p2). Right;
   

   
   Рис.3. Переприкрепление

3. Определяем правое поддерево "нового" корня p2, как начинающееся с p1:

       (*p2). Right = p1;
   

   
   Рис.4. Определение правого поддерева "нового" корня

4. Переприкрепляем левое поддерево дерева p2 на место правого поддерева "старого" корня:

       (*p).Right = (*p2). Left;
   

   
   Рис.5. Переприкрепление

5. Определяем левое поддерево "нового" корня p2, как начинающееся со "старого" корня:

       (*p2). Left = *p;
   

   
   Рис.6. Определение правого поддерева "нового" корня

6. Изменяем значение указателя на корень дерева (p):

       p = p2;
   

   
   Рис.7. Установка начальных значений

    В результате получилось следующее сбалансированное дерево:

Рис.8. Результат балансировки

Вывод.

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

    Проиллюстрируем эту несбалансированность и ее устранение следующими рисунками:

Рис.9. Несбалансированность (отмечены узлы, вызвавшие несбалансированность)

Рис.10. Несбалансированность устранена (отмечены узлы, вызвавшие несбалансированность)

    Итак, все случаи, в которых после вставки необходима дополнительная балансировка для сохранения свойств АВЛ-дерева, ограничиваются разобранными случаями и случаями зеркального отражения этих структур.

    На следующем шаге мы разберем алгоритм построения АВЛ-дерева.

Предыдущий шаг Содержание Следующий шаг