真的要手写一棵 C++ 红黑树吗？很多人看到“平衡二叉树”和“红黑树”这两个词，第一反应是背各种 case，第二反应是打开资料发现红黑树插入删除居然有六七个分支，然后默默关掉页面。但只要你用过 std::map、std::set，就早就在和红黑树打交道了——C++ STL 的关联容器底层默认实现几乎都是红黑树。它不是考试专属玩具，工程里一句map[key] = value背后就是一棵红黑树在帮你保持有序并完成对数级别查找。
这篇东西我想用真正写过、调试过红黑树的经验，把“为什么需要它”“五条性质到底在说什么”“C++ 怎么落地”“STL 和数据库里的 B+ 树跟它什么关系”讲透。写到一半会给出一个可以直接跑通的红黑树核心实现，后面还整理了我在实际项目中踩过的坑。适合正在学 C++ 数据结构、准备面试、或者想深入理解 STL 底层的人看。新手看不懂的地方，我会用大白话解释；有经验的人可以直接跳到实现部分。
1. 先说结论：这就是 C++ 里 map 的“骨架”
1.1 红黑树在工程里的真实存在感
很多同学把红黑树当成“面试魔咒”，但它的存在感比你想象中强得多。C++ 标准库里的std::map、std::set、std::multimap、std::multiset，主流实现（libstdc++、libc++、MSVC STL）底层都是红黑树。你在map里插入、删除、查找一个键，平均和最坏时间复杂度都是 O(log n)。为什么不用哈希表？因为红黑树能提供有序遍历，而且最坏情况不会像哈希表那样因为冲突劣化到 O(n)。
红黑树本质上是一棵“弱平衡”的二叉搜索树。它允许左右子树高度差超过 1，但通过颜色约束把树高限制在 O(log n) 以内。相比 AVL 那种严格控制高度差不超过 1 的铁血纪律，红黑树在插入删除时需要的结构调整更少，所以 STL 在频繁增删场景下选它更划算。
1.2 往工程落地前，先想清楚三个问题
- 你的场景是否需要有序键？需要用
lower_bound、find、顺序遍历，才适合红黑树；如果只按 key 查 value，unordered_map的哈希表通常更快。 - 要不要支持重复键？
map不允许重复，multimap允许。红黑树本身不关心键是否重复，只是插入策略不同。 - 内存和拷贝成本高不高？红黑树每个节点要额外存颜色、左右孩子、父节点指针，比哈希表节点重一些。如果键是可哈希的廉价类型，哈希表往往更轻。
想清楚这几个问题，你就明白“STL 里为什么有 map 还有 unordered_map”了。
2. 平衡二叉树与红黑树的底层逻辑
2.1 二叉搜索树为何会退化成链表
二叉搜索树（BST）的定义很简单：左子树所有节点小于根，右子树所有节点大于根。但只看定义的话，它很容易长歪。按 1、2、3、4、5 的顺序插入，会得到一棵纯右链的树，查找 5 要一路走到叶子，复杂度退化成 O(n)。这就是“不平衡”。
平衡二叉树就是要在每次插入或删除后，把树的高度拉回可控范围。AVL 树用高度差（平衡因子）判断，一旦某个节点左右子树高度差超过 1，就做旋转。红黑树不用高度，用“颜色”约束，最后同样能把树高控制住。
2.2 红黑树五条性质，逐条翻译成大白话
红黑树的定义通常写成五条：
- 每个节点要么红色，要么黑色。
- 根节点是黑色。
- 所有叶子节点（NIL 空节点）是黑色。
- 红色节点的子节点必须是黑色。
- 从任意节点到其每个叶子节点的路径上，黑色节点数量相同。
第一条是状态定义，没什么好说的。
第二条和第三条可以合并理解：树不能以红色节点做根，空叶子一律看成黑色。这里说的“叶子”不是我们日常说的“没有孩子的节点”，而是指所有nullptr哨兵位置。第四条很关键：红色节点不能挨着红色节点，也就是“红红不相连”。第五条是整棵树的灵魂，通常叫“黑高相等”：任意节点往下走到任一空叶子，经过的黑色节点数必须一样。
把四条和五条合起来看，一棵红黑树本质上是在保证“最长路径上的节点数不会超过最短路径的两倍”。为什么？因为红色不能连续出现，所以一条路径上红色节点数最多等于黑色节点数；又因为每条路径黑色节点数相等，所以最长路径长度最多 2 倍最短路径长度。这就是弱平衡。
2.3 “黑高相等”如何保证 O(log n)
如果一棵红黑树有 n 个节点，它的高度 h 满足 h ≤ 2·log₂(n+1)。证明思路很简单：把所有红色节点去掉，黑色节点会形成一棵“黑色平衡”的树，这棵树的节点数至少是原树的一半；而黑色全满的完全二叉树高度是 log 级别。所以红黑树高度是 O(log n)，查找就不会退化。
这也是为什么红黑树敢不用高度差：只要颜色规则不被破坏，性能就有下限保证。
3. 旋转、变色与插入删除修复
3.1 左旋、右旋的几何直观
旋转是平衡二叉树的通用操作，红黑树也只是换个花样用旋转。左旋就是把当前节点的右孩子“提上来”，自己变成右孩子的左孩子；右旋方向相反。用现实类比：原来 A 是领导，B 是 A 的右下手，左旋后 B 当领导，A 变成 B 的下属，B 原来左下手过继给 A 当右下手。
旋转之后中序遍历顺序不变，所以它不会破坏 BST 的“左小右大”语义。旋转是调整结构、维护平衡的基础工具。
用简单 ASCII 图表示右旋：
z / \ y t3 / \ t1 t2 右旋 y 上位后： y / \ t1 z / \ t2 t3左旋就是镜像对称。
3.2 插入修复的三种局面
插入新节点时，默认把它染成红色。为什么选红色？如果染黑，会立刻破坏“黑高相等”，所有经过它的路径黑色节点数都多了一个，修复成本极高；如果染红，只可能破坏“红红不相连”，影响范围更小。
插入后，如果新节点父亲是黑色，直接结束，整棵树依然合法。如果父亲是红色，说明祖父一定存在而且祖父一定是黑色（因为父亲是红，父亲不能是根），这时看叔叔（祖父的另一个孩子）的颜色，分成三种情况：
- 叔叔是红色：把父亲和叔叔都染黑，祖父染红，然后继续把祖父当成新插入的节点向上处理。这是最温和的“变色就能继续”的局面。
- 叔叔是黑色，且当前节点是父亲的右孩子：先对父亲左旋，把情况转成第三种，本质上是把“拐弯”捋直。
- 叔叔是黑色，且当前节点是父亲的左孩子：父亲染黑，祖父染红，再对祖父右旋，局部重新平衡。
我把这三种情况分别叫“变色上推”“左旋拐弯”“右旋定局”。背熟这三步，插入修复就结束了，最后记得把根强制染黑。
3.3 删除修复：为什么都说它比插入难
删除的麻烦在于：你删掉一个节点后，如果这个节点是黑色，某条路径上黑色节点数会少 1，整棵树的“黑高相等”被破坏。所以删除后需要把缺失的黑色“补”回来。常见说法是让替代节点带上“双重黑色”，然后在树里上推，直到把多出来的一层黑色处理掉。
标准做法分四个 case，还是看兄弟节点的颜色和侄子节点的颜色：
- 兄弟是红色：把兄弟染黑，父亲染红，旋转父亲，把兄弟变成黑胡子兄弟，然后继续。
- 兄弟是黑色，且兄弟的两个孩子都是黑色：把兄弟染红，问题向上推给父亲。
- 兄弟是黑色，兄弟的左孩子是红色、右孩子是黑色：先把左孩子染黑，兄弟染红，右旋兄弟，变成第四种情况。
- 兄弟是黑色，兄弟的右孩子是红色：这是最理想的情况，直接让兄弟继承父亲的颜色，父亲染黑，右孩子染黑，然后左旋父亲，问题解决。
删除修复之所以难，不是因为它算法更复杂，而是因为 case 之间会相互转化，而且每一步都在改变局部颜色状态。写代码的时候建议把每一个 case 的“入口条件”写成注释，调试时能省很多时间。
4. C++ 实现与完整代码
下面这份实现我按教学优先的写法组织：只存 key，用哨兵节点nil代替所有空指针。这样做删除修复里即使操作的是“空叶子”，也能安全访问color和parent，逻辑和 CLRS 教材完全一致，代码比一堆nullptr判断更干净。
4.1 数据结构、哨兵与旋转
#include <iostream> template <typename T> class RBTree { private: struct Node { T key; bool color; // true 红，false 黑 Node* left; Node* right; Node* parent; Node(const T& k, bool c, Node* nil) : key(k), color(c), left(nil), right(nil), parent(nil) {} }; Node* nil; Node* root; void leftRotate(Node* x) { Node* y = x->right; x->right = y->left; y->left->parent = x; y->parent = x->parent; if (x->parent == nil) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; } void rightRotate(Node* x) { Node* y = x->left; x->left = y->right; y->right->parent = x; y->parent = x->parent; if (x->parent == nil) root = y; else if (x == x->parent->right) x->parent->right = y; else x->parent->left = y; y->right = x; x->parent = y; } public: RBTree() { nil = new Node(T{}, false, nullptr); nil->left = nil->right = nil->parent = nil; root = nil; } };注意nil自己成为一个黑色节点，所有空位置都指向它。旋转函数里的y->left->parent = x即使y->left是nil也安全，因为nil有parent字段。
4.2 插入与插入修复
private: void insertFixup(Node* z) { while (z->parent->color == true) { if (z->parent == z->parent->parent->left) { Node* y = z->parent->parent->right; // 叔叔 if (y->color == true) { // 情况1：叔叔红色，变色后继续上推 z->parent->color = false; y->color = false; z->parent->parent->color = true; z = z->parent->parent; } else { // 情况2：当前节点是右孩子，先左旋父节点 if (z == z->parent->right) { z = z->parent; leftRotate(z); } // 情况3：父黑、祖红、右旋祖父 z->parent->color = false; z->parent->parent->color = true; rightRotate(z->parent->parent); } } else { // 对称分支：parent 是祖父的右孩子 Node* y = z->parent->parent->left; if (y->color == true) { z->parent->color = false; y->color = false; z->parent->parent->color = true; z = z->parent->parent; } else { if (z == z->parent->left) { z = z->parent; rightRotate(z); } z->parent->color = false; z->parent->parent->color = true; leftRotate(z->parent->parent); } } } root->color = false; } public: void insert(const T& key) { Node* z = new Node(key, true, nil); Node* y = nil; Node* x = root; while (x != nil) { y = x; if (key < x->key) x = x->left; else if (key > x->key) x = x->right; else { delete z; return; // 已存在，不处理重复键 } } z->parent = y; if (y == nil) root = z; else if (key < y->key) y->left = z; else y->right = z; insertFixup(z); }插入修复的核心就是三种情况。实际写代码时，我建议把对称分支也完整写出来，不要靠“这里对称”的注释脑补，否则调试时会很痛苦。
4.3 删除与删除修复
删除操作先按普通 BST 删节点，然后根据被删节点的原始颜色决定是否调用eraseFixup。只有被删节点是黑色时才需要修复，因为只有黑色节点的减少会破坏黑高。
private: Node* minimum(Node* x) const { while (x->left != nil) x = x->left; return x; } void transplant(Node* u, Node* v) { if (u->parent == nil) root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; v->parent = u->parent; } void eraseFixup(Node* x) { while (x != root && x->color == false) { if (x == x->parent->left) { Node* w = x->parent->right; if (w->color == true) { w->color = false; x->parent->color = true; leftRotate(x->parent); w = x->parent->right; } if (w->left->color == false && w->right->color == false) { w->color = true; x = x->parent; } else { if (w->right->color == false) { w->left->color = false; w->color = true; rightRotate(w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = false; w->right->color = false; leftRotate(x->parent); x = root; } } else { Node* w = x->parent->left; if (w->color == true) { w->color = false; x->parent->color = true; rightRotate(x->parent); w = x->parent->left; } if (w->right->color == false && w->left->color == false) { w->color = true; x = x->parent; } else { if (w->left->color == false) { w->right->color = false; w->color = true; leftRotate(w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = false; w->left->color = false; rightRotate(x->parent); x = root; } } } x->color = false; } Node* findNode(const T& key) const { Node* cur = root; while (cur != nil) { if (key == cur->key) return cur; else if (key < cur->key) cur = cur->left; else cur = cur->right; } return nil; } public: void erase(const T& key) { Node* z = findNode(key); if (z == nil) return; Node* y = z; Node* x; bool yOriginalColor = y->color; if (z->left == nil) { x = z->right; transplant(z, z->right); } else if (z->right == nil) { x = z->left; transplant(z, z->left); } else { y = minimum(z->right); yOriginalColor = y->color; x = y->right; if (y->parent == z) { x->parent = y; } else { 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 (yOriginalColor == false) eraseFixup(x); delete z; }这里最难理解的是“后继补位”分支：当被删节点有两个孩子时，实际真正删除的是右子树里的最小节点 y，然后把 y 的内容搬到 z 的位置，再给 y 换上 z 的颜色。这样不会破坏红黑树颜色结构，只是物理位置上换了人。
4.4 查找、遍历与自检函数
public: bool contains(const T& key) const { return findNode(key) != nil; } void inorder(std::ostream& os = std::cout) const { inorderRec(root, os); os << "\n"; } private: void inorderRec(Node* n, std::ostream& os) const { if (n == nil) return; inorderRec(n->left, os); os << n->key << " "; inorderRec(n->right, os); } public: // 校验红黑树五条性质是否合法，返回高度（用于测试） int checkValid() const { bool ok = true; int blackHeight = 0; validateRec(root, ok, blackHeight); return ok ? blackHeight : -1; } private: void validateRec(Node* n, bool& ok, int& blackCount) const { if (n == nil) { blackCount = 1; return; } int lb = 0, rb = 0; validateRec(n->left, ok, lb); validateRec(n->right, ok, rb); if (lb != rb) ok = false; // 性质5 if (n->color == true && (n->left->color == true || n->right->color == true)) ok = false; // 性质4 blackCount = lb + (n->color == false ? 1 : 0); } };checkValid会在每次操作后返回黑高。如果返回 -1，说明性质被破坏。我写红黑树时基本把它当成“测试仪器”，每次插入删除后都跑一遍，比肉眼快得多。
5. 红黑树在 STL / 数据库 / 工程中的不同表现
5.1 map 和 set 为什么选红黑树而不是 AVL
AVL 要求任何节点的左右子树高度差不超过 1，查找性能确实更好；但为了维持这种铁血平衡，插入删除时的旋转次数往往比红黑树多。红黑树允许最多两倍高度差，读操作稍微慢一点点，但写操作更省。
工程场景里，map的插入删除比 AVL 更频繁，所以 STL 选红黑树。这不是说 AVL 没有用武之地，它适合“查询远多于修改”的场景，比如数据库内存索引、只读配置表。不要在面试时说“红黑树比 AVL 快”，这个说法不严谨，准确说法是“红黑树在频繁插入删除时调整成本更低，AVL 查询更严格但调整更频繁”。
5.2 B+ 树和红黑树有什么关系
网上经常有人把 B+ 树和红黑树搞混，其实 B+ 树不是红黑树。B+ 树是多路搜索树，一个节点存多个 key，适合磁盘 IO 的块读写；红黑树是内存里的二叉搜索树。数据库 InnoDB 索引选 B+ 树，是因为它能用一次磁盘 IO 读取多条索引记录，且叶子节点链式相连非常适合范围扫描。
红黑树在数据库领域并非主角，但不少存储引擎的内存缓冲、日志索引、锁管理里会用红黑树做有序结构。Redis 的有序集合 zset 底层是“跳表 + 哈希表”的组合，也不是红黑树；不过 Redis 里某些内部数据结构确实可以用红黑树思路理解。
碰到“B+ 树是红黑树吗”这类问题，直接回答不是，抓准三点：B+ 树是多路、叶子链式、面向磁盘；红黑树是二叉、面向内存。
5.3 工程中还有哪些地方藏着红黑树
- Linux 内核的 CFS 调度器早年用红黑树管理进程，后来改成红黑树队列的组合。
- Linux 虚拟内存管理中的
vm_area_struct查找用红黑树。 - 很多内存分配器会用红黑树管理空闲块。
- C++ 的
std::map/std::set不必多说。
能熟练写出红黑树后，再看这些系统源码会顺畅很多，因为它们大多是“红黑树 + 自定义比较规则”的壳。
6. 面试与实战中的高频坑
6.1 五个让我调试到深夜的 bug
- 插入修复里忘了把根染黑。性质2要求根是黑色，但插入后向上变色的过程中可能把根变红，循环结束后必须统一处理。
- 左右对称写反。右侧分支的旋转方向完全是左侧的镜像，很多人在
eraseFixup右侧分支里习惯性复用左旋，导致树结构错乱。我的办法是每次对称分支都写完整注释。 - 删除后继时没有正确处理
y->parent == z的情况。如果 y 就是 z 的直接右孩子，不能先做transplant(y, y->right)，否则会把 z 和 y 的父子关系弄断。 - 哨兵节点的
parent被反复覆盖。单哨兵实现里，transplant到 nil 时会把nil->parent指向某个父节点，其他位置的 nil 的 parent 可能还是旧的。只要当前访问的 x 的 parent 正确，就不会出错，但如果你在调试时打印所有节点，看到 nil 的 parent 乱跳会非常慌。 - 忘记把新节点的左右孩子指向 nil。插入新节点时，
Node构造函数已经处理了，但如果你自己malloc再赋值，很容易让新节点的 left/right 是随机值，后续检查n->left->color直接崩。
6.2 如何快速验证一棵树的合法性
我强烈建议写一个checkValid()，在每次插入删除后调用，同时打印中序序列，确认没有破坏 BST 有序性。
验证分三步：先遍历中序，看是否单调递增；再递归检查性质4——红色节点的孩子不能是红；最后检查性质5——每个节点的左右子树黑高必须相等。
实测下来，这个自检函数帮我抓到的 bug 比单元测试还多。写红黑树如果没有这一步，调试会非常痛苦，因为树一旦歪了，你根本不知道是插入问题还是删除问题。
6.3 面试这样回答能加分
面试官问你红黑树，别急着背 case。先讲“为什么要平衡”，再讲“为什么红黑树允许一定不平衡”，最后说“插入的关键是变色上推，删除的关键是兄弟节点分担黑色”。把五条性质和 O(log n) 的证明讲清楚，已经超过大多数候选人。
如果被追问“会不会手写”，我的建议是：不要从零默写整个类，先写旋转，再写插入修复的三个 case，删除修复能说出四个 case 的转化关系就够了。工程面试更看重思路，不要求你 20 分钟默写 300 行。
我在实际写红黑树的过程中，最大的体会是：它不需要死记每个 case，关键是理解“黑色节点数必须相等”这个不变式。只要这个核心守住，所有旋转变色都是在朝这个目标调整。最后再分享一个小技巧：调红黑树时建议把颜色打印出来，用R和B标识，再配合中序遍历序列检查，定位问题比单看数字快得多。红黑树不是魔法，它只是把“黑高相等”这件事执行得足够彻底而已。
