平衡的意义
之前学习了二叉搜索树, 知道这种结构基于折半的原理, 在查找的时候效率很高, 理想的情况下时间复杂度为 O(log n) , 那不理想的情况又是怎样的呢? 举个例子, 根据二叉搜索树的特性, 插入 { 6,5,4,3,2,1 } 这组数据, 最终生成的二叉树如下:
要判断这棵树中是否存在 1 . 1 处在这棵树的最底部, 并且这个棵树呈现出一边倒的形状, 导致找 1 时遍历了所有的节点, 这种情况下时间复杂度为 O(n) . 可见一旦二叉搜索树失去了平衡也就失去了效率, 理想的二叉搜索树, 是树的节点 "均匀" 分布在根节点两侧, 才能满足时间复杂度 O(log n) .
平衡的定义
怎样才算 "均匀" 分布呢? 对于树中的节点, 不能只让左或右孩子独得恩宠, 雨露均沾才是王道. Wikipedia https://en.wikipedia.org/wiki/AVL_tree 给出了定义:
二叉搜索树中, 对于任意节点, 右子树与左子树高度差不超过 1 , 则认为这棵树是平衡的.
这个定义有个官方的名字 平衡因子(Balance factor), 平衡因子只可能是「1,0,-1」, 注意是右子树的高度 - 左子树的高度. 有了这个规定, 失衡的现象就能有所缓解了. 俗话说不患贫而患不均, 虽然「1,-1」目前是可接受的, 却为将来的失衡埋下伏笔. 这种导致失衡的隐患 Wikipedia https://en.wikipedia.org/wiki/AVL_tree 给出了定义:
平衡因子为 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 左重
树的旋转
"症状" 有了, 就需要对症下药了. 正常的思路是, 哪边高了就降低其高度, 但是要注意二叉搜索树中的节点是有顺序的(左<中<右), 如何降低高度也是有讲究的. 这里就引入一个很重要的操作 -- 旋转, 旋转 https://en.wikipedia.org/wiki/Tree_rotation 能满足只改变树的结构, 又符合节点的排列顺序. 你可能在很多地方看到, 为了保证树的平衡, 会有左旋或右旋的操作, 这里的左旋, 右旋具体指的又是啥? Wikipedia https://en.wikipedia.org/wiki/AVL_tree 上的介绍
当说到旋转时, 是指对某个节点旋转(上图对 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
- 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 -☺
来源: https://juejin.im/post/5c6782d5e51d457f7b6c3d55