Почему Splay Tree в учебнике отличается от моего?

Question

В Анализ структур данных и алгоритмов в C ++ (4-е издание) , автор Mark Allen Weiss, на странице 162 на рис. 4.50, книга описывает, как в конечном итоге можно было бы растянуть самого левого дочернего элемента дерева только с левыми дочерними элементами. выглядеть так.

Где я запутался, так это то, как книга переходит с шага 2 на шаг 3. Вот шаги, выделенные на стр. 162 на рисунке 4.50:

Принимая во внимание, что мой шаг третей выглядит следующим образом:

               7                                                                                          
              /                                                  
             6                                                   
            /                                                    
           1                    
            \                                                  
             3                                                  
            / \
           2   4
                \
                 5

И мой четвертый и последний шаг подобен этому:

    1
     \
      4
     / \
    3   6
   /   / \
  2    5  7

Я не понимаю, какКнига балансирует на дереве. Для меня, когда 1 превзошел 4, нижняя часть дерева выглядела так:

  ...
 /
1
 \
  2
   \
    3
     \
      4

Моя логика заключалась в том, что корень, в котором будет иметь место баланс, будет равен 2. Тогда вы будете делать левый поворот, а днодерева будет выглядеть следующим образом:

  ...
 /
1
 \
  3
 / \
2   4

Я делаю что-то не так или я просто делаю это по-другому, но в равной степени справедливо для книги? Я также сбит с толку, потому что последнее дерево книги не сбалансировано с корнем 6, тогда как у моего корня 4 нет дисбаланса.

Answer 1

Это в основном случай "Zig-zig" до верха, поэтому каждый раз, когда вы делаете правое вращение на прародителе узла, а затем правое вращение на родителе.

Пример:

           5                                                                                          
          /                                                  
         4                                                   
        /                                                    
       3                    
      /                                                  
     2
    /
   1

Если вы хотите отобразить 1, вы поворачиваете вправо вокруг 3, а затем 2, в результате чего:

        5                                                                                          
       /                                                  
      4                                                   
     /                                                    
    1
     \
      2
       \
        3                   

Поскольку это снова случай Zig-Zig, мы поворачиваем вокруг 5, а затем 4, в результате чего:

   1
    \
     4
    / \
   2   5
    \
     3     

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