AVL Tree

AVL Tree


2019-01-21

平衡的意义

之前学习了二叉搜索树,知道这种结构基于折半的原理,在查找的时候效率很高,理想的情况下时间复杂度为 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. Adelson-Velsky 和 Evgenii Landis,名字不重要,功能才重要,它能在失衡的情况下通过旋转重新实现平衡,因此它的时间复杂度为 O(\log{n}) 。上面介绍了 4 种失衡的情况,现在分别介绍 AVL 树是如何做到重新平衡的:

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

1
2
3
4
5
    9
/ \
7 10
/ \
6 8

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

1
2
3
4
5
         9(-1)
/ \
7(0) 10(0)
/ \
6(0) 8(0)

插入 3 后:

1
2
3
4
5
6
7
          9(-1?)
/ \
7 (0?) 10(0)
/ \
6(-1) 8(0)
/
3(0)

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

1
2
3
4
5
6
7
          9(-1?)
/ \
7(-1) 10(0)
/ \
6(-1) 8(0)
/
3(0)

最后,相应的 9 的平衡因子也变了:

1
2
3
4
5
6
7
          9(-2)
/ \
7(-1) 10(0)
/ \
6(-1) 8(0)
/
3(0)

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

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

1
2
3
4
5
  8
/ \
7 10
/ \
9 11

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

1
2
3
4
5
    8 (+1)
/ \
7(0) 10(0)
/ \
9(0) 11(0)

插入 12 后,直接跳到最后一步:

1
2
3
4
5
6
7
    8(+2)
/ \
7(0) 10(+1)
/ \
9(0) 11(+1)
\
12(0)

这种右重的情况左旋后可以达到平衡,找到负载因子为 +2 的节点(8)左旋:

LR(左右):假设要在下面这棵树中插入 9

1
2
3
  10
/
7

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

1
2
3
   10(-1)
/
7(0)

插入 9 后,直接跳到最后一步:

1
2
3
4
5
   10(-2)
/
7(+1)
\
9(0)

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

1
2
3
4
5
 7(+2)
\
10(-1)
/
9(0)

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

1
2
3
4
5
   10                              10                                9
/ / / \
7 (将 7 左旋) ---> 9 (将 10 右旋) ---> 7 10
\ /
9 7

RL(右左):假设要在下面这棵树中插入 9

1
2
3
8
\
10

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

1
2
3
8(+1)
\
10(0)

插入 9 后,直接跳到最后一步:

1
2
3
4
5
8(+2)
\
10(-1)
/
9(0)

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

1
2
3
4
5
8                                8                                9
\ \ / \
10 (将 10 右旋) ---> 9 (将 8 左旋) ---> 8 10
/ \
9 10

Enjoy –☺