Skip to main content

Chapter 53: Mini Red-Black Tree

核心问题与阅读主线

本章导读8 个核心小节 · 附自检与总结

有序关联容器需要在动态增删下维持对数级查找与稳定迭代器语义,红黑树通过局部旋转与颜色重染把全局平衡压缩成可局部修复的不变量。本章围绕节点与 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_basecolor、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 链断裂或遍历跳过节点:

  1. 接管中间子树:将 y->left 挂到 x->right,若非 &header_ 则把其 parent 改为 x。
  2. 替换父链接:让 y->parent 接替 x->parent,并更新 root_ref()(当 x == root())或原父节点对应子指针。
  3. 落下旧根:设置 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->righty 顶替 x,x 成为 y->left仅 x == root() 时更新 root_ref()
rotate_right(x)y = x->left != &header_y->right 移至 x->lefty 顶替 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 上移至 grandparent / uncle 改黑,grand 改红是(继续检查 grand)
黑色(含 &header_)折线(内侧孩子)先绕 parent 反方向旋转成直线转入下方直线分支否(经直线分支后终止)
黑色(含 &header_)直线(外侧孩子)绕 grand 向 uncle 侧单旋parent 改黑,grand 改红否(新局部根为黑)

贯穿序列插入 6 时,5 -> 7 -> 6 形成右左折线且叔叔 5->left 为 &header_(黑色),修复按三步收敛:

  1. 对 7 执行 rotate_right(7),将局部拉直为 5 -> 6 -> 7。
  2. 将新父节点 6 染黑、祖父 5 染红,并执行 rotate_left(5)。
  3. 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);

请逐项判断以下三个问题:

  1. 插入 6 时为什么需要先局部右旋再围绕祖父左旋?
  2. lower_bound_node(8) 为什么会返回 key 为 10 的节点?
  3. 删除 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_。