【STL源码剖析】二叉世界的平衡：从BST 到 AVL-tree 和 RB-tree 的插入逻辑

前言

树是计算机中最为常见的数据结构之一，底层有对文件的管理查找，上层有我们经常使用的set,map等等。树根据类型可以分为很多种，像二叉树，多叉树，满二叉树，搜索树，平衡搜索树…

本文将从普通的树的基本概念开始一直谈到经典的AVL树，红黑树的实现方法。不论之前你有没有了解过树这一数据结构，相信通过本文你将对set和map有一个清晰的理解。

大体可以划分为4个板块：

1. 树的基本概念；
2. 搜索二叉树；
3. AVL树；
4. 红黑树。

树 的导览

在介绍各种树之前，掌握树状结构的基本术语是必须的。

• 树是由节点和边组成的，最上端的节点被称为根节点root；
• 在两个相连的节点中，上面的节点被称为父节点parent，下面的节点被称为子节点child，如：A是B的父节点，E是B的子节点；
• 如果一个节点没有子节点就被称为叶子节点leaf，如：H，J，L都是叶子节点；
• 如果两个节点有相同的父节点，这两个节点就被称为兄弟节点siblings，如：上面的H和I；
• 从根节点到任意节点的路径长度，被称为深度depth；
• 根节点的深度永远是0；
• 从A能到B节点，就称B是A的子孙descendant，A是B的祖先ancestor。

搜索二叉树

基本概念

二叉树指的就是：每一个节点最多有2个子节点的树状结构。

二叉搜索树就是能够在对数时间下完成对元素的插入和查找的树状结构。

二叉搜索树中节点的放置原则：任何一个节点的值一定大于左子树，一定小于右子树。
二叉搜索树中是不允许出现重复数据的。

因此，从根一直往左走直到无路可走是，该位置就是最小元素；从跟一直往右走，直到无路可走时，就是最大元素。

搜索二叉树的找最大值和最小值是比较简单的，关键是如何向一颗搜索二叉树中插入元素和删除元素，如何保证插入元素之后依旧是一颗搜索二叉树，以及删除元素时应该如何调整。

插入元素

插入元素之前首先要找到该元素和合法位置，可以从根节点出发，遇到比插入元素大的就向左节点走，遇到比插入元素小的就向右移，直到移动到尾端停止，该位置就是新元素的合法位置。

示意图如下：

删除元素

删除元素分为三种情况，假设欲删除旧节点A：

1. 先找到A的位置，如果A节点没有子节点就直接删除；
2. 如果A节点有一个子节点，就直接将子节点连接到父节点上；
3. 如果A节点有两个子节点，就用右树的最小节点取代A；

示意图如下：

细节，如果只有一个子节点就直接将子节点与父节点相连再释放目标节点，如果有两个子节点就将右树的最小值赋给删除节点位置，再将右树的最小位置节点释放。

平衡二叉搜索树

普通的二叉搜索树在插入的时候可能会出现一些极端情况，可能会出现形成的二叉搜索树每个位置都只有一个节点，那么此时的树状结构，不就是链表嘛，这就会导致查找的时间从O(logN)提升到O(N)，比如下图：

因此在插入的时候我们就需要采取一定的措施让这棵树整体呈现平衡的状态，不会出现后面这种头重脚轻的情况。因此为了防止这一情况，平衡二叉树的使用是必须的。下面介绍两种最经典的平衡儿二叉搜索树：AVL树和红黑树。

AVL-tree

AVL tree 是一个"加上了额外平衡条件"的二叉搜索树。AVL tree 新增了一个平衡因子的概念，要求每个节点的左右子树的高度差最多是1，并没有要求完全相等。

如果因为一个新节点的插入，导致原来节点的左右子树之差大于1了，就需要对这颗树进行调整。
如下图：

此时平衡二叉树的结构就被破坏了，如果想要将其恢复成一个平衡二叉树，就需要向上找到最深的哪一个，即上图的18节点，将这个位置进行调整后这颗树又可以恢复平衡。调整的方式也很多种，对于不同情况需要使用不同的方案来调整，假设平衡破环中最深的节点是X，情况大致可以分为四种：

1. 插入节点在左节点的左子树 —— 左左；
2. 插入节点在左节点的右子树 —— 左右；
3. 插入节点在右节点的右子树 —— 右右；
4. 插入节点在右节点的左子树 —— 左右；
   

情况1，4被称为外侧插入，采用单旋转操作就可以解决；情况2，3被称为内测插入，需要采用双旋才能解决。

下面介绍一单旋和多选：

单旋转

单旋的情况必定是上图所示的样子，其中A，B，C表示三颗子树，A比B高度大1，B比C高度大1；

反证：

1. 如果A和B高度一样大，在没插入11之前，k2节点就已经不满足平衡二叉树的条件了，所以不可能；
2. 如果B和C的高度一样，那么k1节点会先不满足条件，不会选择调整k2，所以也不可能；

综上所述：要被更新的节点情况如上。

调整：为了调整平衡状态，我们希望将 A子树提高一层，并将C子树下降一层 ， 这已经就离 AVL-tree所要求的平衡条件更进一步了。
上图右侧即是调整后的情况。我们可以这么想象，==把k1向上提起，使k2自然下滑，并将B子树挂到k2的左侧。==这么做是因为，二叉搜索树的规则我们知道，k2>k1，所以k2 必须成为新树形中的 k1 的右子节点。二叉搜索树的规则也告诉我们，B子树的所有节点的值都在k1 和k2 之间，所以新树形中的 B 子树必须落在k2 的左侧。

双旋转

如果是内侧插入，单旋转是满足不了条件的，所以要进行多次旋转。

上图插入新节点是15，此时k3平衡不满足条件，此时如果依旧采用单旋是解决不了的，不论是对k1还是k3进行单旋都不行（可以画图自己试试）。所以就需要采用其他策略来解决。==

1. 不妨以k2为新的根节点；
2. 将k1放在k2的左边，k3放在k2的右边。

这样就能让k2新的根节点的平衡因子是0，而其左右子树的平衡因子也是0。

以上面的插入为例，==先将k1左旋，让k2代替k1的位置，再将k3右旋，让k2代替k3的位置，==这样就完成了新的根节点替换。

示意图如下：

RB-tree

除了AV-tree，还有一种平衡平衡二叉树：RB-tree，红黑树并没有AVL严格，红黑树只要求最长路的长度不超过最短路的二倍。下面看看红黑树是通过要求达到的这一效果：

1. 每个节点都有颜色，要么是红色要么是黑色；
2. 根节点一定是黑色；
3. 如果当前节点是红色，其子节点一定是黑色，即红色节点不能相连；
4. 任意一条路径上的黑色节点个数相同。

通过3和4就使得最短路都是黑色，最长路红黑交替，因此最长路长度不会超过最短路的二倍。

• 根据规则4，新插入的节点一定是红色的；
• 根据规则3，新增节点的父节点一定是黑色的，否则需要调整。

下图是一个满足条件的红黑树：

插入节点

红黑树也是搜索二叉树，所以想找到位置，将节点插入，判断父节点是否是黑色，如果不是就不满足条件，需要进行调整。

下图就是插入节点时的各种情况：

上图中插入的节点都不满足条件，所以需要进行调整。

为了方便讨论，让我先为某些特殊节点定义一些代名。以下讨论都将沿用这些代名。假设新节点为X，其父节点为P，祖父节点为G，伯父节点（父节点之兄弟节点）为S，曾祖父节点为GG。现在，根据二叉搜索树的规则，新节点X必为叶节点。根据红黑树规则4,X必为红。若P亦为红（这就违反了规则3，必须调整树形），则G必为黑(因为原为RB-tree，必须遵循规则3)。于是，根据X的插人位置及外围节点(S和GG)的颜色，有了以下四种考虑。

1. 状况1：S为黑且X为外侧插人。对此情况，我们先对 P,G做一次单旋转，再更改P,G颜色，即可重新满足红黑树的规则3。

2. 状况2：S为黑且X为内侧插入。对此情况，我们必须先对P,X做一次单旋转并更改G,X颜色，再将结果对G做一次单旋转，即可再次满足红黑树规则3。

3. 状况3：S为红且X为外侧插人。对此情况，先对P和G做一次单旋转，并改变X的颜色。此时如果GG为黑，一切搞定，如图。但如果GG 为红，则问题就比较大些，看情况4

4. 状况4：S为红且X为外侧插人。对此情况，先对P和G做一次单旋转，并改变X的颜色。此时如果GG亦为红，还得持续往上做，直到不再有父子连续为红的情况。

一个由上而下的程序

在上图情况3中如果，GG节点依旧是红色，就需要继续向上进行调整，继续旋转，这就导致可能因为插入一个节点，导致大量的旋转。

此处有个优化：如果向上更新的时候，X是红，P也是红，S也是红，可以直接将P和S都调整成黑色，将G调整为红色，继续拿着G当作X向上找，如果P和S还是红，继续修改颜色，向上直到P是红，而S是黑时，就是情况1或2进行旋转。这样就可以大大减少旋转的次数了。

示意图如下：