红黑树的核心概念
红黑树本质上是一棵二叉搜索树，每个节点额外增加了一个颜色位（红色或黑色）。通过对路径上颜色的约束，它确保了没有一条路径会比其他路径长出两倍，从而实现了近似平衡。
红黑树的五条规则
- 每个节点非红即黑。
- 根节点必须是黑色。
- 红色节点的子节点必须是黑色（无连续红节点）。
- 任意节点到其所有叶子（NIL）的路径上，包含相同数量的黑色节点。
注：这里提到的叶子通常指外部空节点 NIL，实现时往往省略，但理解概念时需知晓。引入 NIL 是为了准确标识所有路径，但在代码细节中我们通常直接处理 nullptr。
为什么它是高效的？
假设黑高为 bh，最短路径全黑长度为 bh，最长路径一黑一红间隔为 2bh。因此高度 h 满足 bh ≤ h ≤ 2bh。对于 N 个节点，h ≈ logN，增删查改的最坏时间复杂度稳定在 O(logN)。
相比 AVL 树，红黑树对平衡要求稍松，插入时的旋转次数更少，更适合频繁插入的场景。AVL 树通过高度差直观控制平衡，而红黑树通过颜色约束间接实现，两者效率同一档次，但红黑树在工程实践中更常见。
红黑树的实现
节点结构
我们需要记录左右子节点、父节点以及颜色。为了后续旋转方便，父指针必不可少。
enum Colour { RED, BLACK };
template<class K, class V>
struct RBTreeNode {
pair<K, V> _kv;
RBTreeNode* _left;
RBTreeNode* _right;
RBTreeNode* _parent;
Colour _col;
RBTreeNode(const pair<K, V>& kv)
: _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};
插入操作与平衡维护
插入新节点时，默认设为红色。如果父节点是黑色，无需调整；若父节点也是红色，则违反规则 3，需进行旋转或变色修复。我们约定 cur 为当前节点，p 为父节点，g 为祖父节点，u 为叔叔节点。
实际处理时主要分三种情况：
- 变色：叔叔节点存在且为红色。将 p 和 u 变黑，g 变红，然后 g 成为新的 cur 继续向上检查。若 g 是根，最后再将其变回黑色。
- 单旋 + 变色：叔叔不存在或为黑色，且 cur 与 p 同侧（如左左或右右）。以 g 为轴旋转，变色后结束。
- 双旋 + 变色：叔叔不存在或为黑色，且 cur 与 p 异侧（如左右或右左）。先对 p 旋转，再对 g 旋转，最后变色。
核心代码实现
下面是插入函数的完整逻辑，包含了查找位置、插入节点以及后续的平衡维护。注意旋转函数 RotateL/R 需自行实现，逻辑与 AVL 树类似，重点在于指针更新。
bool Insert(const pair<K, V>& kv) {
(_root == ) {
_root = (kv);
_root->_col = BLACK;
;
}
Node* parent = ;
Node* cur = _root;
(cur) {
(cur->_kv.first < kv.first) {
parent = cur;
cur = cur->_right;
} (cur->_kv.first > kv.first) {
parent = cur;
cur = cur->_left;
} {
;
}
}
cur = (kv);
cur->_col = RED;
(parent->_kv.first < kv.first) {
parent->_right = cur;
} {
parent->_left = cur;
}
cur->_parent = parent;
(parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
(parent == grandfather->_left) {
Node* uncle = grandfather->_right;
(uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} {
(cur == parent->_left) {
(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} {
(parent);
(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
;
}
} {
Node* uncle = grandfather->_left;
(uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} {
(cur == parent->_right) {
(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} {
(parent);
(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
;
}
}
}
_root->_col = BLACK;
;
}
