Chapter 53: Mini Red-Black Tree
核心问题与阅读主线
有序关联容器需要在动态增删下维持对数级查找与稳定迭代器语义,红黑树通过局部旋转与颜色重染把全局平衡压缩成可局部修复的不变量。本章围绕节点与 header_ 哨兵布局,拆解旋转、插入/删除修复、中序迭代器与 lower_bound 之间的指针和黑高因果链。
全章共用场景样本
本章的贯穿材料是简化唯一键树 mini_rb_tree<Key, Value, Compare> 与操作序列“插入 10, 5, 15, 7, 6 → 删除 5 → 查询 lower_bound(8)”,用以模拟 std::map / std::set 常见实现中的节点、header_ 哨兵与修复主干(C++ 标准仅约束 ordered associative containers 的语义与复杂度,并未强制规定底层必须为红黑树)。
排查顺序
验证红黑树状态是否合法应按固定顺序逐层检查:1) BST 键值顺序;2) parent 与 left / right 双向指针;3) header_ 的 root / leftmost / rightmost 端点;4) 节点颜色与黑高;5) 迭代器端点与异常安全边界。
53.1 node 结构
红黑树节点把拓扑链接与键值数据拆成两层:rb_node_base 仅保存颜色与父子指针,rb_node<Key, Value> 再追加元素本身。容器另持一个 header_ 哨兵复用 rb_node_base,无需构造假 Value 即可统一表示空树、根节点、begin() 与 end()。
#include <cassert>
#include <functional>
#include <utility>
namespace mini {
enum class rb_color { red, black };
struct rb_node_base {
rb_color color = rb_color::red;
rb_node_base* parent = nullptr;
rb_node_base* left = nullptr;
rb_node_base* right = nullptr;
};
template <class Key, class Value>
struct rb_node : rb_node_base {
Key key;
Value value;
template <class K, class V>
rb_node(K&& k, V&& v)
: key(std::forward<K>(k)), value(std::forward<V>(v)) {}
};
} // namespace mini
容器独占节点内存与元素生命周期,节点指针本身不带所有权语义;因此删除节点时必须先将其从树结构摘除,再析构并释放对象。mini_rb_tree 通过 header_ 统一收敛整棵树的边界入口:
template <class Key, class Value, class Compare = std::less<Key>>
class mini_rb_tree {
using base = mini::rb_node_base;
using node = mini::rb_node<Key, Value>;
base header_{};
std::size_t size_ = 0;
Compare comp_{};
base* root() noexcept { return header_.parent; }
const base* root() const noexcept { return header_.parent; }
base*& root_ref() noexcept { return header_.parent; }
static node* as_node(base* p) noexcept {
return static_cast<node*>(p);
}
void reset_header() noexcept {
header_.color = mini::rb_color::black;
header_.parent = &header_;
header_.left = &header_;
header_.right = &header_;
}
public:
mini_rb_tree() { reset_header(); }
};
| 结构组件 | 保存内容 | header_ / 空树状态 | 核心职责 |
|---|---|---|---|
rb_node_base | color、parent、left、right | 哨兵与迭代器的共用基类 | 表达非所有权的双向树链接,供旋转与遍历复用 |
rb_node<Key, Value> | 继承 base,增加 key、value | 仅真实节点构造此类型 | 承载元素生命周期,解引用时由 as_node 强转 |
header_ 哨兵 | 复用 rb_node_base(恒为黑色) | parent/left/right 均指向 &header_ | 依次指向 root、最小节点(begin())与最大节点(--end()) |
边界与误区
header_ 消除空指针分支的代价是所有插入、删除与清空操作都必须同步维护它的三个指针。节点颜色仅参与平衡修复、绝不参与 Compare 比较,而对 header_ 解引用属于调用错误。
53.2 rotate_left
rotate_left(x) 用于降低右侧局部高度或把红色冲突向左侧转移,前提是 x 存在真实右孩子 y(y != &header_)。旋转只重连 x、y 与夹在二者之间的子树 y->left,不改变中序遍历顺序。
void rotate_left(base* x) noexcept {
base* y = x->right;
assert(y != &header_);
x->right = y->left;
if (y->left != &header_) {
y->left->parent = x;
}
y->parent = x->parent;
if (x == root()) {
root_ref() = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
指针提交必须按以下三步顺序执行,否则可能临时丢失 y->left 并导致 parent 链断裂或遍历跳过节点:
- 接管中间子树:将
y->left挂到x->right,若非&header_则把其parent改为x。 - 替换父链接:让
y->parent接替x->parent,并更新root_ref()(当x == root())或原父节点对应子指针。 - 落下旧根:设置
y->left = x与x->parent = y,完成局部旋转。
关键事实
rotate_left 不分配内存、不比较 key、不构造元素,因此严格 noexcept——这保证修复阶段不会在树处于半平衡状态时抛出异常。由于中序顺序不变,左旋仅在 x == root() 时更新 root_ref(),无需调整 header_.left 与 header_.right。
53.3 rotate_right
rotate_right(x) 是左旋的镜像操作:前提是 x 存在真实左孩子 y,旋转后 y 顶替 x 成为局部根,x 退为 y->right,原 y->right 挂为 x->left。
void rotate_right(base* x) noexcept {
base* y = x->left;
assert(y != &header_);
x->left = y->right;
if (y->right != &header_) {
y->right->parent = x;
}
y->parent = x->parent;
if (x == root()) {
root_ref() = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
| 旋转方向 | 输入前提 | 中间子树转移 | 旋转后局部父子关系 | header_ 影响 |
|---|---|---|---|---|
rotate_left(x) | y = x->right != &header_ | y->left 移至 x->right | y 顶替 x,x 成为 y->left | 仅 x == root() 时更新 root_ref() |
rotate_right(x) | y = x->left != &header_ | y->right 移至 x->left | y 顶替 x,x 成为 y->right | 仅 x == root() 时更新 root_ref() |
下图中 A、B、C 均为子树而非单个节点,旋转前后相对键序始终保持 A < y < B < x < C:
核心判断
旋转的最小验收标准是指针可逆性:对局部先执行 rotate_right(x),再对新父节点执行 rotate_left(y)(或反向组合),所有父子链接必须完全还原;该测试无需节点颜色参与,因为平衡重染属于 insert_fixup 与 erase_fixup 的职责。
53.4 insert
insert_unique 分两段推进:先沿 root() 按 BST 规则定位空子位置并分配红色新节点,再把节点接入树结构并调用 insert_fixup。比较 key 与构造节点均发生在修改树指针之前,因此异常发生时树状态完全不受污染,接入后的平衡修复也无需再处理构造失败。
template <class K, class V>
std::pair<base*, bool> insert_unique(K&& key, V&& value) {
base* parent = &header_;
base* current = root();
bool insert_left = true;
while (current != &header_) {
parent = current;
node* current_node = as_node(current);
if (comp_(key, current_node->key)) {
current = current->left;
insert_left = true;
} else if (comp_(current_node->key, key)) {
current = current->right;
insert_left = false;
} else {
return {current, false};
}
}
node* fresh = new node(std::forward<K>(key), std::forward<V>(value));
fresh->color = mini::rb_color::red;
fresh->left = &header_;
fresh->right = &header_;
fresh->parent = parent;
if (parent == &header_) {
root_ref() = fresh;
header_.left = fresh;
header_.right = fresh;
} else if (insert_left) {
parent->left = fresh;
if (parent == header_.left) {
header_.left = fresh;
}
} else {
parent->right = fresh;
if (parent == header_.right) {
header_.right = fresh;
}
}
++size_;
insert_fixup(fresh);
return {fresh, true};
}
新节点默认染红是为了避免破坏各路径的黑高(节点到叶端点路径上的黑节点数):
- 黑父直通:若父节点为黑色,插入后所有红黑性质依然成立,无需修复。
- 红父冲突:若父节点为红色,则违反“红节点的孩子必须为黑”,交由
insert_fixup修复。 - 贯穿序列追踪:插入
10, 5, 15后形成黑根10与红孩子5、15;再插入7时因父5、叔15均红而触发变色(5和15改黑,10改红并最终被根强制改黑);继续插入6则落入黑叔旋转分支。
关键事实
红黑树高度受黑高与红父子约束限制为对数级,搜索、接入与上溯修复均只沿单条祖先链移动;类似地,std::map::lower_bound 等有序接口的对数复杂度承诺也建立在此树高边界之上,语义细节可参见 cppreference 的 map::lower_bound 页面。
53.5 insert_fixup
insert_fixup(z) 只解决一个不变量冲突:新接入或上移的红节点 z 拥有红色父节点(z != root() && z->parent->color == red)。循环持续把冲突向上推或通过局部旋转消化,结束时强制把 root() 染黑。
void insert_fixup(base* z) noexcept {
while (z != root() && z->parent->color == mini::rb_color::red) {
base* parent = z->parent;
base* grand = parent->parent;
if (parent == grand->left) {
base* uncle = grand->right;
if (uncle->color == mini::rb_color::red) {
parent->color = mini::rb_color::black;
uncle->color = mini::rb_color::black;
grand->color = mini::rb_color::red;
z = grand;
} else {
if (z == parent->right) {
z = parent;
rotate_left(z);
parent = z->parent;
grand = parent->parent;
}
parent->color = mini::rb_color::black;
grand->color = mini::rb_color::red;
rotate_right(grand);
}
} else {
base* uncle = grand->left;
if (uncle->color == mini::rb_color::red) {
parent->color = mini::rb_color::black;
uncle->color = mini::rb_color::black;
grand->color = mini::rb_color::red;
z = grand;
} else {
if (z == parent->left) {
z = parent;
rotate_right(z);
parent = z->parent;
grand = parent->parent;
}
parent->color = mini::rb_color::black;
grand->color = mini::rb_color::red;
rotate_left(grand);
}
}
}
root()->color = mini::rb_color::black;
}
源码中的左右镜像分支可统一压缩为“看 uncle 颜色、判折线与直线”三类情形:
uncle 颜色 | z 与 parent 形状 | 旋转动作 | 变色结果 | 循环是否继续 |
|---|---|---|---|---|
| 红色(真实节点) | 任意 | 不旋转,z 上移至 grand | parent / uncle 改黑,grand 改红 | 是(继续检查 grand) |
黑色(含 &header_) | 折线(内侧孩子) | 先绕 parent 反方向旋转成直线 | 转入下方直线分支 | 否(经直线分支后终止) |
黑色(含 &header_) | 直线(外侧孩子) | 绕 grand 向 uncle 侧单旋 | parent 改黑,grand 改红 | 否(新局部根为黑) |
贯穿序列插入 6 时,5 -> 7 -> 6 形成右左折线且叔叔 5->left 为 &header_(黑色),修复按三步收敛:
- 对
7执行rotate_right(7),将局部拉直为5 -> 6 -> 7。 - 将新父节点
6染黑、祖父5染红,并执行rotate_left(5)。 6(B)升至局部根、左右分别挂5(R)与7(R),红父子冲突终止。
边界与误区
uncle 为 &header_ 时依赖哨兵本身恒为黑色这一不变量,才能省去空指针判断并直接进入旋转分支;因此所有真实叶节点的空孩子指针必须指向 &header_ 而非 nullptr。
53.6 erase
erase 的难点在于删除黑色节点会造成对应路径黑高减一:若实际移出原位置的节点 y 为红色,黑高不受影响;若 y 为黑色且树非空,则需通过 erase_fixup 沿父链吸收或旋转重分这份黑高缺口。
实现拆分为链接替换与黑高修复两层:transplant 只负责重连父子指针,不改动颜色与极值端点;erase_node 定位实际移出节点 y(双孩子时取右子树最小后继 minimum(z->right),并将 y 重连到 z 位置以保地址稳定),再维护 header_ 并决定是否修复。
void transplant(base* old_node, base* replacement) noexcept {
base* parent = old_node->parent;
if (old_node == root()) {
root_ref() = replacement;
} else if (old_node == parent->left) {
parent->left = replacement;
} else {
parent->right = replacement;
}
if (replacement != &header_) {
replacement->parent = parent;
}
}
base* minimum(base* x) const noexcept {
while (x->left != &header_) {
x = x->left;
}
return x;
}
void erase_node(base* z) {
base* y = z;
base* x = &header_;
base* x_parent = z->parent;
mini::rb_color y_original_color = y->color;
if (z->left == &header_) {
x = z->right;
x_parent = z->parent;
transplant(z, z->right);
} else if (z->right == &header_) {
x = z->left;
x_parent = z->parent;
transplant(z, z->left);
} else {
y = minimum(z->right);
y_original_color = y->color;
x = y->right;
if (y->parent == z) {
x_parent = y;
} else {
x_parent = y->parent;
transplant(y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (header_.left == z) {
header_.left = (z->right == &header_) ? z->parent : minimum(z->right);
}
if (header_.right == z) {
header_.right = (z->left == &header_) ? z->parent : maximum(z->left);
}
if (y_original_color == mini::rb_color::black && root() != &header_) {
erase_fixup(x, x_parent);
}
delete as_node(z);
--size_;
if (size_ == 0) {
reset_header();
}
}
上例假定 maximum 与 minimum 对称实现。在贯穿序列插入 10, 5, 15, 7, 6 后删除 5:
5是红色叶节点且正为header_.left,因y_original_color为红故无需erase_fixup。- 由于
5->right == &header_,header_.left随删除同步更新为5->parent(即6)。
下图汇总黑高缺口 x 与其兄弟节点 sibling 的四类修复迁移;循环持续到 x 变为红色(直接染黑即可吸收缺口)或升至 root() 时结束:
由于 erase_node 仅调整节点间指针而不搬移未删节点的内存地址,除被删除元素外其余元素的迭代器与引用全部保持有效,这与 cppreference 的 map::erase 页面 描述的失效语义一致。
边界与误区
erase_fixup(x, x_parent) 必须显式传入 x_parent:当顶上来的替代孩子 x 是 &header_ 时,header_.parent 仍指向 root() 而非 x 的父节点,若直接读取 x->parent 将找错兄弟节点并破坏树结构。此外,修复阶段只改指针与颜色,严禁触发 key 比较或元素构造/析构。
53.7 iterator
红黑树 iterator 仅持有当前节点 current_ 与哨兵 header_,按 key 中序推进:++it 走 successor,--it 走 predecessor,header_ 作为 past-the-end 边界同时充当 --end() 的跳转入口。
static base* successor(base* x, base* header) noexcept {
if (x->right != header) {
x = x->right;
while (x->left != header) {
x = x->left;
}
return x;
}
base* y = x->parent;
while (y != header && x == y->right) {
x = y;
y = y->parent;
}
return y;
}
static base* predecessor(base* x, base* header) noexcept {
if (x == header) {
return header->right;
}
if (x->left != header) {
x = x->left;
while (x->right != header) {
x = x->right;
}
return x;
}
base* y = x->parent;
while (y != header && x == y->left) {
x = y;
y = y->parent;
}
return y;
}
| 移动方向 | 特殊哨兵处理 | 存在目标子树时 | 无目标子树时 |
|---|---|---|---|
successor(++it) | 不得对 end() 递增 | 进入 x->right 并一路向左至最小节点 | 沿 parent 向上至首个将当前路径挂在左侧的祖先 |
predecessor(--it) | x == header_ 时直接返回 header_->right | 进入 x->left 并一路向右至最大节点 | 沿 parent 向上至首个将当前路径挂在右侧的祖先 |
class iterator {
base* current_ = nullptr;
base* header_ = nullptr;
public:
using difference_type = std::ptrdiff_t;
using value_type = std::pair<const Key, Value>;
using iterator_category = std::bidirectional_iterator_tag;
iterator& operator++() noexcept {
current_ = successor(current_, header_);
return *this;
}
iterator& operator--() noexcept {
current_ = predecessor(current_, header_);
return *this;
}
bool operator==(const iterator& other) const noexcept {
return current_ == other.current_;
}
};
关键事实
红黑树迭代器属于双向迭代器(bidirectional_iterator_tag):单步移动最坏需沿祖先链走对数步,但完整遍历 begin() 到 end() 时每条树边最多经过两次,均摊总成本为线性。只要 erase 正确修复 parent 链与 header_ 端点,插入、旋转与非目标节点删除均不会破坏既有迭代器的地址有效性。
53.8 lower_bound
lower_bound_node(key) 返回第一个不小于 key 的节点位置。搜索从 root() 出发,每次遇到 !comp_(current_node->key, key) 即记录当前节点为 candidate 并转向左子树寻找更小候选;否则直接转向右子树。
base* lower_bound_node(const Key& key) const {
base* current = const_cast<base*>(root());
base* candidate = const_cast<base*>(&header_);
while (current != &header_) {
const node* current_node = static_cast<const node*>(current);
if (!comp_(current_node->key, key)) {
candidate = current;
current = current->left;
} else {
current = current->right;
}
}
return candidate;
}
在贯穿序列构建的树中查询 lower_bound(8) 的收敛路径如下(无合格节点时 candidate 保持 &header_ 即 end()):
- 根节点
10不小于8,记录candidate = 10后左转到6。 6与其右孩子7均小于8,相继右转至&header_,循环结束并返回10。
边界与误区
!comp_(current_key, key) 在严格弱序下同时覆盖“等价”与“大于”两种情况。该算法依赖两条前提:树链接满足 BST 中序有序,且 Compare 在容器生命周期内提供稳定严格弱序;若外部篡改 key 或比较器依赖可变状态,搜索路径就会失配并返回错误候选。
最小自检任务
下面的代码片段来自本章的 mini red-black tree 思路。假设 &header_ 作为黑色哨兵叶端点,空孩子均指向 &header_,comp_ 为稳定严格弱序比较器:
mini_rb_tree<int, int> tree;
tree.insert_unique(10, 100);
tree.insert_unique(5, 50);
tree.insert_unique(15, 150);
tree.insert_unique(7, 70);
tree.insert_unique(6, 60);
auto first = tree.lower_bound_node(8);
tree.erase_node(tree.lower_bound_node(5));
auto second = tree.lower_bound_node(8);
请逐项判断以下三个问题:
- 插入
6时为什么需要先局部右旋再围绕祖父左旋? lower_bound_node(8)为什么会返回 key 为10的节点?- 删除 key 为
5的节点后,为什么指向 key 为10的迭代器仍然保持有效?
本章知识点总结
- 节点与哨兵布局
rb_node_base剥离链接与颜色以复用服务迭代器和header_哨兵,header_分别指向root、begin()与--end(),空树时三者均回指自身。 - 所有权边界
容器独占节点内存与元素生命周期,节点指针仅表示非所有权链接,
erase必须先摘除节点链接再delete。 - 旋转与异常安全
rotate_left与rotate_right仅重连局部三角指针并保持中序顺序,因不分配内存且不比较 key 而严格noexcept,仅在x == root()时更新root_ref()。 - 插入与两类修复
新节点默认染红以保留黑高;
insert_fixup遇红叔则变色上移检查点,遇黑叔(含&header_)则经折线转直线与祖父单旋后重染终止。 - 删除与显式父参
erase_node按实际移出节点y的原色决定是否触发erase_fixup;显式传递x_parent是因为替代孩子x为&header_时,header_.parent仍指向root而非x的父节点。 - 迭代器移动与稳定
successor与predecessor按中序规则跨子树或沿parent爬升;插入与旋转保留已有节点地址,删除仅使目标节点迭代器失效。 - 候选搜索收敛
lower_bound依赖稳定的严格弱序与合法 BST 链接,遇到!comp_(node->key, key)更新candidate并左转收缩,无匹配时返回&header_。