企业官网建设流程全解析

很早以前我就在想一个问题：既然 STL 的 map 和 set 都要求元素有序、都要求增删查做到 O(logN)，那为什么不能直接用同一棵红黑树把两个容器都实现了？后来我真正动手去读库实现、自己照着封装一遍之后，才明白所谓“复用”并不是把代码复制两份再改改，而是通过模板参数把“变化的东西”抽象出来，让一棵底层红黑树既能存 key，又能存 key-value 对。

这篇文章就是我自己从零封装红黑树、然后基于它实现 map 和 set 的完整记录。我会把节点设计、迭代器、插入删除的旋转变色、map 和 set 的上层封装细节，还有我踩过的各种坑全部写出来。如果你是那种“会用 map/set 但想知道底层到底怎么长出来”的人，或者正准备手写一棵红黑树却不知道从哪下手，那这篇就是写给你的。文章里的代码是简化版，但核心逻辑和真实 STL 的 _Rb_tree 结构是同一个套路，看懂了它，你再去读 libstdc++ 源码会轻松很多。

1. 为什么 set 和 map 能共用一棵红黑树

1.1 红黑树到底解决什么问题

先回到最基本的问题：STL 里的 set 和 map 都是“关联容器”，它们最重要的三个能力是：元素按 key 有序存储、插入/删除/查找的时间复杂度为 O(logN)、支持中序遍历得到有序序列。能同时满足这三点的数据结构，最常见的就是平衡二叉搜索树。而红黑树就是平衡二叉搜索树里工程上用得最广的一种。

红黑树本质上还是二叉搜索树，只是给每个节点加了一个颜色属性（红或黑），并通过五条性质来限制树的形态：

1. 每个节点要么是红色，要么是黑色。
2. 根节点必须是黑色。
3. 每个叶子节点（NIL 空节点）都是黑色。
4. 红色节点的两个子节点必须都是黑色，也就是不能出现连续两个红色节点。
5. 从任意节点到其所有后代叶节点的路径上，黑色节点数量必须相同。

这五条性质加在一起，保证了从根到叶子的最长路径不会超过最短路径的两倍。最短路径全是黑色节点，最长路径是“黑-红-黑-红”交替，因为红色不能连续，所以最长路径最多就是最短路径的两倍。这样一来，树的高度被限制在 O(logN)，所有操作也就稳定在 O(logN)。

我最初自己写的时候，经常记混第 5 条，后来找了个生活化类比：把黑色节点当成火车站，红色节点当成普通停靠站。从根到任何叶子，你数出来的“火车站”数量必须一样，这意味着哪怕路线再绕，站点的骨架也不会歪到哪里去。有了这个约束，整棵树才不会退化成链表。

1.2 为什么不用 AVL 树或哈希表

很多人会问：AVL 树平衡得更严格，查找性能不是更好吗？哈希表不是更快吗？

AVL 树确实让左右子树高度差不超过 1，查找时最坏情况更优。但代价是插入和删除时的旋转操作更频繁。红黑树的平衡标准是“最长路径不超过最短路径的两倍”，比 AVL 宽松，所以插入和删除时需要调整的次数更少。对于 STL 这种“插入删除操作非常多、一次查找只要 O(logN) 就够用”的应用场景，红黑树是更好的折中。

哈希表的问题在于它不保持有序性。map 和 set 都支持 lower_bound、upper_bound、equal_range，还能用迭代器做 ++/-- 遍历，这些操作都建立在“元素之间有意义的大小关系”上。哈希表只能回答“在不在”，不能回答“谁是下一个比它大的元素”。所以 STL 的 unordered_map/unordered_set 用哈希表，而 map/set 用红黑树，两者定位完全不同。

另外一个容易被忽略的点是：红黑树不需要负载因子，不需要扩容搬移，内存分配是每次插入一个节点单独分配。长时间使用后哈希表可能因为冲突、rehash 出现延迟抖动，红黑树则相对稳定。这也是某些实时性要求高的场景仍然偏向树形结构的原因。

2. 从零设计一棵可复用的红黑树

2.1 节点结构：颜色、左右孩子、父指针，还有哨兵

真正开始写代码的时候，第一步不是急着写旋转，而是先把节点定义好。我的节点长这样：

enum Color { RED = false, BLACK = true }; template <typename Value> struct RBNode { Color color; Value data; RBNode* left; RBNode* right; RBNode* parent; explicit RBNode(const Value& val = Value(), Color c = RED) : color(c), data(val), left(nullptr), right(nullptr), parent(nullptr) {} };

这里有几个设计决策。

第一，为什么存 Value 而不是分开存 Key 和 T？因为底层树并不知道自己将来是被 map 用还是被 set 用。map 要存 pair<const K, V>，set 只需要存 K。如果一个红黑树节点同时带上 Key 和 T 的模板参数，那 set 的“值”字段就会白白浪费。所以节点只存一个统一的 Value，至于这个 Value 里面怎么取出来比较，交给上层仿函数。

第二，为什么要 parent 指针？红黑树插入和删除时经常需要回溯到父节点、叔叔节点、祖父节点，没有 parent 指针就只能在递归函数里传一堆引用来模拟回溯，非常痛苦。STL 的 _Rb_tree 节点里也保存了父指针，只是它用了更高明的技巧把 parent 指针的最高位用来存颜色，这是内存优化的做法，我们学原理阶段先不搞那么变态。

第三，关于空节点。经典的红黑树算法里，所有叶子都是 NIL 哨兵节点，而不是 nullptr。哨兵节点是黑色的，它的 parent、left、right 都指向自己或者根节点。引入哨兵可以避免在删除时对空指针做特殊判断，尤其是处理“双黑”情况时，哨兵让逻辑统一很多。STL 源码里其实没有给每个节点挂哨兵，而是通过 header 节点和 end() 迭代器来做类似的事，这个后面讲迭代器再展开。

我自己的实现里用了哨兵节点nil，作为全局空节点。树根 root 初始化时指向 nil，nil->parent = root 这种反指关系在旋转时比较省心。不过要注意，哨兵隔离了空指针，调试的时候很容易忘，比如你打印一棵空树，它其实有一个黑色节点在那，别觉得奇怪。

2.2 KeyOfValue 仿函数：让一棵树同时服务 map 和 set

如果要复用红黑树，最核心的问题就是：底层树怎么拿到 key？map 的节点存的是 pair，set 的节点存的是 key 本身，两者的“取 key”方式不同。如果红黑树代码里写死 data.first，那 set 根本没法用。

解决办法是给红黑树增加一个模板参数KeyOfValue，它是一个仿函数，负责从 Value 中提取 Key。红黑树内部所有比较都用KeyOfValue()(node->data)拿到 key 之后，再去和传入的 key 比较。

STL 里的 map 传入的是_Select1st<pair<const _Key, _Tp>>，set 传入的是_Identity<T>。我自己的实现如下：

template <typename K, typename V> struct MapKeyOfValue { const K& operator()(const std::pair<const K, V>& p) const { return p.first; } }; template <typename K> struct SetKeyOfValue { const K& operator()(const K& k) const { return k; } };

有了这个仿函数，红黑树的插入函数签名就可以写成：

iterator insert(const KeyType& key);

内部会把 key 构造出一个完整的 Value，再按照二叉搜索树的规则找位置。比如 map 插入时，key 是第一个参数，Value 是pair<const K, V>；set 插入时，key 和 Value 是同一个东西。

这里有一个容易踩的坑：map 的 value_type 是pair<const K, V>，但红黑树内部做节点比较时必须用 pair 第一个元素，也就是 key。如果你不小心用了整个 pair 去比较，pair 的 operator< 会先比 first，再比 second，导致两个 key 相同但 value 不同的 pair 被当成不同节点插入，map 的“key 唯一性”就彻底失效了。所以KeyOfValue不是可有可无的优化，而是语义正确性的保证。

2.3 迭代器设计：中序遍历和 ++ 操作

写迭代器是封装容器里最“颇”的一环。红黑树的迭代器本质上要支持*、->、++、--、==、!=，其中++和--对应的就是二叉搜索树中序遍历的后继和前驱。

中序遍历的顺序是：左子树、根节点、右子树。所以“找下一个节点”的逻辑是：

• 如果当前节点的右子树不为空，那么后继就是右子树中最左边的节点。
• 如果当前节点的右子树为空，那么后继就是“从当前节点向上走，第一个作为左孩子存在的祖先节点的父节点”。

我第一次写的时候第二句话绕了半天。换成大白话：当前节点已经走完了以它为根的整棵子树，下一步应该回到“把它当成左子树的那个父节点”。

迭代器类大致长这样：

template <typename T> struct RBTreeIterator { using Node = RBNode<T>; Node* ptr; T& operator*() const { return ptr->data; } T* operator->() const { return &ptr->data; } RBTreeIterator& operator++() { if (ptr->right != nil) { ptr = leftMost(ptr->right); } else { Node* y = ptr->parent; while (y != nil && ptr == y->right) { ptr = y; y = y->parent; } ptr = y; } return *this; } };

这里描述的是最简单的版本。STL 里为了配合end()迭代器，节点结构里加了 header 节点，header 的 parent 指向根节点，header 的 left/right 分别指向最小/最大节点。这样begin()就是最左节点，end()就是 header，--end()就是最大节点。这个设计非常巧妙，但初次实现时可以先不加，直接用 nullptr 表示 end()，只要保证遍历到 nullptr 就停止就行。

const 迭代器怎么做？STL 的做法是给迭代器模板增加IsConst参数，或者直接用基类派生。C++ 里最简单的做法是用同一个模板类，把指针类型变成const Node*：

template <typename T, bool IsConst> struct RBTreeIterator { using NodePtr = typename std::conditional<IsConst, const RBNode<T>*, RBNode<T>*>::type; using Ref = typename std::conditional<IsConst, const T&, T&>::type; NodePtr ptr; // 其余逻辑一样 };

这样底层树的iterator和const_iterator共用一套遍历算法，只是指针的 const 限定不同。注意node_type和value_type不能混：迭代器对外返回的是value_type&，但内部遍历时操作的是节点。map 的iterator解引用得到pair<const K, V>&，这意味着你不能用迭代器修改 key，但可以修改 value，这个效果由 pair 的第一个 const 自动保证。

3. map 和 set 的上层封装实现

3.1 map 的封装：pair 和 operator[]

底层红黑树建好之后，map 类就变成了一层薄薄的适配器。map 内部持有一个红黑树对象，红黑树模板参数是Value = pair<const K, V>，KeyOfValue = MapKeyOfValue<K, V>。map 的绝大多数方法都直接转发给树。

这里最值得讲的是operator[]。这是 map 和 set 区别最大的地方：set 没有operator[]，而 map 有，并且它的行为很特殊——如果 key 不存在，会自动插入一个默认构造的 value，然后返回该 value 的引用。

朴素的实现：

V& operator[](const K& key) { iterator it = find(key); if (it == end()) { it = insert({key, V()}).first; } return it->second; }

但其实是两次查找，一次 find，一次 insert。STL 为了提高效率，直接用 lower_bound 返回的位置作为插入提示：

V& operator[](const K& key) { iterator it = lower_bound(key); if (it == end() || key_comp()(key, it->first)) { it = insert(it, {key, V()}); } return it->second; }

先 lower_bound，如果 key 不在树中，lower_bound 返回的就是第一个不小于 key 的位置，也就是插入点。这时用带 hint 的 insert，能做到 O(logN) 并且避免二次查找。如果 key 已经存在，lower_bound 返回的就是该 key 所在节点的迭代器，直接返回引用即可。注意判断条件要用key_comp()(key, it->first)，这也验证了 key 严格小于当前位置的 key 时才需要插入。

我用过上面这个版本后，再看某些教程里“find + insert”的实现，只能说能用，但性能差一截。工程里差的这几次 O(logN) 在大量查询场景下是能感受到的。

3.2 set 的封装：key 即 value

set 的封装比 map 简单得多，因为 set 的 value 本身就是 key。红黑树模板参数是Value = K，KeyOfValue = SetKeyOfValue<K>。所有插入、删除、查找操作，set 都是直接转发给树。

但 set 有一个特殊性：不允许修改元素的值。因为如果允许修改，就可能破坏红黑树的排序性质。STL 里 set 的iterator和const_iterator的 operator* 返回的都是const T&，也就是说你拿到的迭代器只能读不能写。我实现的时候，set 暴露迭代器的方式是：

typedef typename Tree::const_iterator iterator; typedef typename Tree::const_iterator const_iterator;

直接把 const_iterator 别名成 iterator，这样外部即使想修改也修改不了。这是 set 和 map 在封装层面的关键差异。

另一个差异在 insert 的返回值类型：map 的 insert 返回pair<iterator, bool>，set 的 insert 返回pair<iterator, bool>，但 set 的 iterator 本质是 const_iterator。我在代码里对迭代器类型做转换时踩过坑：底层树的 iterator 可以隐式转换成 const_iterator，但不能反向转换。所以 set 上的find返回 const_iterator，如果用 auto 接住，交给其他接口时要注意类型匹配。

3.3 封装时最容易出错的三类类型问题

第一，pair 的第一个参数必须加 const。map 的 value_type 是pair<const K, V>，不能写成pair<K, V>。如果写成后者，用户通过迭代器拿到pair<K, V>&后就能修改 first，等于改了 key，树的有序性就崩了。红黑树内部所有节点比较都用KeyOfValue，如果你能直接改 first，意味着红黑树维护的排序结构被破坏，后面的 lower_bound、迭代器遍历全部失效。

第二，迭代器解引用的类型要跟容器的 value_type 一致。map 的iterator::operator*必须返回pair<const K, V>&，set 必须返回const K&。这个可以在编译期通过模板强制，但如果封装时不小心把底层的Value直接暴露成迭代器返回值，就可能出现 map 的迭代器能改 key 的漏洞。

第三，value_comp的实现。C++ 标准要求 map::value_comp 返回一个比较函数对象，它比较两个 value_type 时只按 key 比较。我一开始没搞封装，直接拿红黑树的比较器，导致 value_comp 比较了整个 pair，行为不符合标准。正确做法是内部写一个仿函数，专门调用KeyOfValue后再比较。

4. 核心操作：插入、删除、旋转，以及红黑性质的维护

4.1 插入：为什么新节点必须是红色

插入算法分为两步：先按二叉搜索树规则把节点放进去，再通过变色和旋转修复红黑性质。新节点为什么默认是红色？因为如果新节点是黑色，它就一定会让从根到它所在叶子路径上的黑色节点数量比其他路径多一个，直接违反性质 5，而且这种破坏很难修复。如果新节点是红色，可能违反的只有性质 4（不能连续红色），修复起来只需要局部变色加一到两次旋转，代价小得多。所以工程实现里新插入节点一律红色。

插入后，如果新节点的父节点是黑色，不需要做任何修复，直接完成。如果父节点是红色，那么祖父节点一定是黑色（因为性质 4），此时要看叔叔节点的颜色分三种情况。

我把这三种情况用自己的话整理一遍，假设当前节点是 x，父节点 p，祖父节点 g，叔叔节点 u：

• 情况一：u 是红色。把 p 和 u 都变黑，g 变红，然后把 x 上移到 g，继续循环。这相当于把“红色冲突”向上传递。
• 情况二：u 是黑色（或 nil），并且 x 是 p 的右孩子。先对 p 做左旋，变成情况三。也就是把一条斜线理顺成一条直线。
• 情况三：u 是黑色（或 nil），并且 x 是 p 的左孩子。对 g 做右旋，交换 p 和 g 的颜色。修复结束。

很多教程喜欢画一堆图，但实际写代码就分这几种。难点在于 x 上移到 g 之后，可能再次触发情况，所以要 while 循环。循环终止条件是 x 的父节点变成黑色，或者 x 成为根节点。

插入修复的代码骨架：

void insertFixup(Node* x) { while (x != root && x->parent->color == RED) { if (x->parent == x->parent->parent->left) { Node* u = x->parent->parent->right; // uncle if (u->color == RED) { x->parent->color = BLACK; u->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; } else { if (x == x->parent->right) { x = x->parent; leftRotate(x); } x->parent->color = BLACK; x->parent->parent->color = RED; rightRotate(x->parent->parent); } } else { // 对称逻辑 } } root->color = BLACK; }

这里有个细节：每轮循环开头判断x->parent->color == RED，一旦父节点是黑就直接退出。因为插入红色节点后，唯一可能被破坏的性质是 4，只要父节点黑，就没事了。循环最后强制把根涂黑，保证性质 2。

4.2 删除：为什么比插入麻烦得多

删除操作是红黑树里最劝退的部分，但把它拆开看也没那么恐怖。先按普通二叉搜索树删除：如果被删节点有两个孩子，就找到它的中序后继（右子树最左节点），把后继的 data 复制到当前节点，然后转而删除这个后继节点。经过这个转移后，真正要删除的节点最多只有一个孩子。

删除完成后，真正需要修复的情况是被删节点是黑色。因为如果被删节点是红色，红黑性质并不会被破坏（红色节点不影响黑色数量，也不会产生连续红冲突），直接删掉完事。如果被删的是黑色，那么那条路径上少了一个黑色节点，性质 5 被违反了，需要引入一个“双黑”概念来修复。

双黑的意思就是：原来的黑色节点被 y 的孩子 x 继承了，x 在自己是黑色之外，还欠了一份黑色。接下来的目标就是把这份多余的黑色向上传递，直到找到一个红色节点涂黑，或者传到根节点。

修复分四种情况，以 x 是父节点的左孩子为例：

• 情况一：x 的兄弟节点 w 是红色。把 w 变黑，x 的父节点变红，对父节点左旋，然后更新 w 为新的兄弟节点。这是为了把问题转换成兄弟为黑色的情况。
• 情况二：w 是黑色，且 w 的两个孩子都是黑色。把 w 变红，x 上移到父节点，继续循环。因为 w 变红后，以父节点为根的子树里左右两边黑色数相等，但总量少了一个，需要交给上层修复。
• 情况三：w 是黑色，w 的左孩子是红色，右孩子是黑色。对 w 右旋，交换 w 和左孩子的颜色，把情况转换为情况四。
• 情况四：w 是黑色，且 w 的右孩子是红色。把 w 涂成父节点颜色，父节点涂黑，w 的右孩子涂黑，对父节点左旋，修复结束。

删除修复的代码比插入长一倍，主要是四种情况的对称镜像。我在手写的时候发现，最容易出错的是更新兄弟节点 w 的时机：每旋转一次，w 的位置都可能变化，必须要重新根据x->parent来取新的兄弟指针，而不是继续用旧的。

另外一个容易忽略的点是：如果被删的节点是根节点，而且它是唯一的黑色，直接把它删掉，新根（可能是 nil）一定要涂黑。我在实现时，删除后总是把 root 显式置为黑色，即使 root 是 nil 也执行，让哨兵保持黑色性质，免得后面插入修复时条件判断出错。

4.3 左旋和右旋：两个人的旋转舞

旋转是红黑树的基础操作。左旋的意思是把某个节点 x 的右孩子 y 提上来，让 y 成为 x 的父节点，x 成为 y 的左孩子，y 原来的左子树变成 x 的右子树。右旋就是完全对称。

我写旋转的代码时，第一个版本忘记更新三个 parent 指针，导致第一轮插入就死循环。正确顺序是：

1. 保存 x 的右孩子 y = x->right。
2. y 的左子树 b 过继给 x，作为 x 的右孩子。
3. x 的父节点重新绑定（可能指向 y，也可能指向原来 x 的父节点）。
4. y 的左孩子设为 x。
5. 如果 x 是根节点，更新 root。

其中第 3 步最容易漏：x 可能是它父节点的左孩子，也可能是右孩子，还可能就是根。代码里需要统一判断。

我自己的经验是每次旋转完，立刻用assert检查 x、y、x->parent、y->parent 的左右关系是否正确。红黑树 bug 绝大多数是旋转后父子指针断裂，写个小的checkTreeIntact函数能省很多调试时间。

5. 常见问题与排查技巧实录

5.1 迭代器失效问题：erase 之后到底还能不能用

这是使用 map/set 时最经典的问题。STL 的红黑树实现中，除了被 erase 的那个节点对应的迭代器失效外，其他迭代器都不会失效。原因是红黑树节点在内存中是独立的，插入删除不涉及节点的整体搬移，旋转操作也没有把数据拷来拷去，只是改变指针指向。所以只要你不在循环里使用被删掉的迭代器，遍历就安全。

但有一个细节：erase(iterator)返回的迭代器在 C++11 中是下一个元素的迭代器，但在 C++98 里 map/set 的 erase 返回 void。如果做边遍历边删除，C++98 的惯用写法是：

for (auto it = m.begin(); it != m.end(); ) { if (shouldErase(it)) { m.erase(it++); } else { ++it; } }

C++11 之后可以写成it = m.erase(it)。我在自己封装的红黑树里，把 erase 的返回值设计成被删节点的后继，这样用户可以直接用新的写法，更人性化。

5.2 内存分配：一个个 new 会不会太慢

红黑树每个节点都单独new，在大量插入操作面前确实有性能损耗。STL 并没有在红黑树层实现内存池，而是通过std::allocator提供抽象。默认 allocator 会调用::operator new，但很多库在实现 std::allocator 时做了大小类内存池优化，比如 glibc 的 malloc 本身就有 fastbin，所以小对象分配并不慢。

我在自己封装时，为了做性能测试，干脆实现了一个简单的节点内存池：预先分配一整块RBNode<Value>内存，插入时从空闲链表取节点，删除时归还。结果测试下来，100 万次插入+遍历，内存池版本比逐 new 快约 30% 左右。但要注意：内存池版本需要处理节点构造函数和析构函数的调用，正确做法是placement new和显式析构，而不是直接 memcpy。新手别直接写内存池，先用标准 new 把逻辑跑通再说。

5.3 性能实测：map 和 set 的真实表现

我自己写了小型 benchmark，分别测试 100 万次随机插入、100 万次查找、中序遍历 100 万次。结果是 map 和 set 的耗时基本在同一量级，map 略慢几分钟，原因是 map 的节点里存了 pair，比较 key 时多一层仿函数调用。如果开启编译器优化（O2），仿函数调用都会被内联掉，差距基本消失。

一个有意思的发现是：红黑树的插入性能非常稳定，但受随机数质量影响很大。如果插入数据接近有序，插入修复过程会更多调用旋转，所以性能会比随机插入差。极端情况下，即使树是平衡的，插入时红色节点冲突的概率也会增大。所以在做性能测试时，要注意数据分布，最好用三种数据测：随机、升序、降序。

5.4 调试红黑树的独家技巧

红黑树的调试是最痛苦的，因为你看树结构看不出对不对。我的办法是写两个辅助函数：

第一个是中序遍历，验证整个树是否满足二叉搜索树性质：

void inorderCheck(Node* x, const K& prev) { if (x == nil) return; inorderCheck(x->left, prev); assert(prev < KeyOfValue()(x->data)); inorderCheck(x->right, prev); }

注意红黑树中不允许重复 key，所以严格判断 prev < current 即可。

第二个是性质校验，递归计算每条路径黑色节点数量，检查是否一致，同时检查有没有连续红色节点：

int checkBlackHeight(Node* x) { if (x == nil) return 0; int lh = checkBlackHeight(x->left); int rh = checkBlackHeight(x->right); assert(lh == rh); assert(!(x->color == RED && x->parent->color == RED)); return lh + (x->color == BLACK ? 1 : 0); }

这两个函数在每次插入、删除后调用一次，几乎能抓出 99% 的指针错误。我强烈建议你在写旋转代码时，每写完一个旋转函数，就调用这两个检查函数跑大量随机操作。一旦出错，你就把那一轮的操作序列打出来，复现最小用例，很快就能定位到是哪一步旋转出的问题。

另外，调试时最好把红黑树以“中序遍历+颜色+key”的形式打印出来，比如(B)10 (R)20 (B)30，用这种格式配合断点，比画图直观。

最后分享一个小技巧

我在自己封装的过程中，最深的体会就是：不要把红黑树的所有代码一次性写完再调试，而是分三步走。第一步只实现普通二叉搜索树的插入、删除、遍历，完成后再验证有序性；第二步加入颜色和旋转修复，用随机数据猛测；第三步才去封装 map 和 set 的上层接口。每一步的 bug 都不会牵涉太多变量。

如果你也打算照着这篇思路自己写，建议你把哨兵节点和 header 节点的关系好好理一下。我最初用了全局哨兵 nil，后来为了支持 end() 迭代器加 header，结果 header 和 nil 的关系没理清，遍历时经常多输出一个空节点。后来我采用的办法是：header 本身就是一个真实的节点，它不存储有效数据，它的 left 指向最小节点，right 指向最大节点，parent 指向根；而 nil 仍然作为所有空孩子的哨兵。这样begin()直接返回 header->left 对应的迭代器，end()返回指向 header 的迭代器，--end()就是 header->right。这套结构和 STL 源码的设计基本一致。理解了它，你再去看任何一份红黑树实现，都不会觉得云里雾里。

从一棵裸的红黑树到 map/set 的封装，中间其实没有太多魔法，真正核心的只有两件事：通过模板参数把比较规则抽象出来，通过迭代器类型限定把 const 语义传递出去。这两件事处理好了，你不仅能封装 map/set，以后想封装 multiset、multimap、甚至能按任意字段排序的容器，也只是多给红黑树传一个不同的比较器而已。