На этом шаге мы рассмотрим первый алгоритм поворота.

    На этом и следующем шагах мы приведем алгоритмы однократных поворотов, проиллюстрируем их конкретными примерами и в конце следующего шага сформулируем общее правило их использования.

    Итак, приведем текст алгоритма:

    p1 = (*p).Left;
    (*p).Left = (*p1).Right; (*p1).Right = p;
    (*p).bal = 0; p = p1;

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

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

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

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

1. Определяем адрес той вершины, которая станет корнем дерева:

       p1 = (*p).Left;
   

   
   Рис.2. Сохранение адреса нового корня дерева

2. Переприкрепляем правое поддерево от "нового" корня, делая это поддерево левым поддеревом "старого" корня:

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

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

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

       (*p1).Right = p;
   

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

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

       (*p).bal = 0; p = p1;
   

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

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

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

    На следующем шаге мы разберем однократный RR-поворот.

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