从零实现C++红黑树：手写mymap与myset容器实战
1. 项目概述：从STL容器到自研轮子
在C++开发里，
std::map
和
std::set
是再熟悉不过的容器了，它们底层通常由红黑树实现，提供了稳定的O(log n)的查找、插入和删除性能。但不知道你有没有想过，如果自己动手，从零开始封装一个红黑树，并基于它实现自己的
mymap
和
myset
，会是怎样一番体验？这绝不仅仅是“重复造轮子”，而是一次深入理解关联式容器核心机制、掌握复杂数据结构实现细节的绝佳机会。我最近就完整地走了一遍这个流程，从红黑树节点的定义、五大性质的维护，到迭代器的封装、模板化的键值分离设计，最后打磨出接口与STL高度兼容的自定义容器。这个过程里踩的坑、获得的启发，远比单纯调用
std::map
要多得多。无论你是想夯实C++和数据结构基础，应对深度技术面试，还是为特定场景定制高性能容器，这篇文章记录的实战经验和思考都能给你提供一份可靠的“地图”。
2. 红黑树核心原理与设计抉择
红黑树，本质上是一种自平衡的二叉查找树。它在普通BST的基础上，为每个节点增加了一个颜色属性（红或黑），并通过一组约束规则来确保树在动态插入和删除后，能大致保持平衡，从而避免退化成链表的最坏情况。理解这些规则，是我们实现它的第一步。
2.1 红黑树的五项基本性质
红黑树之所以能工作，全靠这五条铁律在维持平衡。我们的所有操作都必须以维护这些性质为前提：
- 每个节点非红即黑 。这是基础。
- 根节点是黑色的 。这是一个重要的边界条件。
- 所有叶子节点（NIL节点）都是黑色的 。在实现中，我们通常用一个统一的、黑色的、空的哨兵节点来代表所有叶子，这能简化边界判断。
- 红色节点的两个子节点必须是黑色的 。这意味着红色节点不能连续出现，确保了从任一节点到其子孙叶子节点的所有路径上，红色节点的数量是受控的。
- 从任一节点到其每个叶子节点的所有简单路径上，包含相同数量的黑色节点 。这个性质是红黑树平衡的关键，它保证了最长路径（红黑交替）不会超过最短路径（全黑）的两倍。
性质4和5共同作用，约束了树的高度。假设从根到叶子的黑色节点数为B（黑高），那么最短路径长度就是B（全黑），最长路径长度不超过2B（红黑相间）。因此树的高度h满足：B <= h <= 2B。由于含有N个节点的红黑树，其黑高至少为log₂(N+1)/2，所以树高h始终是O(log N)级别。
2.2 节点与树结构的基础设计
在编码之前，我们需要先设计好节点和树骨架。这里有几个关键设计点需要决定。
节点结构体设计
：
一个典型的红黑树节点需要包含：键（Key）、值（Value，对于
set
，值就是键本身）、颜色、指向父节点和左右子节点的指针。我选择使用模板来让节点能适应不同的数据类型。
enum Color { RED, BLACK };
template <typename T>
struct RBTreeNode {
T data; // 存储的数据。对于map是pair<const Key, Value>，对于set就是Key。
Color color;
RBTreeNode* parent;
RBTreeNode* left;
RBTreeNode* right;
// 构造函数，新节点默认红色（方便插入调整）
RBTreeNode(const T& val, Color c = RED)
: data(val), color(c), parent(nullptr), left(nullptr), right(nullptr) {}
};
这里有一个细节：
data
的类型是
T
。对于
myset
，
T
就是
Key
；对于
mymap
，
T
将是
std::pair<const Key, Value>
。使用
const Key
是为了模仿STL中
map::iterator
解引用得到的是一个
pair<const Key, Value>
，防止用户通过迭代器修改键值，破坏树的有序性。
哨兵NIL节点的处理
：
如何处理空叶子？一种常见且高效的做法是，让整棵树共享一个全局的、静态的黑色哨兵节点。所有真实的叶子节点（
left
或
right
为空）都指向这个哨兵，根节点的父节点也指向它。这样做的好处是，我们不需要在每次操作中判断指针是否为空，而是统一判断是否等于
NIL
，代码更简洁，也避免了空指针解引用。
// 在RBTree类内部定义一个静态哨兵节点
static RBTreeNode<T>* NIL;
// 在类外初始化
template <typename T>
RBTreeNode<T>* RBTree<T>::NIL = new RBTreeNode<T>(T(), BLACK); // 数据部分用默认值构造
// 在构造函数中，初始化根节点指向NIL
template <typename T>
RBTree<T>::RBTree() : root(NIL) {}
模板化设计：一棵树支撑两种容器
我们的目标是实现
mymap
和
myset
。它们底层都是红黑树，但存储的数据类型不同。一个优雅的设计是，先实现一个通用的、模板化的红黑树类
RBTree
，它接受一个数据类型
T
。然后，让
mymap
和
myset
分别封装这个
RBTree
，但传入不同的
T
。
-
myset<Key>：内部包含一个RBTree<Key>。 -
mymap<Key, Value>：内部包含一个RBTree<std::pair<const Key, Value>>。 这样，红黑树的核心逻辑（旋转、插入修复、删除修复）只需要写一份，实现了代码复用。
3. 核心操作实现：旋转、插入与删除修复
红黑树的所有魔法都藏在插入和删除后的修复逻辑里，而修复的基础是旋转操作。
3.1 左旋与右旋：平衡的微观调整
旋转是局部调整子树结构而不破坏二叉查找树性质的操作。它改变了节点间的父子关系，但保持了中序遍历序列不变。
左旋 (Left Rotate)
：围绕节点
x
进行。假设
x
有一个右孩子
y
。左旋后，
y
成为子树的新根，
x
成为
y
的左孩子，
y
原来的左孩子成为
x
的右孩子。
template <typename T>
void RBTree<T>::leftRotate(RBTreeNode<T>* x) {
RBTreeNode<T>* y = x->right; // 设定y是x的右孩子
x->right = y->left; // 将y的左子树变为x的右子树
if (y->left != NIL) {
y->left->parent = x;
}
y->parent = x->parent; // 连接y与x的父节点
if (x->parent == NIL) {
root = y; // 如果x是根，则y成为新根
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x; // 将x放在y的左边
x->parent = y;
}
右旋 (Right Rotate)
：是左旋的对称操作，围绕节点
y
进行，使其左孩子
x
上升。
关键理解 ：旋转操作只涉及常数个指针的修改，时间复杂度O(1)。它不关心节点的颜色，也不直接修复红黑性质，而是为后续的重新着色改变拓扑结构，是修复过程的“搬运工”。
3.2 插入操作与修复：情况拆解
插入新节点
z
的第一步和普通BST一样：找到合适的位置，将其作为红色叶子节点挂上去。因为新节点是红色，可能违反性质2（根为黑）或性质4（红节点不能有红孩子）。性质5（黑高相同）不会被破坏，因为新增的红色节点不影响任何路径上的黑色节点数。
插入修复函数
insertFixup
的目标就是通过重新着色和旋转，消除连续红色节点，同时保证黑高不变。修复过程主要关注
z
的父节点和叔父节点的颜色。经典算法将情况分为三类（假设父节点是祖父节点的左孩子，右孩子的情况对称）：
情况1：叔父节点是红色
。
此时，祖父节点一定是黑色。我们将父节点和叔父节点都染黑，祖父节点染红。这样，以祖父节点为根的子树恢复了性质4，但祖父节点变红可能使其与它的父节点形成新的双红冲突。于是，我们把
z
指针上移到祖父节点，把问题向上传递。
黑(G) 红(G)
/ \ / \
红(P) 红(U) -> 黑(P) 黑(U)
/ /
红(z) 红(z)
情况2：叔父节点是黑色，且z是父节点的右孩子
。
我们可以通过一次左旋，将情况转化为情况3。旋转后，原来的父节点
P
变成了
z
的左孩子，
z
上升。
黑(G) 黑(G)
/ \ / \
红(P) 黑(U) -> 红(z) 黑(U)
\ /
红(z) 红(P)
情况3：叔父节点是黑色，且z是父节点的左孩子
。
这是可以一次性修复的情况。我们将父节点
P
染黑，祖父节点
G
染红，然后对
G
进行一次右旋。旋转后，
P
成为子树的新根（黑色），
G
成为其右孩子（红色），
U
保持不变。这样，局部子树完全满足所有性质，并且因为新根
P
是黑色，不会把红色冲突继续向上传递。
黑(G) 黑(P)
/ \ / \
红(P) 黑(U) -> 红(z) 红(G)
/ \
红(z) 黑(U)
实操心得 ：在实现
insertFixup时，一定要先处理好对称情况（父节点是右孩子）。一个清晰的写法是，在循环开始时，根据父节点是祖父的左孩子还是右孩子，将代码分成两个完全对称的大块。每一块内部再按上述三种情况处理。这样可以避免逻辑缠绕，代码更易读、易调试。
3.3 删除操作与修复：更复杂的博弈
删除比插入更复杂，因为删除一个节点可能会减少某条路径上的黑色节点数，破坏性质5。我们首先用BST的标准删除逻辑找到实际被删除的节点
y
和它的替代者
x
。红黑树的删除修复，核心是围绕替代者
x
进行的，目标是弥补因为删除
y
而可能造成的“黑色赤字”。
删除逻辑简述 ：
-
如果
y（待删除节点）少于两个孩子，则直接用其唯一的孩子（或NIL）x替代它。 -
如果
y有两个孩子，则找到它的中序后继z（右子树中的最小节点），将z的数据复制到y，然后问题转化为删除节点z（此时z一定最多只有一个孩子）。 -
记录下被删除节点
y的颜色。如果y是黑色，那么删除它就会导致经过x的路径黑高减少1，需要调用deleteFixup(x)来修复。
删除修复的四种情况
：
修复函数
deleteFixup
的目标是让
x
“额外增加一层黑色”（可以是红+黑，或黑+黑），并通过旋转和变色，将这层“额外黑色”沿着树向上推，直到：1)
x
指向一个红黑节点（将其染黑即可）；2)
x
指向根节点（直接移除额外黑色）；3) 通过旋转和变色完成修复。
情况围绕
x
（当前节点）是其父节点的左孩子展开（右孩子对称）。设
w
为
x
的兄弟节点。
情况1：兄弟节点w是红色
。
此时父节点一定是黑色。我们将父节点染红，兄弟节点染黑，然后对父节点进行一次左旋。旋转后，
x
的新兄弟节点是原来
w
的左孩子，它一定是黑色。这样就将情况1转化为了情况2、3或4。
黑(P) 红(w)
/ \ / \
黑(x) 红(w) -> 黑(P) 黑(B)
/ \ / \
黑(A) 黑(B) 黑(x) 黑(A)
情况2：兄弟节点w是黑色，且w的两个孩子都是黑色
。
我们可以将
w
染红，这样从
P
出发，经过
w
的路径黑高也减少了1，与经过
x
的路径持平。于是，“额外黑色”的问题从
x
转移到了其父节点
P
。将
x
指针上移到
P
，继续循环。
?(P) ?(P) [+额外黑]
/ \ / \
黑(x) 黑(w) -> 黑(x) 红(w)
/ \ / \
黑(A) 黑(B) 黑(A) 黑(B)
情况3：兄弟节点w是黑色，w的左孩子是红色，右孩子是黑色
。
将
w
染红，
w
的左孩子染黑，然后对
w
进行一次右旋。这会将情况3转化为情况4。
?(P) ?(P)
/ \ / \
黑(x) 黑(w) -> 黑(x) 黑(A)
/ \ \
红(A) 黑(B) 红(w)
\
黑(B)
情况4：兄弟节点w是黑色，w的右孩子是红色
。
这是可以终止循环的情况。将
w
的颜色设为父节点
P
的颜色，将
P
和
w
的右孩子都染黑，然后对
P
进行一次左旋。操作完成后，树的性质得以恢复，我们可以将
x
设为根节点以结束循环。
?(P) ?(w)
/ \ / \
黑(x) 黑(w) -> 黑(P) 黑(B)
/ \ / \
?(A) 红(B) 黑(x) ?(A)
踩坑记录 ：删除修复是最容易出错的部分。务必在纸上画出每一种情况的树形图，跟着代码走一遍指针和颜色的变化。特别注意，在情况2中，如果父节点
P原来是红色，那么将其染黑（因为附加了额外黑色）后，红黑性质就完全恢复了，可以退出循环。这是循环终止的一个重要条件。
4. 迭代器封装与容器接口设计
一个完整的容器必须提供迭代器，用于遍历元素。红黑树的中序遍历（左-根-右）恰好能按键的顺序输出元素，这正是
map
和
set
有序性的来源。
4.1 迭代器的实现要点
迭代器本质上是一个智能指针，它需要支持
*
（解引用）、
->
（成员访问）、
++
（前移）、
--
（后移）、
==
、
!=
等操作。对于红黑树迭代器，核心难点在于实现高效的
++
和
--
操作，即找到当前节点的中序后继和前驱。
中序后继查找算法 ：
- 如果当前节点有右子树，那么后继是其右子树中的最左节点。
- 如果没有右子树，则需要向上回溯，直到找到一个节点，使得当前节点是其左子树的一部分。那个祖先节点就是后继。
Self& operator++() {
if (node_->right != NIL) {
// 情况1：有右子树，找右子树的最小节点
node_ = minimum(node_->right);
} else {
// 情况2：无右子树，向上找第一个左孩子是它的祖先
RBTreeNode* parent = node_->parent;
while (parent != NIL && node_ == parent->right) {
node_ = parent;
parent = parent->parent;
}
node_ = parent; // 可能指向NIL（end()）
}
return *this;
}
--
操作符是对称的，找中序前驱：有左子树则找左子树最大节点；否则向上找第一个右孩子是它的祖先。
迭代器类的设计
：
我们需要为
RBTree
实现一个内部的
iterator
类和
const_iterator
类。它们通常包含一个指向树节点的指针。为了能让
begin()
返回最小元素，
end()
返回一个特殊位置（通常用
NIL
哨兵表示），我们需要在树类中实现
minimum
和
maximum
函数来查找最左和最右节点。
4.2 mymap与myset的封装策略
有了通用的
RBTree
和它的迭代器，
mymap
和
myset
的封装就清晰了。它们的主要工作是：
-
定义内部类型
：如
key_type,value_type,iterator,const_iterator等，与STL保持一致。 - 组合RBTree实例 ：作为私有成员。
-
转发接口
：将容器的公共接口（如
insert,erase,find,begin,end,size,empty等）的实现，委托给内部的RBTree对象去完成。 -
处理差异
：这是关键。
-
对于
myset：value_type就是Key。插入操作直接插入键值。比较器直接比较键。 -
对于
mymap：value_type是std::pair<const Key, Value>。插入操作需要插入一个pair。为了实现类似map[key] = value的下标运算符，我们需要： a. 在RBTree的find基础上，实现一个insert，它返回一个pair<iterator, bool>，指示插入是否成功以及迭代器位置。 b. 在mymap中重载operator[]。其逻辑是：用key查找，如果找到则返回其对应value的引用；如果没找到，则插入一个pair<key, Value()>（用Value的默认构造函数构造一个值），然后返回这个新值的引用。这正是STLmap下标运算符的行为。
-
对于
// mymap中operator[]的简化实现示例
template <typename Key, typename Value>
Value& mymap<Key, Value>::operator[](const Key& key) {
// 尝试插入一个pair，value部分用默认构造函数初始化
auto ret = tree_.insert(std::make_pair(key, Value()));
// ret.first 是迭代器，ret.second 是bool（是否新插入）
// 返回这个pair中value的引用
return (ret.first)->second;
}
注意事项 ：
mymap的迭代器解引用得到的是pair<const Key, Value>&，其中Key是const，这阻止了用户通过迭代器修改键，保证了树结构的有序性。这是STL的设计，我们也应该遵循。
5. 测试、调试与性能考量
自己实现的数据结构，必须经过严格的测试才能放心使用。
5.1 系统化的测试策略
-
基础功能测试 ：
-
插入测试
：随机插入大量元素，检查
size()是否正确，并用中序遍历检查序列是否有序。 -
查找测试
：对插入的元素进行查找，确保都能找到；查找不存在的元素，确保返回
end()。 - 删除测试 ：随机删除一部分元素，每删除一次，都检查剩余元素是否仍然有序，并遍历树检查红黑树性质是否被破坏。
-
边界测试
：测试插入空容器、删除最后一个元素、重复插入相同键（对于
map应插入失败或更新值，对于set应插入失败）等情况。
-
插入测试
：随机插入大量元素，检查
-
红黑树性质验证 ： 编写一个辅助函数
checkRBProperties，递归检查：- 根节点是否为黑。
- 红色节点的子节点是否为黑。
- 从根到所有叶子的路径，黑色节点数是否相同（黑高一致性）。 在每次插入和删除操作后调用此函数（在调试版本中），可以快速定位违反性质的操作。
-
迭代器与STL兼容性测试 ：
- 测试迭代器的遍历是否与中序遍历结果一致。
-
测试
begin()、end()、rbegin()、rend()（如果实现了反向迭代器）的行为。 -
尝试将你的容器用于STL算法，如
std::find、std::for_each，检查是否编译通过并工作正常。
5.2 调试技巧与常见问题
- 可视化工具 ：在调试时，编写一个简单的打印树结构的函数（按层级或图形化），能直观地看到树是否平衡，颜色是否正确。这比单步调试指针快得多。
- 断言(Assert)的广泛使用 ：在旋转、插入修复、删除修复等核心函数的开头和结尾，加入对红黑树性质的断言检查。一旦断言触发，就能立刻知道在哪一步操作后树的性质被破坏了。
-
内存泄漏检查
：确保析构函数正确递归删除所有节点。对于哨兵
NIL节点，如果是静态成员，需要小心处理其生命周期，避免重复删除。可以使用智能指针管理节点内存，但要注意循环引用问题（节点有指向父节点的指针）。在本次实现中，使用原始指针并手动在析构函数中delete是清晰的，但务必保证正确性。 -
常见Bug
：
-
旋转后父指针未更新
：旋转函数中，某个节点的
parent指针忘记设置，会导致树的结构断裂。 -
NIL哨兵处理不当
：在比较节点时，误用
nullptr而不是NIL，或者忘记将新节点的子节点初始化为NIL。 - 删除修复情况判断错误 ：四种情况的判断条件写错，尤其是对称情况，会导致修复失败，最终破坏树的性质。
-
旋转后父指针未更新
：旋转函数中，某个节点的
5.3 性能分析与优化思考
虽然我们的实现以教学和理解为先，但考虑性能是有意义的。
-
时间复杂度 ：红黑树的插入、删除、查找操作的时间复杂度都是O(log n)，这与STL的
map/set一致。我们的实现是否达到了这个上界？关键在于修复函数insertFixup和deleteFixup。它们虽然包含循环，但最多沿着树向上回溯O(log n)层，且每次循环只做常数时间操作，因此整体仍是O(log n)。 -
空间开销 ：每个节点比普通BST多存储一个颜色信息（通常用一个
bool或枚举），以及父节点指针。父指针是必须的，用于向上回溯。这与大多数STL实现一致。 -
与std::map/std::set的对比 ：
-
功能
：我们的
mymap/myset实现了最核心的接口，但可能缺少一些高级特性，如emplace、extract、merge（C++17）、自定义分配器等。 -
性能
：在算法复杂度上是一致的。但STL的实现经过了极致的优化（如使用全局的
_Rb_tree基类、更精细的内存管理、可能利用平台特定优化），在常数时间上可能更优。 - 调试与学习价值 ：这是自实现容器最大的优势。你可以完全控制内部逻辑，添加性能计数器（如统计旋转次数），或者修改算法进行实验（例如，尝试实现另一种平衡树如AVL树进行对比）。
-
功能
：我们的
-
可能的优化方向 ：
-
迭代器优化
：
++和--操作中的回溯逻辑，在频繁遍历时可能成为瓶颈。一些实现会考虑使用“线索化”的思想，但会增大节点复杂度。 -
内存池
：频繁的节点
new和delete可能带来开销。可以为节点实现一个简单的内存池，一次性分配一大块内存，减少向操作系统申请的次数。 - 移动语义 ：为节点和容器实现移动构造函数和移动赋值运算符，可以在某些场景下避免不必要的拷贝。
-
迭代器优化
：
完成整个项目后，我最大的体会是，数据结构教科书上的算法描述和实际的代码实现之间，隔着无数个细节。指针操作的小心翼翼、边界条件的反复确认、调试时对树形态的绞尽脑汁，都让“红黑树”这三个字从概念变成了肌肉记忆。当你第一次看到自己实现的
mymap
顺利通过所有测试，并能无缝替换一个小程序中的
std::map
时，那种成就感是无可替代的。这个项目不仅让我彻底搞懂了红黑树，更让我对C++的模板、迭代器、STL设计哲学有了更深的理解。如果你正在学习C++和数据结构的交叉领域，我强烈建议你关闭这篇博客，打开编辑器，从定义一个
RBTreeNode
开始，亲手实现一遍。过程中遇到的每一个问题，都会成为你技术栈里最扎实的一块砖。
更多推荐
7
0- 0
已为社区贡献55条内容
所有评论(0)