相对友好的 AVL Tree 教程

之前学习了二叉搜索树，知道这种结构基于折半的原理，在查找的时候效率很高，理想的情况下时间复杂度为 O(log n) ，那不理想的情况又是怎样的呢？举个例子，根据二叉搜索树的特性，插入 { 6，5，4，3，2，1 } 这组数据，最终生成的二叉树如下：

要判断这棵树中是否存在 1 。 1 处在这棵树的最底部，并且这个棵树呈现出一边倒的形状，导致找 1 时遍历了所有的节点，这种情况下时间复杂度为 O(n) 。可见一旦二叉搜索树失去了平衡也就失去了效率，理想的二叉搜索树，是树的节点“均匀”分布在根节点两侧，才能满足时间复杂度 O(log n) 。

平衡的定义

怎样才算“均匀”分布呢？对于树中的节点，不能只让左或右孩子独得恩宠，雨露均沾才是王道。Wikipedia 给出了定义：

二叉搜索树中，对于任意节点， 右 子树与 左 子树高度差不超过 1 ，则认为这棵树是平衡的。

这个定义有个官方的名字 平衡因子 （Balance factor），平衡因子只可能是「1，0，-1」， 注意是右子树的高度 - 左子树的高度 。有了这个规定，失衡的现象就能有所缓解了。俗话说不患贫而患不均，虽然「1，-1」目前是可接受的，却为将来的失衡埋下伏笔。这种导致失衡的隐患Wikipedia 给出了定义：

平衡因子为 1 则该节点 右重（right-heavy） ，平衡因子为 -1 则该节点 左重（left-heavy）

4 种失衡

上面说到可能导致失衡的隐患，分别是右重和左重。你可能在很多地方看到 LL（左左）、RR（右右）、LR（左右）、RL（右左） ，搞得跟秘籍键似的这 TM 到底指的是啥？其实就是下面的 4 种失衡情况：

LL（左左）：2 是 3 的 左 子树，2 左 重；

RR（右右）：2 是 1 的 右 子树，2 右 重

LR（左右）：1 是 3 的 左 子树，1 右 重

RL（右左）：3 是 1 的 右 子树，3 左 重

树的旋转

“症状”有了，就需要对症下药了。正常的思路是，哪边高了就降低其高度，但是要注意二叉搜索树中的节点是有顺序的（左<中<右），如何降低高度也是有讲究的。这里就引入一个很重要的操作—— 旋转 ，旋转能满足只改变树的结构，又符合节点的排列顺序。你可能在很多地方看到，为了保证树的平衡，会有左旋或右旋的操作，这里的左旋、右旋具体指的又是啥？Wikipedia 上的介绍

当说到旋转时，是指对某个节点旋转（上图对 Q 右旋，对 P 左旋），仔细观察发现， 右旋使得 Q 的左孩子 P 取代了自己原来的位置，左旋使得 P 的右孩子 Q 取代了自己原来的位置 ，记住这一点很重要哈。

上面动图直观的感受就是 右旋后右子树高度升高，左子树高度降低；左旋后左子树升高，右子树高度降低； 除此之外，旋转的过程中也涉及到节点的交换

从上图可以看到，当简单地说右旋，其实展开来说是指：

• 根节点 5 右旋，首先将左子树 3 的右孩子 4 作为此时根节点 5 的左孩子；
• 再将 5 这棵树作为新根节点 3 的右子树；

左旋反之；因为这样很啰嗦，平时不会这么说，但这背后的原理得知道。此外旋转后节点还是符合大小排列顺序，这正是我们所希望的。

AVL 树

说了半天，这 AVL 树是个啥？这个有点“黄”的名字来源于它的发明者 G. M. A delson- V elsky 和 Evgenii L andis，名字不重要，功能才重要，它能在失衡的情况下通过旋转重新实现平衡，因此它的时间复杂度为 O(log n)。上面介绍了 4 种失衡的情况，现在分别介绍 AVL 树是如何做到重新平衡的：

LL（左左）: 假设要在下面这棵树中插入 3

9
     / \
    7   10
   / \
  6   8
复制代码

首先要做的是先确定各个节点的平衡因子：

9(-1)
         /       \
       7(0)      10(0)
      / \
  6(0)   8(0)
复制代码

插入 3 后：

9(-1?)
          /      \
        7 (0?)   10(0)
       /   \
   6(-1)   8(0)
   /
 3(0)
复制代码

注意这里对可能影响到的路径后面加了个 ？，是因为此时他们的平衡因子还不确定，需要重新计算，由于 7 的左子树高度加 1 ，7 的平衡因子也变了：

9(-1?)
          /      \
        7(-1)    10(0)
       /   \
   6(-1)   8(0)
   /
 3(0)
复制代码

最后，相应的 9 的平衡因子也变了：

9(-2)
          /      \
        7(-1)    10(0)
       /   \
   6(-1)   8(0)
   /
 3(0)
复制代码

根据上面学的内容，这种左重的情况右旋后可以达到平衡，找到负载因子为 -2 的节点（9）右旋，剩下的就是上面已经介绍过的，节点交换什么的。如下：

RR（右右）: 假设要在下面这棵树种插入 12

8
     / \
    7   10
        / \
       9   11
复制代码

先确定各个节点的平衡因子：

8 (+1)
         /       \
       7(0)      10(0)
                  / \
               9(0)  11(0)
复制代码

插入 12 后，直接跳到最后一步：

8(+2)
         /       \
       7(0)      10(+1)
                  / \
               9(0)  11(+1)
                       \
                       12(0)
复制代码

这种右重的情况左旋后可以达到平衡，找到负载因子为 +2 的节点（8）左旋：

LR（左右）：假设要在下面这棵树中插入 9

10
     / 
    7   
复制代码

先确定各个节点的平衡因子：

10(-1)
         /       
       7(0)    
复制代码

插入 9 后，直接跳到最后一步：

10(-2)
         /      
       7(+1)    
        \         
        9(0)
复制代码

按照之前的套路，这种左重的情况需要右旋，找到负载因子为 -2 的节点（10）右旋，结果咋样呢？

7(+2)
           \     
           10(-1)    
           /    
         9(0)
复制代码

发现套路不好使了，这里就要用到两次旋转，第一次将旋转将 LR（左右）变成熟悉的 LL（左左），第二次旋转就可以用之前的套路了

10                              10                                9
         /                               /                                 /  \ 
       7          (将 7 左旋) --->       9          (将 10 右旋) --->       7   10 
        \                              /
        9                             7
复制代码

RL（右左）：假设要在下面这棵树中插入 9

8
        \  
         10  
复制代码

先确定各个节点的平衡因子：

8(+1)
        \  
         10(0)  
复制代码

插入 9 后，直接跳到最后一步：

8(+2)
        \  
         10(-1)  
         /
        9(0)
复制代码

同样要用到两次旋转，第一次将旋转将RL（右左）变成熟悉的 RR（右右），第二次旋转就可以用之前的套路了

8                                8                                9
        \                               \                              /  \
         10       (将 10 右旋) --->        9       (将 8 左旋) --->     8    10
         /                                 \ 
        9                                   10
复制代码

Enjoy –☺