AVL树的实现

过年在家没事，找出了几年前把我折磨得死去活来的《数据结构与算法分析》这本书。确切地说，这段时间这本书也在折磨我。

书中的 AVL 树旋转讲得不清不楚，而且使用递归实现了 AVL 树的插入与删除操作，使得本来就不太清晰的描述变得更加扑朔迷离，让我有一种想烧掉这本书的冲动。最后实在看不懂书上对 AVL 树的操作方式，只好自己从网上找一些资料实现了 AVL 树（代码在此）。另外，维基百科上有关于 AVL 树基本性质的描述，我在这里就不多介绍了。但是请勿对照那篇文章去实现 AVL 树，因为它对删除操作的描述是有问题的。关于树的旋转，维基百科的文章也没有把最根本的问题说清楚。AVL 树最难的部分就是树的旋转，本文主要讨论旋转的问题。

首先，旋转的作用是降低子树的高度。旋转的方式有两种：一种是用来降低左子树高度，通常称为右旋；另一种是用来降低右子树高度，通常称为左旋。这两种旋转在物理上是对称的，在编码上也是对称的。因此，在编码方面，只需要实现一种旋转，另一种旋转就可以依照类似的方法实现。另外，在每个节点中保存一个父节点可以大大降低编码的复杂度。

下面是左旋的具体变化过程：

      A                            B  
       \                          / \  
        B         左旋 ==>        A   C   
         \    
          C   

下面是右旋的具体变化过程:

          A                      B   
         /                      / \    
        B         右旋 ==>      C   A    
       /                            
      C   

上面的这两种情况是比较理想的情况，在实际的使用情况下是没有这么理想的。不能处理下面这些情况。

                 A                          A
                  \                        /
                   B                      B
                  /                        \
                 C	                        C

上面的这两种情况就是书上所说的双旋转问题。解决这两种情况的方法是先对 B 节点进行旋转，使 C 点与 B 点的指向方向与 A 点和 B 点相同。然后再根据 A 点进行相应方向的旋转。

     A                A                C            A              A               C
      \                \              / \          /                \             / \
       B      =>        C       =>   A   B        B       =>         C      =>   A   B
      /                  \                         \                  \
     C                    B                         C                  B
     

写到这里貌似可以去开工写代码了，但是请等等。在实际的编码中碰到如下情况还是不知道到底该怎样旋转。

        A                                  A           
         \                                /
          B                              B
         / \                            / \
        C   D                          C   D

在这两种情况下，书上的解决方法通常是“判断新插入的节点是位于左子树还是右子树”，然后再做相应的调整。这样确实能解决问题，但是在删除节点时，这种方法就无法使用。不过，我们可以根据树旋转的性质来解决这个问题。从上述问题可以看出，树旋转的最根本目的是降低树的高度。基于这个性质，我们可以进一步分析，对不平衡的子节点进行旋转。具体来说，就是“哪边更高就旋转哪边，将其高度降低一层”。如果子节点两边的高度相同，或者更高的子节点方向与父节点一致，那么就直接旋转父节点。

以上就是 AVL 树基本的旋转过程。AVL 树与二叉树的插入和删除操作基本相同，不同之处在于 AVL 树在插入和删除后需要自下而上地扫描并旋转整棵树以保持平衡。

References

• 原文链接