【STL源码剖析】系列十：关联式容器--RB-tree

发表于 2023-11-09 更新于 2024-04-20 分类于 STL源码剖析阅读次数：本文字数： 4.8k 阅读时长 ≈ 16 分钟

前言

本篇主要介绍STL中的RB-tree(红黑树)结构，主要内容包括：

1.在了解红黑树之前，需要对于二叉搜索树和AVL树进行初步认识，红黑树作为一种二叉搜索树，其本身就是为了提高查找效率(O(logn))，此外还需要熟悉AVL树的左旋和右旋操作；

2.红黑树的性质，以及当插入时如何通过一些调整措施保证红黑树的性质不被破坏；

3.在STL中对于红黑树的实现，以及常见操作。

树与AVL树

二叉搜索树

二叉搜索树也称为二叉排序树、二叉查找树，定义为具有以下性质的二叉树：

若左子树不空，那么左子树上所有节点的值均小于根节点的值；
若右子树不空，那么右子树上所有节点的值均大于根节点的值；
左右子树也均为二叉搜索树

二叉搜索树的查找操作：

从根节点开始逐个与目标值进行比较，如果当前根节点的值大于目标值，就递归从左子树查找；如果当前根节点的值小于目标值，就递归从右子树查找。

二叉搜索树的插入操作：

插入一个新元素时，从根节点开始，遇到值较大就向左子树，遇到值小就向右子树，直到尾端就是插入位置。

二叉搜索树的删除操作：

如果要删除一个节点A，分为两种情况：（如果A是叶子节点可以直接删除）

（1）A只有一个子节点，直接将A的子节点连接到A的父节点，然后删除A；

（2）A有两个子节点，以A的右子树的最小值取代A，也就是A的右子树的最左叶子节点。

查找速度取决于二叉排序的层数，但是二叉排序树的形状是不确定的。比如：

平衡二叉搜索树–AVL树

树的一些相关定义：

树的根节点到任何节点之间有一条唯一的路径，路径所包含的边数称为路径长度。

一个节点的深度指的是根节点到该节点的路径长度。

一个节点的高度指的是该节点到其最深子节点（叶子节点）的路径长度。

由于二叉搜索树的查找效率取决于节点所在的层数，因此所有节点的深度均不会太大就会使得总体的查找效率比较低。这也就是平衡二叉树的思想。

AVL-tree的平衡条件是任何节点的左右子树的高度差最多为1。左子树深度减去右子树深度称为平衡因子，平衡树的平衡因子只有可能是1（左子树比右子树深）、0（左子树和右子树一样深）、-1（右子树比左子树深）

这里需要引入一个最小不平衡子树的概念：距离插入节点最近的，并且以平衡因子的绝对值大于1的节点为根的子树，称为最小不平衡子树。如果插入新节点导致不平衡，只需调整最小不平衡子树即可。

AVL-tree的单旋转与双旋转

当最小不平衡子树根节点的BF大于1时，右旋；
当最小不平衡子树根节点的BF小于-1时，左旋。

（左旋和右旋均只涉及一些指针操作，比较简单，以右旋为例：

同时需要注意，当插入结点之后，最小不平衡子树根节点的BF与它的子树的BF符号相反时，需要先对子树进行旋转使得子树与根的BF符号相同之后，再对根节点进行一次反向旋转之后才能平衡。

注1：什么时候最小不平衡子树根节点的BF与它的子树的BF符号相反？什么时候相同？
左左（插入点位于最小不平衡子树根节点的左子节点的左子树）和右右（插入点位于最小不平衡子树根节点的右子节点的右子树）BF符号相同：以左左为例，根的BF为2，左子节点的BF为1；

左右（插入点位于最小不平衡子树根节点的左子节点的右子树）和右左（插入点位于最小不平衡子树根节点的右子节点的左子树）BF符号不同：以左右为例，根的BF为2，左子节点的BF为-1.

注2：以左右为例说明双旋转的过程：根据根节点的BF为2判断应该进行右旋，但是检查左子节点的BF为-1，所以应该先对左子节点进行左旋（因为左子节点的BF是负数），再对根节点进行右旋。

RB-tree（红黑树）

RB-tree的定义，不仅是一个二叉搜索树，还必须满足以下规则：

1.每个节点不是红色就是黑色；

2.根节点为黑色；

3.如果节点为红，子节点必须为黑色；

4.任一节点到NULL（树尾端）的所有路径，所包含的黑节点的数目必须相同。

默认NULL节点为黑色。

根据规则4，新增节点必须为红：如果新增一个黑色节点，那么其父节点经过这个新增节点到达NULL的黑节点数目一定大于经过其它路径到达NULL的黑节点数目。

根据规则3，新增节点的父节点一定是黑色：因为新增节点为红色，因此父节点不能为红（父子不能同时为红）

当新节点根据二叉搜索树的规则到达插入点，却不能符合上面的规则时，需要调整颜色和旋转树形。

补充内容：

红黑树能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍。因为最短路径就是全黑，最长路径就是红黑节点交替，因为每条路径的黑色节点数目都相同，所以最长路径就刚好是最短路径的两倍。

也就是说，相比于AVL树，RB树并不严格追求绝对平衡。

红黑树的插入操作

红黑树是在二叉搜索的基础上进行平衡，因此红黑树的插入步骤可以分为两步：1.按照二叉搜索树的规则找到插入点；2.判断新节点插入之后是否破坏红黑树的条件。

新节点插入时默认是红色，如果其父节点是黑色，那么无需做任何调整，因为没有违反红黑树的性质；如果父节点是红色，就违反了性质3，需要进行调整，调整分为以下几种情况：

父亲为祖父的左儿子：

情况一：父亲和叔叔都是红色，此时无论X是父节点的左孩子还是右孩子，均进行以下调整：
（1）父亲和叔叔变为黑色，满足规则3：父子不能同时为红；叔叔需要变成黑色是因为需要保证叔叔和父亲的路径上黑色数目需要相同
（2）祖父变成红色，满足规则4：因为父亲和叔叔都是黑色，黑色的高度发生了变化，如果祖父还是黑色，会导致这条路径上黑色数目比原来增加；
（3）从祖父开始，继续进行调整，这是为了防止曾祖父为红色，出现祖父和曾祖父同时为红色的情况。

情况二：叔叔是黑色（如果叔叔不存在，即为NULL节点，也默认为黑色），自己是父亲的左孩子：
（1）父亲变成黑色，祖父变成红色。此时右子树的黑色高度减少；
（2）对祖父进行右旋，令父节点称为新的祖父，这样右子树的黑色高度得以恢复.

情况三：叔叔是黑色（如果叔叔不存在，即为NULL节点，也默认为黑色），自己是父亲的右孩子：
（1）对父亲进行左旋操作，使得父亲成为新的X，此时称为上面情况二；
（2）按照情况二进行处理。

父亲为祖父的右儿子：

情况一：父亲和叔叔都是红色，此时无论X是父亲的左孩子还是右孩子，均进行以下处理：
（1）父亲和叔叔都变成黑色，保证父亲不会与孩子X同时为红色。叔叔也需要变成黑色是因为需要保证叔叔和父亲的路径上黑色数目需要相同；
（2）祖父变成红色，满足规则4：因为父亲和叔叔都是黑色，黑色的高度发生了变化，如果祖父还是黑色，会导致这条路径上黑色数目比原来增加；
（3）从祖父开始继续调整，这是为了防止曾祖父为红色，出现祖父和曾祖父同时为红色的情况。

情况二：叔叔是黑色，自己是父亲的右孩子：
（1）父亲变成黑色，祖父变成红色，此时左子树的黑色高度降低；
（2）对祖父进行左旋操作，恢复左子树的黑色高度。

情况三：叔叔是黑色，自己是父亲的左孩子：
（1）对父亲进行右旋操作，使得父亲成为新的X，构造上面情况二；
（2）按照情况二进行处理。

总结：

当父亲为祖父的左孩子时：父叔同色，只进行变色；父叔异色，自己是左孩子，进行R操作；父叔异色，自己是右孩子，进行LR操作；

当父亲为祖父的右孩子时：父叔同色，只进行变色；父叔异色，自己是右孩子，进行L操作；父叔异色，自己是左孩子，进行RL操作。

针对父叔同色的改进

当父叔同色时，对祖父和父叔进行颜色修改之后，需要继续向上对曾祖父进行同样的处理。为了避免自下而上的处理，可以进行一个自上而下的处理：假设新增节点为A，那么验证从根节点到A的路径，只要发现某个节点X的两个子节点都是红色，就将X改为黑色，两个子节点改为黑色。

这样处理之后，如果这个节点X的父节点是红色（此时叔叔不可能是红色，因为上一步中已经把叔父同时为红的情况处理掉了），就需要将X节点视作新增节点，按照情况二（1次旋转）或三（2次旋转）进行处理。

处理完所有X节点之后，就可以对新增节点A进行处理，此时要么直接插入（新增节点的父节点是黑色），要么插入后进行一次单旋转（新增节点的父节点是红色，叔叔一定是黑色）。
不理解为什么作者说一定是一次单旋转，上面的处理过程并不能保证父节点一定是祖父的左孩子还是右孩子，而插入位置也不能保证是父节点的左孩子还是右孩子，因此我认为有可能需要进行两次旋转。

红黑树的节点设计

STL红黑树的节点分为一个base类和一个派生类：

红黑树的节点示意图：

红黑树的迭代器

红黑树的迭代器同样采用继承的架构，分为base迭代器和派生迭代器，两层迭代器与节点之间的关系为：

红黑树的迭代器属于双向迭代器，其解引用和成员访问操作与list相似，比较特殊的是前进和后退操作。RB-tree迭代器的operator++和operator–操作分别调用基类迭代器的increment和decrement方法。

基类迭代器实现：

在实现时，会在树的根节点上多增加一个header节点，这个节点作为根节点的父节点，并且header的父节点就是根节点。header节点的左孩子是二叉排序树的第一个元素，右孩子是二叉排序树的最后一个元素。同时header也作为end()，左孩子是begin()。

increment函数中的情况4：当迭代器指向根节点时，并且根节点没有右孩子，也就是没有直接后继，此时node指向的是根节点，经过while循环处理之后node指向header，y指向根节点，因此node->right就等于y，因此node就是最终结果。

decrement中情况1：当迭代器指向end也就是heaher时，减一操作应该指向header的右孩子，也就是二叉搜索树的最后一个值。

红黑树的迭代器：

红黑树的数据结构

红黑树的构造与内存管理

通过上面的源代码可以看出，红黑树的构造分为两种，一种是以现有的红黑树赋值一个新的红黑树，另一种就是产生一棵空树。但是这个空树会存在一个header节点：

因为增加了一个header节点，所以在进行插入新结点时，不仅需要根据红黑树的规则进行调整，还必须维护header的正确性，令其父节点是根节点，左孩子是最小节点，右孩子是最大节点。

红黑树的元素操作

这里主要介绍红黑树的插入和查找操作。

元素的插入操作

红黑树提供两种插入操作，一种是插入节点的键值（key）必须在整棵树中独一无二，即insert_unique()，如果已经存在相同的键值，那么插入就不会进行；另一种是插入节点的键值可以在树中重复，即insert_equal()。

下面以最简单的版本（只接受一个实值value表示被插入节点）说明，虽然只制定了value，但是通过KeyOfValue仿函数可以从value中获取key。

insert_euqal：

insert_unique：

下面以comp标准为“小于”，说明while循环结束之后的一段代码。

当while循环结束之后，此时x指向插入节点，y指向插入节点的父节点，并且y一定是叶子节点。（这是因为二叉搜索树寻找插入点的特性）此时y与x只有两种可能，要么x是y的左孩子，要么x是y的右孩子，下面分别讨论：

1.x是y的右孩子：
此时comp一定是false，因此x大于等于y才会是右孩子。因此跳过第一段if语句；
在第二段if语句中判断 j （此时与y相同）是否小于x，若是，则经过上面的条件(1)$y \le x$；和此时的条件(2)$y \lt x$可以得到y与x不同，因此可以正常插入；若否，则说明y与x相同。

2.x是y的左孩子：
此时comp一定是true，因此需要进入第一段if语句。首先判断当前的父节点是否为最左节点begin()，如果是，那么直接插入；否则就令 j 指向 y 节点的前一个节点；
接着判断 y 节点的前一个结点与 x 之间的关系。如果 j < x，结合上一步的条件 x < y，并且 j 是 y 的直接前驱，因此 x 不会发生重复；但是如果$j \ge x$，结合之前对于插入点的搜索过程，因为插入点在 j 的后面，所以$x \ge j$，此时就可以说明 j 与 x结点键值重复。

真正的插入程序：__insert