在上文（《细谈二叉搜索树》）中我们提到了二叉搜索树的一个缺陷——退化，在本文中，我们将讨论如何解决这个问题。
使树的高度尽可能的低其实就是维护树的平衡（让树尽可能的平衡），维护树的平衡的方法有很多，比如Treap、Splay、WBLT等等，今天我们不讨论具体树的实现，只讲解如何通过旋转维持树的平衡。
平衡：
如果一棵树的左子树和右子树的树高之差的绝对值不大于1，那么我们称这棵树使是平衡的。
左旋
现在我们以ES为轴进行左旋：
旋转步骤：
- 将
S设置为树的根节点 - 让
E（原根节点）成为S的左子树 - 让
S的左子树Left(S)（如果有的话）成为E的右子树
证明
由二叉搜索树的性质我们可以知道：
Left(E) < E < Left(S) < S < Right(S)- 如果
E有父节点：- 如果
E是其父节点的左子树：E < S < Fat - 如果
E是其父节点的右子树：Fat < E < S
- 如果
易得：旋转后不破坏二叉搜索树的性质。
右旋
接下来，我们再以ES为轴进行右旋：
旋转步骤：
- 将
E设置为根节点 - 让
S（原父节点）成为E的右子树 - 让
E的右子树Right(E)（如果有的话）成为S的左子树
证明
由二叉搜索树的性质我们可以知道：
Left(E) < E < Right(E) < S < Right(S)- 如果
S有父节点：- 如果
S是父节点的左子树：E < S < Fat - 如果
S是父节点的右子树：Fat < E < S
- 如果
易得：旋转后不破坏二叉搜索树的性质。
说明
现在，我们已经知道了如何旋转，但是我们为什么要进行旋转呢？
观察旋转的过程我们不难得知，左旋会使左侧树高加一，右侧减一；右旋会使右侧树高加一，左侧减一。
所以，当树不平衡时，我们只需要旋转树中特定的区域就可以使树变得平衡。
弱平衡树
现在，让我们动手实现一个弱平衡的二叉搜索树（以下简称平衡二叉搜索树）。平衡二叉搜索树的查找过程与普通的二叉树相同就不再赘述。
插入&修复
平衡二叉搜索树先进行与普通二叉搜索树相同的插入过程，不过其插入后多了一个操作：“修复”。
所谓的修复就是维护二叉树平衡的过程，接下来我们来看如何通过旋转维护树的平衡。
假设我们已经有了一个如图所示的二叉搜索树：
因为接下来东西会非常多，所以使用分栏展示，目前没有其它合适的控件可以用，还请谅解
图中的[N]是占位符，无视即可
graph TD
5((5)) --- 3((3)) & 8((8))
3 --- 1((1)) & 4((4))
8 --- 7((7)) & N0[N]
现在让我们添加一个新的节点进去（add 6）：
graph TD
5((5)) --- 3((3)) & 8((8))
3 --- 1((1)) & 4((4))
8 --- 7((7)) & N0[N]
7 --- 6((6)) & N1[N]
很显然，根节点的右子树因为插入操作而变得平衡偏左，我们要通过右旋使其平衡向右移动：
graph TD
5((5)) --- 3((3)) & 7((7))
3 --- 1((1)) & 4((4))
7 --- 6((6)) & 8((8))
这样，我们就完成了修复。
graph TD
5((5)) --- 3((3)) & 6((6))
3 --- 1((1)) & 4((4))
6 --- N0[N] & 7((7))
现在让我们添加一个新的节点进去（add 8）：
graph TD
5((5)) --- 3((3)) & 6((6))
3 --- 1((1)) & 4((4))
6 --- N0[N] & 7((7))
7 --- N1[N] & 8((8))
N0 --- N2[N]
很明显，根节点的右子树失去了平衡且其平衡偏右，所以我们以6-7为轴进行一次左旋：
graph TD
5((5)) --- 3((3)) & 7((7))
3 --- 1((1)) & 4((4))
7 --- 6((6)) & 8((8))
此时我们就成功完成了修复。
graph TD
5((5)) --- 3((3)) & 8((8))
3 --- 1((1)) & 4((4))
8 --- 6((6)) & N0[N]
现在让我们添加一个新的节点进去（add 7）：
graph TD
5((5)) --- 3((3)) & 8((8))
3 --- 1((1)) & 4((4))
8 --- 6((6)) & N0[N]
6 --- N1[N] & 7((7))
很明显，现在这颗平衡树出现了“失衡的现象”，那么我们如何恢复树的平衡呢？
按照上面所说的右旋会使树重心向右移动，看起来我们应当以6-8为轴进行右旋，但是如果我们这么进行旋转树就会变成下面这个样子：
graph TD
5((5)) --- 3((3)) & 6((6))
3 --- 1((1)) & 4((4))
6 --- N0[N] & 8((8))
8 --- 7((7)) & N1[N]
N0 --- N2[N]
很显然树（5的右子树）并没有平衡，只是从重心偏左变成了重心偏右。
所以我们要先把以6为根的树的平衡调整为偏左，所以要先以6-7为轴进行一次左旋：
graph TD
5((5)) --- 3((3)) & 8((8))
3 --- 1((1)) & 4((4))
8 --- 7((7)) & N0[N]
7 --- 6((6)) & N1[N]
接下来，我们要以7-8为轴进行一次右旋：
graph TD
5((5)) --- 3((3)) & 7((7))
3 --- 1((1)) & 4((4))
7 --- 6((6)) & 8((8))
这样子，树就恢复了平衡。
graph TD
5((5)) --- 3((3)) & 6((6))
3 --- 1((1)) & 4((4))
6 --- N0[N] & 8((8))
现在我们插入一个新的节点（add 7）：
graph TD
5((5)) --- 3((3)) & 6((6))
3 --- 1((1)) & 4((4))
6 --- N0[N] & 8((8))
8 --- 7((7)) & N1[N]
N0 --- N2[N]
此时根节点的右子树平衡偏右，按照上文所说，我们需要左旋：
graph TD
5((5)) --- 3((3)) & 8((8))
3 --- 1((1)) & 4((4))
8 --- 6((6)) & N1[N]
6 --- N0[N] & 7((7))
但是和上文中“左侧双旋”情况一样，我们没有成功的恢复树的平衡。
我们应当先以7-8为轴进行右旋，将6的右子树调整为重心偏右：
graph TD
5((5)) --- 3((3)) & 6((6))
3 --- 1((1)) & 4((4))
6 --- N0[N] & 7((7))
7 --- N1[N] & 8((8))
N0 --- N2[N]
然后再以6-7为轴进行左旋：
graph TD
5((5)) --- 3((3)) & 7((7))
3 --- 1((1)) & 4((4))
7 --- 6((6)) & 8((8))
这样，我们就成功修复了树的平衡。
规律总结
经过上面的论述，我们不难发现一个规律：
- 如果新节点插入较高左子树的左侧：我们需要进行左侧单旋
- 如果新节点插入较高左子树的右侧：我们需要进行左侧双旋
- 如果新节点插入较高右子树的右侧：我们需要进行右侧单旋
- 如果新节点插入较高右子树的左侧：我们需要进行右侧双旋
- 其它情况：树依然是平衡的，不需要修复
删除&修复
平衡二叉搜索树进行删除时，首先与普通二叉搜索树一样进行节点删除，然后再以被替换的节点的原父节点为根进行平衡修复即可。
“弱”在哪里
为什么我们说这是一颗弱平衡的二叉搜索树呢？因为按照上述方法维护出来的二叉树一定满足局部平衡但却不一定总体平衡。
假如我们按照如下顺序插入节点：5 -> 8 -> 3 -> 1 -> 4 -> 2，那么我们就会得到下面这样子的树：
graph TD
5((5)) --- 3((3)) & 8((8))
3 --- 1((1)) & 4((4))
1 --- N[N] & 2((2))
可以很明显的发现，这棵树总体上已经失去了平衡。
强平衡树
对于上面弱平衡树的情况，有什么方法可以解决吗？
我们先来分析以下出现“失衡”的原因是什么，很明显，是在进行插入或删除时我们只修复了局部的平衡。修复局部平衡是有可能改变树的高度的，这时候如果这个局部不包含树的根节点，那么就有可能导致左右两个子树的高之差大于1。
明白了原因就好解决问题了，我们只需要在维护某一颗子树的平衡后继续向父节点方向判断并维护平衡即可。
尾注
本文参考了下列资料（没有先后顺序）：
本文使用了下列工具（没有先后顺序）：