从零实现红黑树：手写C++的set与map容器

1. 项目概述：从STL容器到自研轮子

在C++的日常开发中，std::set和std::map是我们再熟悉不过的伙伴了。它们一个负责管理不重复的集合，一个负责维护键值对映射，底层都依赖一颗高效的红黑树来保证数据的有序性和操作的性能。但你是否曾想过，这颗“黑盒子”里的树究竟是如何工作的？当面试官追问红黑树的插入规则，或是让你手撕一个简单的map时，你是否感到一丝心虚？这正是我们今天要动手解决的核心问题：不依赖STL，从零开始封装一颗红黑树，并用它来实现我们自己的MySet和MyMap。

这个项目的价值远不止于应付面试。通过亲手实现，你会彻底理解关联式容器的核心——平衡二叉搜索树是如何在动态插入删除中维持平衡的；你会看清迭代器、仿函数、模板这些抽象概念是如何协同工作，构建出一个易用且强大的库的；更重要的是，你会获得一种“透视”能力，以后再使用STL容器时，对其性能边界和内部行为将有更精准的预判。整个过程就像拆解一台精密的机械钟表，再把它重新组装起来，其中的齿轮（节点结构）如何咬合，发条（平衡调整）如何运作，都将一目了然。

2. 红黑树核心原理与设计抉择

在动手写代码之前，我们必须把红黑树这颗“心脏”的原理吃透。红黑树并非普通的二叉搜索树，它通过一套简单的规则，在插入和删除时进行局部调整，从而避免了普通BST退化成链表的极端情况，保证了最坏情况下的时间复杂度仍为O(log n)。

2.1 红黑树的五项基本规则

红黑树保持平衡依赖于以下五项核心规则，这就像它的“宪法”，所有操作都必须遵守：

1. 每个节点非红即黑。
2. 根节点是黑色的。
3. 所有叶子节点（NIL节点，即空节点）都是黑色的。
4. 任何相邻的父子节点不能同时为红色（即红色节点的子节点必须是黑色）。
5. 从任一节点到其每个叶子节点的所有简单路径上，包含相同数量的黑色节点（这条规则保证了树的“黑高”一致，是平衡的关键）。

这五条规则约束力很强，尤其是规则4和5，直接决定了插入和删除后调整逻辑的复杂性。规则4限制了红色节点的连续出现，规则5则保证了从根到叶子的最长路径不会超过最短路径的两倍（因为最长路径红黑相间，最短路径可能全是黑节点），从而实现了近似平衡。

2.2 节点结构设计与模板化考量

一颗树的基石是节点。我们的节点设计需要足够通用，以同时支撑set（只存键）和map（存键值对）的需求。

// 节点颜色枚举 enum Colour { RED, BLACK }; // 红黑树节点模板类 template<class T> struct RBTreeNode { RBTreeNode<T>* _left; RBTreeNode<T>* _right; RBTreeNode<T>* _parent; T _data; // 关键！这里存储T类型的数据，对于set是Key，对于map是pair<const Key, Value> Colour _col; RBTreeNode(const T& data) : _left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) // 新节点默认插入为红色，破坏规则的可能性比破坏规则5（黑高）要小，调整起来更简单。 {} };

这里有一个关键设计点：_data的类型是模板参数T。对于MySet<K>，T就是K（键类型）；对于MyMap<K, V>，T就是std::pair<const K, V>。这样，红黑树模板类RBTree就只需要处理一种节点类型T，通过模板和仿函数来提取键进行比较，实现了代码的高度复用。这也是STL源码中采用的经典设计。

2.3 插入操作与平衡调整详解

插入新节点后，可能会破坏红黑树规则，主要集中在规则2（根为黑）和规则4（红节点不能连续）。调整的核心思想是通过旋转和变色，在局部恢复平衡。调整情况主要取决于新节点（N）的父节点（P）和叔叔节点（U）的颜色。

情况一：叔叔节点U存在且为红色。此时，将父节点P和叔叔节点U变为黑色，祖父节点G变为红色。然后将祖父节点G视为新的当前节点，继续向上检查。因为G变红后，可能会和它的父节点形成双红冲突。

情况二：叔叔节点U不存在或为黑色，且新节点N与父节点P的朝向不一致（即P是G的左孩子，N是P的右孩子，或者相反）。此时，我们需要通过一次左旋或右旋，将情况转换为情况三。例如，若P是G的左孩子，N是P的右孩子（LR型），则先对P进行左旋，旋转后N和P的角色互换，变成了LL型（即新节点是父节点的左孩子）。

情况三：叔叔节点U不存在或为黑色，且新节点N与父节点P的朝向一致（即同为左孩子或同为右孩子）。这是调整的最后一步。将父节点P变为黑色，祖父节点G变为红色，然后对祖父节点G进行一次与朝向相反的单旋（如果P是G的左孩子，则对G右旋；反之左旋）。经过这次旋转和变色，该子树的红黑规则得以恢复，并且不会影响整棵树的黑色节点数量。

注意：在实现旋转时，一定要处理好节点父子指针的更新顺序，特别是_parent指针的维护，这是最容易出错的地方。一个实用的技巧是画图，在纸上画出旋转前后节点的连接关系，再转化为代码。

3. 封装红黑树模板类RBTree

有了清晰的原理和节点设计，我们就可以构建红黑树的主干了。RBTree类将封装所有树的操作，并为set和map提供统一的接口。

3.1 类框架与关键成员

template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: // 迭代器等接口声明... bool Insert(const T& data); // ... 其他成员函数 private: Node* _root = nullptr; // KeyOfT 仿函数对象，用于从T中提取Key KeyOfT kot; };

这里引入了第三个模板参数KeyOfT，它是一个仿函数（函数对象），专门用来从T类型的数据中取出用于比较的键值Key。这是实现代码复用的精髓所在。

3.2 仿函数KeyOfT：实现泛型的关键

set和map需要向红黑树传入不同的T，但树内部的比较逻辑只关心Key。仿函数就像一个统一的“提取器”。

// 针对set的仿函数：T就是Key，直接返回自身 struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; // 针对map的仿函数：T是pair，返回其first成员（即键） struct MapKeyOfT { const K& operator()(const std::pair<const K, V>& kv) { return kv.first; } };

这样，在RBTree::Insert函数中，当需要比较两个节点的大小时，我们不再直接比较_data，而是通过kot仿函数来获取键值：

if (kot(cur->_data) < kot(data)) { // 去左边 // ... } else if (kot(cur->_data) > kot(data)) { // 去右边 // ... } else { return false; // 键已存在，插入失败 }

3.3 迭代器设计：让树可遍历

STL容器的灵魂之一就是迭代器。我们的红黑树迭代器需要支持++（中序遍历的下一个节点）和--操作。

template<class T, class Ref, class Ptr> struct __RBTreeIterator { typedef RBTreeNode<T> Node; typedef __RBTreeIterator<T, Ref, Ptr> Self; Node* _node; __RBTreeIterator(Node* node) : _node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { // 核心：找中序后继 if (_node->_right) { // 如果右子树存在，后继是右子树的最左节点 Node* left = _node->_right; while (left->_left) left = left->_left; _node = left; } else { // 如果右子树不存在，向上回溯，找到第一个孩子是父亲左孩子的祖先节点 Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_right) { cur = parent; parent = parent->_parent; } _node = parent; } return *this; } // ... 其他操作符重载 };

迭代器的++操作实现了红黑树的中序遍历（升序）。理解这个逻辑的关键在于中序遍历的顺序是“左-根-右”。对于一个节点，如果它有右子树，那么它的后继一定在右子树中最小的节点（即最左节点）。如果没有右子树，那么它的后继是向上追溯时，第一个将当前节点包含在其左子树中的祖先节点。

实操心得：迭代器的end()通常指向一个空节点（即nullptr），或者像STL一样指向一个特殊的哨兵节点。在实现begin()时，返回的是整棵树的最左节点（最小元素）。在封装set/map时，begin()和end()需要正确转发给红黑树的对应接口。

4. 实现MySet与MyMap容器

红黑树封装完毕，MySet和MyMap的实现就变成了“组装”工作。它们内部包含一个RBTree的实例，并将所有操作委托给这个实例。

4.1 MySet的封装实现

MySet的模板参数只有一个K（键类型）。它的核心是定义一个红黑树类型，并公开用户需要的接口。

template<class K> class MySet { public: // 用于从K中提取Key的仿函数 struct SetKeyOfT { const K& operator()(const K& k) { return k; } }; // 红黑树类型定义，T=K, KeyOfT=SetKeyOfT typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } std::pair<iterator, bool> insert(const K& key) { return _t.Insert(key); // 直接调用红黑树的Insert } // ... 其他接口：find, erase, size等 private: RBTree<K, K, SetKeyOfT> _t; // 核心数据成员 };

可以看到，MySet的insert方法直接调用了_t.Insert。这里_t.Insert的返回值类型需要是std::pair<iterator, bool>，其中iterator指向插入的节点（或已存在的节点），bool表示插入是否成功。这需要我们在RBTree::Insert的实现中返回树的迭代器类型。

4.2 MyMap的封装实现

MyMap的模板参数是K和V。它的T类型是std::pair<const K, V>，注意键是const，这是为了禁止用户通过迭代器修改键值，否则会破坏红黑树的有序性。

template<class K, class V> class MyMap { public: // 用于从pair中提取Key的仿函数 struct MapKeyOfT { const K& operator()(const std::pair<const K, V>& kv) { return kv.first; } }; // 注意：T 是 pair<const K, V> typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } std::pair<iterator, bool> insert(const std::pair<const K, V>& kv) { return _t.Insert(kv); } // Map特有的operator[]，功能强大：访问或插入 V& operator[](const K& key) { std::pair<iterator, bool> ret = insert(std::make_pair(key, V())); // ret.first 是迭代器，指向插入的或已存在的pair return ret.first->second; // 返回value的引用 } // ... 其他接口 private: RBTree<K, std::pair<const K, V>, MapKeyOfT> _t; };

MyMap的operator[]是点睛之笔。它的逻辑是：尝试插入一个键为key，值为V()（值类型的默认构造）的键值对。如果key已存在，insert返回已存在节点的迭代器；如果不存在，则插入新节点。最后，无论哪种情况，都返回该键对应值的引用。这完美实现了“如果key不存在则插入，如果存在则访问”的语义，非常简洁高效。

4.3 迭代器与const迭代器的处理

这里有一个进阶的细节：set的迭代器应该是const_iterator，因为set的元素（键）是不可修改的，否则会破坏有序性。而map的迭代器解引用后得到的是一个pair，其中first（键）是const，但second（值）是可以修改的。

为了实现这一点，需要在红黑树的迭代器模板和set/map的封装上做文章。一种常见做法是在RBTree中定义iterator和const_iterator，然后在MySet中，将iterator和const_iterator都定义为红黑树的const_iterator，从而禁止修改。而在MyMap中，则正常使用红黑树的iterator。这涉及到模板和类型别名的巧妙运用，是理解STL设计深度的好机会。

5. 测试、调试与性能对比

实现完成后，必须进行 rigorous 的测试。

5.1 基础功能测试

首先测试基本功能是否正确：

1. 插入测试：大规模插入随机数、有序数（最坏情况），观察树是否保持平衡（可以通过中序遍历输出是否有序来初步判断）。
2. 查找测试：测试find接口，对存在的和不存在的键进行查找。
3. 遍历测试：使用迭代器进行范围for循环，确认遍历顺序是升序的。
4. Map[]操作符测试：测试map["key"] = value的赋值和访问功能，以及键不存在时的插入行为。

void TestMyMap() { MyMap<std::string, int> countMap; std::string arr[] = {"苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果"}; for (auto& str : arr) { countMap[str]++; // 这里完美展示了operator[]的威力 } for (const auto& kv : countMap) { // 使用范围for遍历 std::cout << kv.first << ":" << kv.second << std::endl; } // 预期输出：苹果:6 西瓜:3 香蕉:1 }

5.2 红黑树规则验证

实现一个检查函数，递归验证红黑树的五条规则是否全部满足。这是调试阶段最有效的工具。

• 规则1、2、3很容易检查。
• 规则4（无连续红节点）：遍历时检查每个红色节点，其父节点不能为红。
• 规则5（黑高一致）：编写一个辅助函数，计算从根到任意叶子NIL节点的黑色节点数量，确保所有路径的数量相同。

5.3 与STL性能对比

编写性能测试代码，对比MySet/MyMap和std::set/std::map在大量插入、查找、删除操作上的耗时。可以使用<chrono>库进行计时。

#include <chrono> #include <set> #include <vector> #include <cstdlib> void PerformanceTest() { const int N = 1000000; std::vector<int> v; v.reserve(N); for (int i = 0; i < N; ++i) { v.push_back(rand()); } // 测试std::set std::set<int> s1; auto start1 = std::chrono::high_resolution_clock::now(); for (auto e : v) s1.insert(e); auto end1 = std::chrono::high_resolution_clock::now(); auto duration1 = std::chrono::duration_cast<std::chrono::milliseconds>(end1 - start1); // 测试MySet MySet<int> s2; auto start2 = std::chrono::high_resolution_clock::now(); for (auto e : v) s2.insert(e); auto end2 = std::chrono::high_resolution_clock::now(); auto duration2 = std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2); std::cout << "std::set insert time: " << duration1.count() << " ms" << std::endl; std::cout << "MySet insert time: " << duration2.count() << " ms" << std::endl; }

在Release优化模式下运行，两者的差距应该很小。如果MySet慢很多，可能需要检查旋转、查找等核心逻辑是否有效率瓶颈。

5.4 内存泄漏检查

使用Valgrind（Linux/Mac）或Visual Studio自带的内存诊断工具，确保我们的实现没有内存泄漏。重点检查在节点删除（如果实现了erase）和整个树析构时，是否正确释放了所有节点内存。可以在RBTree的析构函数中实现一个后序遍历来删除所有节点。

6. 常见问题与深度避坑指南

在实现过程中，我踩过不少坑，这里总结几个最具代表性的问题和解决方案。

6.1 迭代器失效问题

问题描述：在遍历容器（如使用迭代器循环）的过程中，如果进行了插入或删除操作，可能会导致当前迭代器指向的节点位置发生变化或失效，继续使用该迭代器会导致未定义行为（崩溃或数据错误）。

根因分析：红黑树的插入和删除操作可能涉及旋转和节点重新链接。例如，一次左旋会改变节点A和其右孩子B的父子关系及左右指针。如果此时有一个迭代器正指向A或B，旋转后迭代器内部持有的节点指针_node可能仍然指向原来的内存地址，但该节点在树中的位置和角色已经改变，导致迭代器逻辑（如++操作）出错。

解决方案：

1. 最安全的做法：遵循STL容器的通用约定——在修改容器结构（插入、删除）后，之前获取的所有迭代器、指针和引用都可能失效，不应再使用。如果需要继续遍历，应重新调用begin()获取新的迭代器。
2. 特定场景优化（高级）：如果你能确定插入操作没有引起旋转（例如，插入新节点后仅通过变色就满足了红黑树性质），那么指向其他未受影响节点的迭代器仍然是有效的。但判断这一点非常复杂，且依赖于红黑树的具体实现状态，因此不推荐在通用库中做这种保证。对于map的operator[]，它内部调用了insert，所以使用operator[]后，其他迭代器也可能失效，这一点要特别注意。

6.2 删除操作的实现难点

红黑树的删除是比插入更复杂的操作，也是很多教程和面试中回避的深水区。其复杂点在于，删除一个节点后，可能会破坏规则4和规则5，并且调整情况比插入更多（主要看接替删除节点的兄弟节点的颜色和其子节点的颜色）。

核心步骤：

1. 找到后继节点并替换：如果待删除节点有两个孩子，需要找到它的中序后继节点（右子树的最左节点），用后继节点的值覆盖待删除节点，然后转为删除那个后继节点（后继节点最多只有一个右孩子）。
2. 处理单孩子或无孩子情况：此时，待删除节点（记为D）最多有一个孩子（记为C）。
   • 如果D是红色，直接删除，用C替换D的位置（C可能是NIL），不会破坏黑高。
   • 如果D是黑色，而C是红色，那么删除D后，用C替换，并将C染黑，即可补偿失去的一个黑节点。
   • 最复杂的情况：D是黑色，C也是黑色（或NIL）。此时删除D会导致经过该路径的黑高减少1，需要从兄弟节点那边“借”一个黑色过来，或者通过旋转和变色重新分配黑色。这衍生出多种子情况，调整可能向上传播。

避坑指南：首次实现时，可以先不实现删除功能，专注于把插入、遍历和查找做稳定。如果必须实现删除，建议在纸上画出所有可能的情况（兄弟节点是红是黑、兄弟节点的孩子是红是黑等），并严格对照《算法导论》或可靠的教材中的伪代码进行实现，每一步调整后立即检查五条规则。编写一个强大的CheckRBTree()函数在每次删除后自动验证，是调试的不二法门。

6.3 模板编译错误排查

由于大量使用了模板和嵌套类型，编译错误信息往往又长又晦涩。

典型错误1：“dependent name is not a type”

typedef RBTree<K, K, SetKeyOfT>::iterator iterator; // 可能报错

解决方法：在嵌套类型名前加上typename关键字，告诉编译器这是一个类型，而不是静态成员。

typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;

典型错误2：链接错误（未定义的引用）模板类的成员函数定义如果放在.cpp文件中，会导致链接错误。因为模板需要在编译时实例化。解决方法：将模板类的声明和定义全部放在头文件（.hpp或.h）中。这是C++模板编程的通用做法。

调试技巧：当遇到一长串模板错误时，从第一个错误开始看。通常第一个错误指出了最根本的问题，后面的很多错误是连锁反应。可以尝试先注释掉部分代码，让程序能通过编译，再逐步添加，定位问题代码块。

6.4 如何验证实现的正确性

除了自己写测试用例，还有一个“笨”但极其有效的方法：与STL容器进行对照测试。

1. 准备相同的随机数序列。
2. 分别插入到std::set和MySet中。
3. 分别进行中序遍历，将结果输出到两个向量中。
4. 比较两个向量是否完全一致。
5. 随机进行大量查找、删除操作，比较两个容器的结果和最终状态是否一致。

这种方法可以帮你发现许多边界条件和逻辑错误。我正是在一次对照测试中，发现自己在处理“叔叔节点为红色”的插入情况时，忘记将祖父节点作为新的当前节点继续向上调整，导致在连续插入特定序列时，树的高度异常。

封装红黑树来实现set和map，是一个将数据结构理论、C++模板编程、STL设计思想融会贯通的绝佳项目。它强迫你去思考每一个细节，从节点的内存布局到迭代器的抽象，从模板的实例化到异常安全。当你最终看到自己写的MyMap能和std::map一样流畅地工作时，那种对底层机制透彻理解的成就感，是任何现成库都无法给予的。这个过程里调试旋转逻辑时画的满纸涂鸦，和最终通过所有测试时的那一下编译成功的提示音，大概就是C++工程师的浪漫吧。