C++ STL详解 红黑树（二）：C++插入实现、旋转修复与合法性验证
·
C++ STL详解 红黑树（二）：C++插入实现、旋转修复与合法性验证
前言：把红黑树规则真正写进代码
上一篇主要解决的是：
红黑树为什么能够保持近似平衡？
以及：
插入以后为什么需要变色和旋转？
这一篇正式进入代码实现。
我们主要实现：
1. 红黑树结点
2. 左旋与右旋
3. BST 插入
4. 红黑树插入修复
5. Find 查找
6. 红黑树合法性验证
一、红黑树结点如何设计
1. 颜色枚举
首先定义颜色：
enum Colour
{
RED,
BLACK
};
每个结点只能处于：
RED
或者：
BLACK
两个状态。
2. RBTreeNode
这里采用：
key-value
结构：
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};
这里值得注意的是：
_parent
普通 BST 有时只保存：
left
right
但是红黑树插入以后需要不断寻找：
parent
grandfather
uncle
所以保留父指针能够让调整代码更加容易。
二、为什么构造时默认把结点设成红色
1. 插入黑色会影响黑高度
假设：
10(B)
/ \
5(B) 15(B)
现在插入：
3
如果直接设成黑色：
10(B)
/ \
5(B) 15(B)
/
3(B)
左边路径立刻多了一个黑结点。
这会破坏：
所有根到 NIL 的路径拥有相同黑结点数
这一性质。
2. 插入红色更加容易修复
如果：
3(R)
那么路径黑高度没有变化。
唯一可能出现的是：
父结点也是红色
从而形成：
RED → RED
这种冲突可以通过：
变色
旋转
解决。
所以非根结点通常默认：
_col = RED;
如果插入的是整棵树的第一个结点，再单独修改：
_root->_col = BLACK;
这正是原资料插入算法采用的处理方式。
三、红黑树为什么需要旋转
1. 旋转不会破坏 BST 的有序性
假设：
parent
\
subR
/
subRL
并且按照 BST：
parent < subRL < subR
进行一次左旋后：
subR
/
parent
\
subRL
中序遍历仍然是：
parent → subRL → subR
所以：
旋转改变的是树的结构，但不会破坏二叉搜索树的有序关系。
因此我们可以通过旋转调整树高和局部结构。
四、左旋 RotateL
1. 左旋前
假设：
parent
/ \
A subR
/ \
subRL C
左旋之后应该得到：
subR
/ \
parent C
/ \
A subRL
2. 左旋代码
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
3. 左旋最容易出错的地方
很多同学第一次写旋转只修改：
_left
_right
但是红黑树还存在：
_parent
所以旋转至少涉及三组关系：
parent 与 subR
parent 与 subRL
subR 与 ppNode
如果其中一个父指针没有更新，很容易导致后面：
parent->_parent
访问错误。
五、右旋 RotateR
1. 右旋前
parent
/ \
subL C
/ \
A subLR
右旋后：
subL
/ \
A parent
/ \
subLR C
2. 代码实现
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
左旋和右旋实际上完全对称。
学习的时候最好不要分别死记，而是记：
左旋：右孩子上位
右旋：左孩子上位
六、第一阶段：先按照 BST 规则插入
红黑树插入的第一阶段和普通 BST 完全相同。
1. 空树
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
第一个结点：
直接作为根
并染成黑色。
2. 寻找插入位置
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;
}
}
这里规定：
key 已经存在 → 插入失败
3. 创建新结点
cur = new Node(kv);
cur->_col = RED;
然后挂到 parent：
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
到这里为止，实际上只完成了一棵普通 BST 的插入。原资料对应代码也是先沿 BST 路径定位位置，再创建红色结点并设置父指针。
七、第二阶段：什么时候需要修复
插入一个红结点以后，只需要观察：
parent
如果：
parent->_col == BLACK
那么：
BLACK → RED
没有违反任何规则。
所以不需要处理。
真正需要处理的是：
while (parent && parent->_col == RED)
也就是说：
parent RED
cur RED
发生红红冲突。
为什么 grandfather 一定存在
由于：
parent 是红色
而红黑树根最终一定是黑色。
因此 parent 不可能是根。
也就是说：
Node* grandfather = parent->_parent;
一定能够找到祖父结点。
八、先判断 parent 在 grandfather 哪边
插入修复代码可以先分成两大类。
情况 A
parent == grandfather->_left
结构大致：
g
/ \
p u
此时：
uncle = grandfather->_right
情况 B
parent == grandfather->_right
结构：
g
/ \
u p
此时：
uncle = grandfather->_left
左右两种情况实际上完全镜像。
九、叔叔为红：只变色
1. 判断
左侧情况：
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
结构类似：
g(B)
/ \
p(R) u(R)
/
c(R)
2. 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
变成：
g(R)
/ \
p(B) u(B)
/
c(R)
3. 为什么继续向上
虽然当前：
p → c
的红红冲突解决了。
但是：
g
刚刚变成红色。
因此它可能和自己的父结点形成新的红红冲突。
于是：
cur = grandfather;
parent = cur->_parent;
继续向上检查。
原资料的实现也是这一处理流程。
十、叔叔为黑：LL 单旋
如果：
parent 在 grandfather 左边
cur 在 parent 左边
形成：
LL
即：
g(B)
/
p(R)
/
c(R)
执行：
RotateR(grandfather);
然后：
parent->_col = BLACK;
grandfather->_col = RED;
于是：
p(B)
/ \
c(R) g(R)
代码：
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
原资料在这一分支同样采用“祖父右旋 + parent 变黑 + grandfather 变红”。
十一、叔叔为黑：LR 双旋
如果：
parent 在 grandfather 左边
cur 在 parent 右边
形成：
LR
即：
g(B)
/
p(R)
\
c(R)
第一次：
RotateL(parent);
变成类似 LL：
g
/
c
/
p
第二次：
RotateR(grandfather);
得到：
c
/ \
p g
颜色：
cur->_col = BLACK;
grandfather->_col = RED;
所以代码：
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
这一逻辑与资料给出的双旋代码保持一致。
十二、右侧情况完全镜像
当：
parent == grandfather->_right
只需要把：
left
right
全部镜像。
RR
g
\
p
\
c
执行：
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
RL
g
\
p
/
c
执行：
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
资料中的右侧分支也是这一镜像关系。
十三、完整 Insert 代码
将前面的逻辑组合起来：
bool Insert(const pair<K, V>& kv)
{
// 1. 空树
if (_root == nullptr)
{
_root = new Node(kv);
_root->_col = BLACK;
return true;
}
// 2. 按照 BST 规则寻找插入位置
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;
}
}
// 3. 插入红色新结点
cur = new Node(kv);
cur->_col = RED;
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
// 4. parent 为红时发生红红冲突
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
// parent 在 grandfather 左边
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
// Case 1：叔叔为红
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
// Case 2：LL
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// Case 3：LR
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
// parent 在 grandfather 右边
else
{
Node* uncle = grandfather->_left;
// Case 1：叔叔为红
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
// Case 2：RR
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
// Case 3：RL
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
// 根最终必须是黑色
_root->_col = BLACK;
return true;
}
原资料最终同样在修复结束后强制 _root->_col = BLACK。
十四、为什么旋转以后可以 break
观察：
LL
RR
LR
RL
这四种情况。
旋转之后，这一局部子树新的根都会被设成：
BLACK
例如 LL：
p(B)
/ \
c(R) g(R)
因此这棵子树向上的连接位置出现的是：
BLACK
它不可能再与上面的红结点构成：
RED → RED
而且旋转前后局部黑高度没有改变。
所以：
break;
直接结束即可。
相比之下，叔叔为红时：
grandfather → RED
所以可能继续产生红红冲突，必须继续向上调整。
这就是两种情况最大的区别。
十五、Find 为什么非常简单
红黑树虽然多了颜色和旋转，但它始终还是：
Binary Search Tree
所以查找完全不需要关心颜色。
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
而红黑树高度满足：
h = O(logN)
所以：
Find = O(logN)
资料中的 Find 也是直接复用 BST 搜索逻辑。
十六、不能只检查“最长路径是否小于两倍最短路径”
这是红黑树验证过程中很容易出现的误区。
我们已经证明：
合法红黑树
↓
最长路径 <= 2 × 最短路径
但这不代表反过来也成立：
最长路径 <= 2 × 最短路径
↓
一定是合法红黑树
这是错误的。
因为一棵树可能高度比例碰巧满足要求，但是存在：
连续红色结点
或者：
不同路径黑结点数量不同
因此真正验证红黑树时应该直接验证红黑树规则。
原资料也特别指出，只比较最长路径与最短路径并不能证明一棵树满足红黑树的颜色约束。
十七、如何检查连续红色结点
我们可以遍历整棵树。
如果当前结点：
root->_col == RED
同时父结点也是：
root->_parent->_col == RED
则直接说明：
红黑树非法
代码：
if (root->_col == RED
&& root->_parent
&& root->_parent->_col == RED)
{
cout << root->_kv.first
<< " 存在连续红色结点"
<< endl;
return false;
}
相比检查：
左孩子
右孩子
检查父结点只需要一次判断，因此实现更加简洁。
十八、如何检查每条路径黑结点数量相同
1. 先取一条路径作为参考
可以从根一路向左：
int refNum = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
{
++refNum;
}
cur = cur->_left;
}
得到：
refNum
作为参考黑结点数量。
2. DFS 检查所有路径
遍历过程中维护：
blackNum
如果当前结点是黑色：
++blackNum;
当：
root == nullptr
时，说明已经走完一条完整路径。
此时比较：
blackNum == refNum
即可。
十九、Check 函数
bool Check(Node* root, int blackNum, const int refNum)
{
if (root == nullptr)
{
if (blackNum != refNum)
{
cout << "存在黑色结点数量不同的路径"
<< endl;
return false;
}
return true;
}
// 检查是否存在红红冲突
if (root->_col == RED
&& root->_parent
&& 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);
}
这里 blackNum 是值传递，因此左右子树都会获得当前路径的黑结点数量副本，不需要手动回溯减一。
原资料的 Check 函数同样在到达 nullptr 时比较参考黑结点数，并在递归过程中统计黑结点数量。
二十、IsBalance 函数
最终：
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()这里只是在验证“红黑性质”。如果要对整个数据结构进行完整测试，还应该额外验证 BST 的大小关系是否正确。
例如：
左子树所有 key < root key
右子树所有 key > root key
否则一棵颜色完全正确、但 key 顺序错误的树，同样不能称为正确的红黑搜索树。
二十一、把核心代码整合起来
下面给出核心结构：
#include <iostream>
#include <utility>
using namespace std;
enum Colour
{
RED,
BLACK
};
template<class K, class V>
struct RBTreeNode
{
pair<K, V> _kv;
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
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);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
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 (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
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);
}
private:
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
bool Check(Node* root,
int blackNum,
const int refNum)
{
if (root == nullptr)
{
return blackNum == refNum;
}
if (root->_col == RED
&& root->_parent
&& root->_parent->_col == RED)
{
return false;
}
if (root->_col == BLACK)
{
++blackNum;
}
return Check(root->_left, blackNum, refNum)
&& Check(root->_right, blackNum, refNum);
}
private:
Node* _root = nullptr;
};
这份代码暂时和原资料一样，主要完成：
Insert
Find
红黑树合法性验证
并没有继续展开红黑树删除。
二十二、插入操作时间复杂度分析
1. 找插入位置
红黑树高度为：
O(logN)
因此 BST 查找插入位置：
O(logN)
2. 变色
叔叔为红时可能不断向祖先传播。
最多从叶子传播到根，因此：
O(logN)
3. 旋转
一旦进入：
LL
RR
LR
RL
旋转次数只是常数次：
单旋：1 次
双旋：2 次
所以单次旋转修复本身：
O(1)
整体插入最终仍然是：
O(logN)
二十三、真正写红黑树时最容易出现的错误
1. 忘记设置 parent
错误：
parent->_left = cur;
却忘记：
cur->_parent = parent;
后面寻找：
grandfather
时就会出现问题。
2. 旋转后忘记连接祖父的父亲
旋转不仅仅改变：
g
p
c
还必须考虑：
g 原来的父亲
否则整棵树可能被断成两部分。
3. 旋转根时忘记更新 _root
必须单独判断：
if (parent == _root)
否则旋转之后 _root 仍然指向旧根。
4. 新结点错误地设成 BLACK
这会直接改变某些路径的黑高度，使问题远比红红冲突难处理。
5. 叔叔为红以后忘记继续向上
变色：
p/u → BLACK
g → RED
以后问题可能传播到：
g 与 g 的父亲
所以必须：
cur = grandfather;
继续检查。
6. 双旋时染错结点
LL / RR 最终：
parent → BLACK
而 LR / RL 最终：
cur → BLACK
这是非常容易写错的一点。
二十四、如何真正记住红黑树插入代码
不要直接背 100 多行代码。
只需要记住下面这个决策树：
插入 RED
|
v
parent 是 RED？
/ \
否 是
| |
结束 v
看 uncle
/ \
RED BLACK/NIL
| |
p、u变黑 判断结构
g变红 |
| ┌────────┼────────┐
| LL LR RR/RL
| | | |
向上继续 单旋 双旋 对称处理
进一步压缩就是：
叔叔红：
变色 + 继续向上
叔叔黑：
旋转 + 变色 + 结束
这句话才是红黑树插入算法真正应该记住的核心。
总结
红黑树的代码虽然看起来比较长，但真正复杂的部分其实只有插入修复。
整个 Insert 可以拆成：
第一阶段：
BST 插入
第二阶段：
新结点染红
第三阶段：
如果父结点为红，修复红红冲突
而修复又只有两大类：
uncle == RED
→ 变色
→ 向上继续
uncle == BLACK / nullptr
→ 判断 LL / RR / LR / RL
→ 旋转
→ 变色
→ 结束
写代码时，只要始终抓住：
cur
parent
grandfather
uncle
四个结点之间的关系，红黑树的插入代码就不会显得杂乱。
最后还可以利用：
根必须为黑
不能存在红红相连
所有路径黑高度相同
写一个 IsBalance() 对自己的实现进行验证。
这也是自己手写红黑树时非常重要的一步。
AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。
更多推荐
27
0- 0
已为社区贡献27条内容
所有评论(0)