C++语言原理与实践(二十):红黑树的实现

本篇目标:
1.掌握红黑树的概念与染色过程

2.学会红黑树的实现

注意：学习本片前必须要学会AVL树的旋转。

一.红黑树的概念

1.概念

红黑树是一棵二叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜色，可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有⼀条路径会比其他路径长出2倍，因而是接近平衡的。

如图：

2.规则

一棵红黑树必须要满足以下的规则:

<1>.每个结点不是红色就是黑色

<2>. 根结点是黑色的

<3>. 如果⼀个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意⼀条路径不会有连续的红色结点。

<4>. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点

首先呢，我们先看一张图片，看看这张图片从根节点到NULL节点上有几条路径？

如图：

很多人的第一反应可能是 4 条，因为图中有 15、25、35、50 四个叶子节点。但这数的是从根节点到普通叶子节点的路径，还没有走到 NULL。

每个叶子节点都有两个空孩子，因此，这四个叶子节点对应：8条到 NULL 的路径。

此外，节点 10 的左孩子也是 NULL，还需要再算一条。

所以，这棵树从根节点到 NULL 节点，一共有：9条

红黑树性质中所说的叶子节点，指的是这些黑色的 NULL（也称 NIL）节点。为了让图更简洁，它

们通常没有画出来，但分析路径时不能忽略。

所以完整的图如下：

注意：通常每个NULL节点都是黑色的，如果是红色容易与规则三冲突。

然后我们接着看些其他的红黑树：

3.效率

首先，我们思考⼀下，红黑树如何确保最长路径不超过最短路径的2倍的？

关键在于两条性质：

从根节点到任意 NULL 节点的路径，包含的黑色节点数量相同。
红色节点不能连续出现，并且根节点为黑色。

设每条路径上都有 bh 个黑色节点。这里统一不计 NULL，用路径上的非空节点数量表示路径长度。

对于任意一条路径：

长度下限：即使没有红色节点，也有 bh 个黑色节点，因此路径长度至少为 bh。
长度上限：由于根为黑色，且红色节点不能连续出现，红色节点数量不会超过黑色节点数量，因此路径长度至多为 2bh。

所以，任意路径长度 h 都满足：bh ≤ h ≤ 2 × bh

设最短路径长度为 h_min，最长路径长度为 h_max，则：h_min ≥ bh，h_max ≤ 2 × bh

因此：h_max ≤ 2 × bh ≤ 2 × h_min

所以，最长路径不超过最短路径的两倍。

需要注意：全黑路径和红黑交替路径只是分析上下限时考虑的极端情况，并不要求每棵红黑树中都存在这样的路径。

接下来，我们谈下红黑树的效率：

假设红黑树中有 N 个非空节点，最短路径长度为 h，最长路径长度为 H。这里路径长度统一按从根到 NULL 经过的非空节点数计算。

由于最短路径长度为 h，前 h 层一定是满的，因此：N ≥ 2^h − 1

由此得到：h ≤ log₂(N + 1)

又因为红黑树的最长路径不超过最短路径的两倍，所以：H ≤ 2h ≤ 2 × log₂(N + 1)

因此，红黑树的高度为 O(log N)，查找、插入和删除的最坏时间复杂度也都是 O(log N)。如果需要修改 value，先按 key 查找即可；key 不能直接修改，否则可能破坏搜索树的性质。

与 AVL 树相比，红黑树对平衡的控制更加间接：AVL 树通过左右子树的高度差维持平衡，红黑树则通过颜色约束，保证最长路径不超过最短路径的两倍。

两者的操作复杂度都属于 O(log N)，但红黑树对平衡的要求更宽松，调整时可以通过变色和旋转恢复性质。需要注意，不能简单认为插入相同数量的节点，红黑树的旋转次数就一定比 AVL 树少，具体次数还与插入顺序有关。

二.红黑树的实现

1.结构

// 枚举值表示颜色
enum Colour
{
RED,
BLACK
};
// 默认按 key/value 结构实现
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;

// 调整树的平衡时，需要通过 parent 指针找到父节点
RBTreeNode<K, V>* _parent;
Colour _col;

RBTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
private:
Node* _root = nullptr;
};

结构与之前的AVL树大致相同，但是红黑树中我们需要一个用来表示颜色的Colour结构。

2.插入

2.1.大致过程

红黑树的插入分为两步：先按二叉搜索树的规则插入节点，再检查并恢复红黑树的性质。

<1>.树为空：创建新节点作为根节点，并将其设为黑色，插入结束。

<2>.树不为空：新增节点设为红色。因为插入红色节点不会改变各条路径上的黑色节点数量；如果插入黑色节点，则会破坏黑色节点数量相同的性质，调整起来更加复杂。

<3>.父节点为黑色：新增的红色节点没有违反任何性质，插入结束。

<4>.父节点为红色：出现连续的红色节点，需要进行调整。此时，当前节点和父节点都是红色，祖父节点必然为黑色。接下来需要根据叔叔节点是否存在及其颜色，结合当前节点与父节点的位置关系，分别处理。

后续图中统一使用以下标记：

c（cur）：当前需要处理的节点，初始为新增节点。
p（parent）：c 的父节点。
g（grandfather）：p 的父节点，即 c 的祖父节点。
u（uncle）：p 的兄弟节点，即 c 的叔叔节点。

调整过程中可能需要继续向上处理，因此 c 不一定始终指向最初新增的节点。

2.2.变色

情况一：c 为红色，p 为红色，g 为黑色，且叔叔节点 u 存在并为红色。

此时，c 与 p 连续为红色，违反了红黑树的性质。处理方式是：

将父节点 p 和叔叔节点 u 变为黑色。

将祖父节点 g 变为红色。

把 g 当作新的 c，继续向上检查。

为什么这样变色？

将 p 和 u 变黑后，经过它们的路径都增加了一个黑色节点；再将 g 变红，每条路径又减少一个黑色节点。因此，从 g 所在子树通往各个 NULL 节点的路径，黑色节点数量保持不变，同时消除了 c 与 p 连续为红色的问题。

为什么还要向上检查？

因为 g 变成了红色，可能与它的父节点形成新的连续红色：

g 的父节点为红色：继续向上调整。
g 的父节点为黑色：调整结束。
g 已经是根节点：将 g 重新设为黑色，调整结束。

这种情况只需要变色，不需要旋转。无论 c 是 p 的左孩子还是右孩子，p 是 g 的左孩子还是右孩子，处理方式都相同。

变色如图：

这个图片向我们展示了⼀种具体情况，但是实际中需要这样处理的有很多种情况。

抽象图如下：

该图将以上类似的处理进行了抽象表达，d/e/f代表每条路径拥有hb个黑色结点的子树，a/b代表每

条路径拥有hb-1个黑色结点的根为红的子树，hb>=0。

代码如下：

bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = Black;
return true;
}

//寻找插入的地方
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
//插入节点
cur = new Node(kv);
cur->_col = Red;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;

//检查parent是否为Red
//注意此处是先检查parent是否存在，在检查parent的颜色是否为红色
while (parent&&parent->_col == Red)
{
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//染色不旋转
if (uncle && uncle->_col == Red)
{
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
//uncle->_col == Black||uncle==nullptr
else
{
}
}
//grandfather->_right == parent
else
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == Red)
{
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;

cur = grandfather;
parent = cur->_parent;
}

else
{
}
}
}
return true;
}

但是，我们还有个问题：会不会改着改着将根节点给改成红色的了？当然是有这种可能的，所以我们要在最后加上：

_root->_col = Black;

而且我们这个代码还要区分grandfather的左节点和右节点哪一个指向parent?这个将会影响后面

的旋转，但是这篇文章我们优先考虑grandfather->_left==parent，当我们真正的了解思想后就可以独立的写grandfather->_right==parent的代码了。

2.3.单旋+变色

情况二：c 为红色，p 为红色，g 为黑色，叔叔节点 u 不存在或为黑色。

这里可以进一步区分：

u 不存在：c 是本次新增的红色节点。
u 存在且为黑色：c 不是新增节点，而是在下层按情况一调整时，由黑色变为红色，再作为新的 c 向上传递的节点。

此时，c 与 p 连续为红色，需要调整。但由于叔叔一侧没有红色节点可以一起变黑，单纯变色无法同时保证黑色节点数量相同，因此需要通过旋转配合变色恢复红黑树的性质。

<1>. p 是 g 的左孩子，c 是 p 的左孩子：右单旋＋变色

g
p u(可能不存在)
c

此时，g、p、c 形成左左结构，处理步骤如下：

以 g 为旋转点进行右单旋，让 p 成为这棵子树的新根。

将 p 变为黑色，g 变为红色。

c 保持红色。

调整后，p 为黑色，c 和 g 为红色，消除了连续红色节点，同时保持这棵子树各条路径上的黑色节点数量不变。

<2>. p 是 g 的右孩子，c 是 p 的右孩子：左单旋＋变色

g
u p
c

此时，g、p、c 形成右右结构，与左左情况对称：

以 g 为旋转点进行左单旋，让 p 成为这棵子树的新根。

将 p 变为黑色，g 变为红色。

c 保持红色。

调整后，同样消除了连续红色节点，并保持这棵子树各条路径上的黑色节点数量不变。

这两种情况调整完成后，都不需要继续向上处理。

因为新的子树根节点 p 为黑色，无论它上面连接的是红色节点、黑色节点，还是它直接成为整棵树的根，都不会产生新的颜色冲突；同时，子树对外的黑色高度保持不变，不会影响其他路径。

这里我拿上面的右单旋来举例子：

示例一:

插入红色节点 3 后，3 与父节点 6 连续为红，形成左左结构。以 10 为旋转点右单旋，再将 6 变黑、10 变红，调整结束。

示例二：

节点 3 原本为黑色。在它的子树中插入节点并进行变色后，3 变红，作为新的 c 向上检查，与红色父节点 6 产生冲突。

此时叔叔 15 为黑色，需要以 10 为旋转点右单旋：

6 成为这棵子树的新根。
子树 d 从 6 的右子树，转接为 10 的左子树。
10 成为 6 的右孩子。
将 6 变黑、10 变红，3 保持红色。

示例三：

最初 a、b 的根为红色，d 的根为黑色。下层插入并变色后，a、b 的根变黑，节点 3 变红，因此经过 3 的路径上，黑色节点数量保持不变。

随后进行右单旋和变色，消除 3 与 6 连续为红的问题。调整后的子树根 6 为黑色，子树对外的黑色高度保持不变，不需要继续向上调整。

代码：

//存在且为⿊或不存在-》旋转+变⾊
if (parent->_left == cur)
{
Rotate_Right(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}

2.4.双旋+变色

情况三：c 为红色，p 为红色，g 为黑色，叔叔节点 u 不存在或为黑色，且 c 与 p 的方向不同。

其中：

u 不存在：c 是本次新增的红色节点。
u 存在且为黑色：c 是下层按情况一变色后，由黑色变为红色，再向上传递的节点。

此时，c 与 p 连续为红色，单纯变色无法同时维持各条路径上的黑色节点数量，需要通过双旋配合变色恢复红黑树的性质。

<1>. p 是 g 的左孩子，c 是 p 的右孩子：左右双旋＋变色

g
p u(可能不存在)
c

处理步骤如下：

以 p 为旋转点进行左单旋，将左右结构转化为左左结构。

以 g 为旋转点进行右单旋，让原来的 c 成为这棵子树的新根。

将 c 变为黑色，g 变为红色，p 保持红色。

调整后，c 为黑色，左右孩子 p、g 为红色，消除了连续红色节点，并保持子树各条路径上的黑色节点数量不变。

<2>. p 是 g 的右孩子，c 是 p 的左孩子：右左双旋＋变色

g
u p
c

处理步骤与左右情况对称：

以 p 为旋转点进行右单旋，将右左结构转化为右右结构。

以 g 为旋转点进行左单旋，让原来的 c 成为这棵子树的新根。

将 c 变为黑色，g 变为红色，p 保持红色。

双旋完成后，变黑的是新的子树根 c，而不是 p。

新的子树根 c 为黑色，无论它上面连接的是红色节点、黑色节点，还是它直接成为整棵树的根，都不会产生新的颜色冲突。同时，子树对外的黑色高度保持不变，因此不需要继续向上调整。

那么我拿上面的左右单旋来举例子：

示例一：

先以 p（6）左旋，使 8 成为 10 的左孩子，6 成为 8 的左孩子；再以 g（10）右旋，使 8 成为子树的新根。最后将 8 变黑、10 变红，6 保持红色。

示例二：

第一次左旋时，子树 a 转接为 6 的右子树，b 仍为 8 的右子树。第二次右旋时，子树 b 转接为 10 的左子树。最终 6、10 分别成为 8 的左右孩子。

示例三：

下层插入并变色后，8 由黑变红，与父节点 6 产生冲突。随后依次左旋、右旋并变色，在消除连续红色节点的同时，保持子树对外的黑色高度不变，调整结束。

代码：

//染色+双旋转,parent->_right == cur
else
{
Rotate_Left(parent);
Rotate_Right(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;

所以一个半完整的代码如下：

if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//染色不旋转
if (uncle && uncle->_col == Red)
{
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
//uncle->_col == Black||uncle==nullptr
else
{
//存在且为⿊或不存在-》旋转+变⾊
if (parent->_left == cur)
{
Rotate_Right(grandfather);
parent->_col = Black;
grandfather->_col = Red;
}
//染色+双旋转,parent->_right == cur
else
{
Rotate_Left(parent);
Rotate_Right(grandfather);
cur->_col = Black;
grandfather->_col = Red;
}
break;
}
}

那么这个grandfather->_right == parent的代码我就不再详细的解释了，如下：

// grandfather->_right == parent
else
{
Node* uncle = grandfather->_left;

// 染色，不旋转
if (uncle && uncle->_col == Red)
{
parent->_col = Black;
uncle->_col = Black;
grandfather->_col = Red;

cur = grandfather;
parent = cur->_parent;
}
else
{
// 染色 + 单旋转
if (parent->_right == cur)
{
Rotate_Left(grandfather);

parent->_col = Black;
grandfather->_col = Red;
}
// 染色 + 双旋转，parent->_left == cur
else
{
Rotate_Right(parent);
Rotate_Left(grandfather);

cur->_col = Black;
grandfather->_col = Red;
}

break;
}
}

3.验证

仅通过获取最长路径和最短路径，检查最长路径是否不超过最短路径的 2 倍，无法判断一棵树是否满足红黑树的规则。

因为即使满足这个条件，结点的颜色仍可能违反规则。当前暂时没有出现问题，后续继续插入时也可能出现问题。

因此，我们还是需要检查以下 4 条规则。满足这些规则，就能保证最长路径不超过最短路径的 2 倍。

<1>.结点的颜色不是黑色，就是红色。

使用枚举类型定义颜色，在正常使用的情况下即可保证这一点。

<2>.根结点必须是黑色。

直接检查根结点的颜色即可。

<3>.不能出现连续的红色结点。

使用前序遍历检查。遇到红色结点时，可以检查其孩子是否为红色，但孩子有两个，而且不一定存在。

因此，反过来检查其父亲的颜色更方便：如果当前结点和父亲都是红色，就违反了规则。

<4>.从根结点到每个空结点的路径上，黑色结点的数量必须相同。

使用前序遍历，通过形参 blackNum 记录从根结点到当前结点的黑色结点数量。每遇到一个黑色结点，就执行 ++blackNum；走到空结点时，就得到了一条完整路径上的黑色结点数量。

任选一条路径的黑色结点数量作为参考值，再依次比较其他路径。如果存在不同的数量，就违反了规则。

代码如下：

bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
// 遍历到空结点，意味着一条路径走完了
if (refNum != blackNum)
{
cout << "存在黑色结点数量不相等的路径" << endl;
return false;
}
return true;
}
// 检查当前结点和父亲是否都是红色
if (root->_col == RED && root->_parent->_col == RED)
{
cout << root->_kv.first << " 存在连续的红色结点" << endl;
return false;
}
// 记录当前路径上的黑色结点数量
if (root->_col == BLACK)
{
blackNum++;
}
return Check(root->_left, blackNum, refNum)
&& Check(root->_right, blackNum, refNum);
}

bool IsBalance()
{
// 空树符合红黑树规则
if (_root == nullptr)
{
return true;
}
// 根结点必须是黑色
if (_root->_col == RED)
{
return false;
}
// 统计最左侧路径上的黑色结点数量，作为参考值
int refNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refNum;
}
cur = cur->_left;
}
return Check(_root, 0, refNum);
}

这里讲一下思路：

先检查根结点，再选择一条路径作为参考，最后递归检查整棵树。

IsBalance()：检查根结点，确定参考值。

空树直接返回 true；根结点为红色，直接返回 false。

接着从根结点开始，一直往左走，统计这条路径上的黑色结点数量，记为 refNum。选最左侧路径只是因为方便，任意一条从根到空结点的路径都可以作为参考。

Check()：统计每条路径上的黑色结点数量。

blackNum 表示当前路径上已经遇到的黑色结点数量。遇到黑色结点，就执行 blackNum++。

当 root == nullptr 时，说明一条路径走完了，此时比较：

refNum == blackNum

相等，说明这条路径符合要求；不相等，说明不同路径上的黑色结点数量不一致。

这里没有把空结点计入黑色结点数量，但每条路径都采用相同的统计方式，因此不影响比较结果。

遇到红色结点，检查其父亲的颜色。

if (root->_col == RED && root->_parent->_col == RED)

当前结点和父亲都是红色，就出现了连续的红色结点，返回 false。

这里依赖 IsBalance() 已经检查根结点为黑色。检查到根结点时，&& 左侧为假，右侧不会执行，因此不会访问根结点的空父指针。

左右子树都通过，当前子树才通过。

return Check(root->_left, blackNum, refNum)
&& Check(root->_right, blackNum, refNum);

任意一侧返回 false，整体就返回 false。

blackNum 按值传递，左右递归拿到的是各自的副本，所以左子树对计数的修改不会影响右子树，也不需要在递归返回后执行 –blackNum。

最后，删除这个部分依旧不讲，如果后期我学会了相关的操作再考虑要不要补充。

总结：

红黑树是在二叉搜索树的基础上，通过颜色规则维持近似平衡的数据结构，其查找、插入和删除的最坏时间复杂度均为 O(log N)。插入时，若出现连续的红色结点，就根据叔叔结点的颜色及结点的位置，通过变色、单旋或双旋恢复红黑树的性质。验证时，应检查根结点为黑色、不存在连续红色结点，以及各条从根到 NULL 的路径上黑色结点数量相同，不能仅凭最长路径不超过最短路径的两倍来判断。