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树在插入和删除后需要由下至上扫描并旋转整棵树以保持平衡。