红黑树插入修复全记录:从旋转到颜色调整
红黑树的五条规则不算复杂,但动手实现插入时,修复逻辑会一直向上蔓延。下面结合 C++ 代码,把关键步骤走一遍。
五条规则
- 节点非红即黑。
- 根节点黑色。
- 红色节点的子节点必须黑色(不能连续红)。
- 任意节点到其叶子节点的路径上黑色节点数相同。
- 叶子(NIL)视为黑色。
这些约束靠颜色和旋转维持,保证树高 O(log n),从而查找、插入、删除最坏也是对数级。

高度边界
黑色高度 bh 是从根到叶路径上的黑节点数。最短路径全黑,长度 bh;最长路径红黑交替,长度 2*bh。因此树高 ≤ 2 log(n+1),这就是 O(log n) 的来源。

节点结构
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(连续红),局部处理就行。
修复的核心在于叔叔节点的颜色:
- 叔叔红色:父、叔变黑,祖父变红,当前节点跳到祖父继续检查。
- 叔叔黑色或不存在:需要旋转。根据节点、父、祖父的位置关系,可能单旋或双旋,并配合变色。
下面这段代码同时处理了左右对称的情况:
bool Insert( 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;
;
}





