为什么教科书中的八卦树与我的八卦树不同？

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的根没有平衡。

在Mark Allen Weiss撰写的C ++数据结构和算法分析（第4版）中，第162页，图4.50，该书描述了如何在仅剩下左孩子的情况下展开树的最左孩子...

Answer 1

这通常是“ Zig-zig”的情况，直到向上，所以每次对节点的祖父母进行右旋转，然后对父节点进行右旋转。