C++算法
STL 红黑树（RB-tree）原理与插入操作实现详解
红黑树是一种自平衡的二叉搜索树，通过颜色约束确保最长路径不超过最短路径的两倍。文章解析了红黑树的四条核心规则，重点阐述了插入操作后的三种修复情况（变色、单旋、双旋），并给出了完整的 C++ 节点结构、旋转逻辑及性质验证代码。相比 AVL 树，红黑树在频繁增删场景下性能更优，时间复杂度为 O(logN)。
红黑树是一种自平衡的二叉搜索树，通过颜色约束确保最长路径不超过最短路径的两倍。文章解析了红黑树的四条核心规则，重点阐述了插入操作后的三种修复情况（变色、单旋、双旋），并给出了完整的 C++ 节点结构、旋转逻辑及性质验证代码。相比 AVL 树，红黑树在频繁增删场景下性能更优，时间复杂度为 O(logN)。
红黑树是一种自平衡的二叉搜索树。它在每个节点上增加一个存储位表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子（空节点）路径上节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因此是近似平衡的。
红黑树的平衡不像 AVL 树那样严格，但它的旋转次数更少，插入删除的效率也更高。
红黑树的平衡靠以下 4 条规则来维持：
注意：叶子节点不一定为红色，可以为黑（那是调整过后的结果）。规则 4 中提到的叶子节点指的是空节点（NIL），它们被认为是黑色的。虽然在实际实现中我们通常不显式处理 NIL 节点，但理解它们有助于理解路径的定义。
bh（black height）。bh。2 * bh。h 满足：bh ≤ h ≤ 2 * bh。假设树中节点数为 N，最短路径长度为 h，则：
2^h - 1 <= N <= 2^(2h) - 1
可得 h ≈ logN，最坏情况下路径长度为 2logN，因此红黑树的查找、插入、删除操作时间复杂度仍为 O(logN)。
相比 AVL 树，红黑树的平衡控制更宽松，旋转次数更少，适合频繁插入删除的场景。
源码：
typedef bool __rb_tree_color_type;
const __rb_tree_color_type __rb_tree_red = false; // 红色为 0
const __rb_tree_color_type __rb_tree_black = true; // 黑色为 1
struct __rb_tree_node_base {
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color; // 节点颜色，非红即黑
base_ptr parent; // RB 树的许多操作，必须知道父节点
base_ptr left; // 指向左节点
base_ptr right; // 指向右节点
static base_ptr minimum(base_ptr x) { while (x->left != 0) x = x->left; return x; }
static base_ptr maximum(base_ptr x) { while (x->right != 0) x = x->right; return x; }
};
template <class Value>
struct _rb_tree_node : public _rb_tree_node_base {
typedef _rb_tree_node<Value>* link_type;
Value value_field; // 节点值
};
实现：
每个节点除了存储键值对、左右子节点指针、父节点指针外，还需要存储颜色。
// 枚举颜色
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) {}
};
新节点为什么默认是红色？ 如果插入黑色节点，会直接违反规则 4（黑色节点数变化），修复成本太高。插入红色节点不会改变黑色节点数，只可能违反规则 3（连续红色），更容易修复。
template<class K, class V>
class RBTree {
typedef RBTreeNode<K, V> Node;
public:
// 构造函数（默认根节点为空）
RBTree() : _root(nullptr) {}
// 插入接口
bool Insert(const pair<K, V>& kv);
// 查找接口
Node* Find(const K& key);
// 验证是否满足红黑树性质
bool IsBalance();
// 中序遍历（用于验证有序性）
void InOrder() { _InOrder(_root); cout << endl; }
private:
// 旋转操作（与 AVL 树类似，但不需要更新平衡因子）
void RotateL(Node* parent); // 左单旋
void RotateR(Node* parent); // 右单旋
// 递归辅助函数
void _InOrder(Node* root);
bool Check(Node* root, int blackNum, const int refNum);
Node* _root = nullptr;
};
为了方便描述，我们约定：
cur：当前新插入的节点（红色）p：父节点（红色，因为如果是黑色就不用处理了）g：祖父节点（一定是黑色，因为不能连续红）u：叔叔节点（p 的兄弟，颜色不确定）【场景描述】
u 存在且为红色p 为红色，g 为黑色【处理方式】
p 和 u 变为黑色g 变为红色g 当作新的 cur，继续向上检查【原理分析】
把 p 和 u 变黑，解决了 cur 和 p 连续红的问题；g 变红，保证了从 g 到叶子路径上黑色节点数量不变（因为下面少了两个黑，上面加了一个红，黑数不变）。但 g 变红后可能和它的父节点形成连续红，所以需要继续向上检查。
// 情况 1：叔叔存在且为红
if (uncle && uncle->_col == RED) {
// 变色
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
}
【场景描述】
u 不存在 或 u 存在且为黑色cur 和 p 在同一侧（都是左孩子 或 都是右孩子）【处理方式】
g 为旋转点进行单旋（左左→右旋，右右→左旋）p 变黑，g 变红【原理分析】
为什么单旋后不用继续向上？因为旋转后 p 成了子树的新根，且 p 是黑色，无论它的父节点是什么颜色，都不会违反规则（红节点下面不能接红，但黑节点下面随便接）。
// 情况 2：左左（右单旋）
if (cur == parent->_left) {
// 右单旋
RotateR(grandfather);
// 变色
parent->_col = BLACK;
grandfather->_col = RED;
break; // 旋转结束，不用继续向上
}
【场景描述】
u 不存在 或 u 存在且为黑色cur 和 p 在不同侧（p 是左孩子，cur 是右孩子 或 反之）【处理方式】
p 为旋转点进行单旋（变成情况 2 的形状）g 为旋转点进行单旋cur 变黑，g 变红【原理分析】 这种情况是"折线"形状，一次旋转解决不了问题。先旋转成"直线"形状，再按情况 2 处理。
// 情况 3：左右（左右双旋）
else // cur == parent->_right
{
// 先左旋 p，再右旋 g
RotateL(parent);
RotateR(grandfather);
// 变色
cur->_col = BLACK;
grandfather->_col = RED;
break; // 旋转结束，不用继续向上
}
bool Insert(const pair<K, V>& kv) {
// 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; // 键值已存在
}
}
// 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. 修复红黑树性质
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (parent == grandfather->_left) {
Node* uncle = grandfather->_right;
// 情况 1：叔叔存在且为红 → 变色
if (uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续向上处理
cur = grandfather;
parent = cur->_parent;
} else {
// 情况 2：叔叔不存在或为黑
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 // parent == grandfather->_right
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED) {
parent->_col = 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;
}
旋转操作和 AVL 树基本一样，只是不需要更新平衡因子。但要注意父指针的更新！
左单旋：
template<class K, class V>
void RBTree<K, V>::RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 1. 将 subRL 链接到 parent 的右
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
// 2. 记录 parent 的原父节点
Node* pParent = parent->_parent;
// 3. subR 的左指向 parent
subR->_left = parent;
parent->_parent = subR;
// 4. 处理 subR 与上层节点的链接
if (parent == _root) {
// parent 是根节点
_root = subR;
subR->_parent = nullptr;
} else {
// parent 是局部子树
if (pParent->_left == parent)
pParent->_left = subR;
else
pParent->_right = subR;
subR->_parent = pParent;
}
// 注意：不需要更新平衡因子！
}
右单旋：
template<class K, class V>
void RBTree<K, V>::RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 1. 将 subLR 链接到 parent 的左
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
// 2. 记录 parent 的原父节点
Node* pParent = parent->_parent;
// 3. subL 的右指向 parent
subL->_right = parent;
parent->_parent = subL;
// 4. 处理 subL 与上层节点的链接
if (parent == _root) {
_root = subL;
subL->_parent = nullptr;
} else {
if (pParent->_left == parent)
pParent->_left = subL;
else
pParent->_right = subL;
subL->_parent = pParent;
}
}
与普通二叉搜索树相同，时间复杂度 O(logN)。
template<class K, class V>
typename RBTree<K, V>::Node* RBTree<K, V>::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; // 没找到
}
验证一棵树是否是红黑树，不能简单地检查"最长路径≤最短路径的 2 倍"，因为即使满足这个条件，也可能不满足颜色规则。必须严格检查 4 条规则。
template<class K, class V>
bool RBTree<K, V>::IsBalance() {
if (_root == nullptr) return true;
// 规则 2：检查根节点是否为黑色
if (_root->_col == RED) {
cout << "错误：根节点为红色" << endl;
return false;
}
// 规则 4：找一个参考值（最左路径的黑色节点数）
int refNum = 0;
Node* cur = _root;
while (cur) {
if (cur->_col == BLACK) refNum++;
cur = cur->_left;
}
// 递归检查每条路径
return Check(_root, 0, refNum);
}
template<class K, class V>
bool RBTree<K, V>::Check(Node* root, int blackNum, const int refNum) {
if (root == nullptr) {
// 走到空节点，说明一条路径走完了
// 规则 4：检查黑色节点数是否等于参考值
if (blackNum != refNum) {
cout << "错误：黑色节点数量不相等，当前路径有" << blackNum << "个，参考值为" << refNum << endl;
return false;
}
return true;
}
// 规则 3：检查是否有连续的红色节点
// 技巧：检查红色节点的父节点（孩子有两个不好检查，检查父亲更方便）
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);
}
template<class K, class V>
void RBTree<K, V>::_InOrder(Node* root) {
if (root == nullptr) return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << " ";
_InOrder(root->_right);
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online