1. 为什么红黑树成了面试的“硬通货”
先聊点实际的。你打开任何一份 C++ 后端或基础架构岗位的面试题清单，红黑树几乎从未缺席。这还真不是面试官故意刁难——红黑树几乎就是现代计算机系统里“平衡与效率”这对矛盾的标准解。C++ 标准库里的std::map、std::set、std::multimap、std::multiset，Linux 内核的 CFS 调度器、epoll就绪队列，Nginx 的定时器，甚至 Java 的TreeMap和TreeSet，底层清一色是它。绕过红黑树，等于绕过了这些基础设施的共同骨架。
有意思的是，红黑树明明叫“红黑”，但它最核心的思想跟颜色本身没什么关系。颜色只是规则的载体，真正的价值在于它用一种极简洁的着色规则，把一棵二叉搜索树的高度控制在O(log n)级别。面试里问红黑树，多数时候问的不是“你背过几个旋转情形”，而是：左旋和右旋到底在干什么？插入和删除为什么需要调整？你能否把调整过程用代码干干净净地写出来？
我在这篇里要做的，是用硬核图解的方式把整棵红黑树拆开，从原理一路推到 C++ 完整实现。我不会只给你贴一段能跑通的代码，而是把每个调整场景背后的动机讲清楚。读完这篇，你应该能做到：不看参考，徒手写出红黑树的插入与删除旋转逻辑，并且能在面试时把“为什么要这样旋转”解释得明明白白。
先说清楚适用范围。如果你是那种已经把二叉搜索树玩得滚瓜烂熟、但一提平衡树就头皮发麻的 C++ 学习者，这篇就是给你准备的。如果你在准备面试，想要的是“原理 + 手写代码”的完整链路，这篇同样合适。不过我要提前泼一盆冷水：红黑树的删除调整确实不简单，如果你指望十分钟速成，现实点说，不现实。但只要你愿意把每一个 case 走一遍，它的复杂度实际上远没有传说中那么可怕。
2. 红黑树到底在平衡什么
在看旋转和染色之前，必须先建立一个共识：红黑树本质是一棵增加了约束条件的二叉搜索树。它保留了 BST 的全部性质——左子树所有节点小于根节点、右子树所有节点大于根节点、中序遍历有序——然后额外加了五条约束。网上流传的说法五花八门，我建议你以这个版本为准：
- 每个节点非红即黑。
- 根节点是黑色。
- 每个叶子节点（这里的叶子指的是 NIL 空节点）是黑色。
- 如果一个节点是红色，那么它的两个子节点必须是黑色，也就是说红节点不能有红孩子。
- 从任一节点到其每个叶子节点的所有路径上，包含相同数目的黑节点。
前四条都很直观，关键是第五条。它可以等价地理解为：对于每一个节点，它到所有后代叶子的路径上，黑色节点的数量必须相等。这个数量有一个专门术语，叫黑高。
那有人要问了，为什么这五条约束就能保证树的高度是O(log n)？这个证明的推演过程其实很漂亮。
考虑一棵红黑树，如果我把所有的红节点都“折叠”进它们的黑父节点中，也就是说让红节点和黑父节点合并成一个“超节点”，那么原来树上的每条路径就可以视作由若干个这样的超节点串联而成。由于红节点不能有红孩子，每个超节点内部最多只有一个红节点。又因为所有路径的黑节点数量相等，折叠之后整棵树的所有路径，长度就完全相等了——这就变成了一棵理想平衡的 2-3-4 树。一棵包含n个内部节点的 2-3-4 树，高度上界是log_2(n+1)。折叠回去，红节点最多只会让路径高度翻倍，因此红黑树的高度不超过2 * log_2(n+1)。
这个证明理解起来需要一个抽象跳跃，但结论非常好用：红黑树的高度最多不会超过理想平衡二叉树的二倍。这就是为什么它能在最坏情况下依然保证插入、删除、查找都是O(log n)。AVL 树的平衡更严格，它的高度接近1.44 * log_2 n，比红黑树更矮，但代价是旋转更频繁。红黑树稍微“放松”了一点平衡约束，换来了更少的旋转次数。在随机插入删除频繁的场景下，红黑树的整体性能往往更占优势，这就是工程上大量选它的原因。
这里有个常见的认知误区我必须纠正：红黑树不是“近似平衡”的形容词，它有精确的数学保证。所谓的“近似”只是跟 AVL 那种严格左右子树高度差不超过 1 相比，它的平衡约束更宽松，但它的高度上界依然是一个确定的可证明的O(log n)。面试时把这个证明讲出来，和只会背口诀的候选人立刻拉开了差距。
3. 旋转操作：红黑树唯一改变结构的武器
红黑树的调整过程，说穿了就是两件事：变色和旋转。变色不改变树的形态，只改变节点的颜色记录；旋转则真正改变了节点之间的父子关系，是维护 BST 有序性的核心工具。旋转分为左旋和右旋，它们互为镜像操作。
3.1 右旋的精确定义
先看右旋。假设y是根，它有一个左孩子x，x的右孩子是β，那么右旋我们这样操作：
x替换y成为新的子树根。y变成x的右孩子。β（即x原来的右子树）变成y的左子树。
对应 C++ 代码画成伪代码是：
rightRotate(y): x = y.left T2 = x.right x.right = y y.left = T2 y.parent = x x.parent = y.parent if y.parent is null: root = x else if y is left child of y.parent: y.parent.left = x else: y.parent.right = x T2.parent = y左旋完全对称，只是把方向反过来。核心就一句话：左旋是让右孩子上位，右旋是让左孩子上位。旋转操作不会破坏二叉搜索树的有序性，因为β这棵子树里的所有节点，在旋转前既大于x又小于y（右旋场景下，β是x的右子树，所以它大于x；同时β又是y的左子树，所以它小于y）。旋转后β变成y的左子树，依然满足“大于x且小于y”的中序位置。旋转前后，整棵树的中序遍历结果完全不变。
3.2 旋转的直观理解：保持中序序列不变
很多人看旋转代码一脸懵，是因为不理解为什么这样搬来搬去，树还是合法的。我建议你换个角度看：旋转的本质是在不改变中序遍历序列的前提下，把两个节点的上下关系对调。你可以把中序遍历序列想象成一条排好队的队伍，旋转对调了其中两个相邻节点的“上下位置”，但队伍本身没有人离开、没有新人插队。正是因为这个性质，任何情况下我们都可以放心大胆地用旋转去调整结构，不用担心搞乱 BST 的有序性。
3.3 C++ 节点结构与旋转实现
现在动手写代码。我采用一个简洁的节点定义，用color枚举区分红黑，用parent指针支持向上回溯。这是红黑树实现和普通 BST 最大的不同——没有父指针的话，删除调整根本没法高效实现。
#include <iostream> enum Color { RED, BLACK }; struct Node { int key; Color color; Node *left, *right, *parent; explicit Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} };我默认新节点初始为红色。为什么？因为红色节点只受“不能有红孩子”这条规则约束，不会破坏黑色节点数量相等这一核心性质。初始染红可以把问题限制在局部，后续调整只需要处理连续的红色冲突。如果初始染黑，那么每当插入一个节点，该路径的黑高就会立即变化，修复起来远比处理红冲突复杂。这个选择的理由面试官问到的概率极高，务必理解。
右旋和左旋实现如下：
void leftRotate(Node*& root, Node* x) { Node* y = x->right; x->right = y->left; if (y->left != nullptr) y->left->parent = x; y->parent = x->parent; if (x->parent == nullptr) 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*& root, Node* y) { Node* x = y->left; y->left = x->right; if (x->right != nullptr) x->right->parent = y; x->parent = y->parent; if (y->parent == nullptr) root = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; x->right = y; y->parent = x; }写旋转最容易出 bug 的地方是空指针处理。比如x->right可能为空，那么x->right->parent = y这行就会崩。另一个高频 bug 是父指针更新遗漏：旋转涉及两个节点的父指针变更，加上子树根与祖父的链接关系，一共三处，漏掉任意一处，后续调整时回溯就会出错。我建议你写完旋转后做个自查：从祖父视角看，这棵子树根有没有正确替换；从β视角看，它的 parent 有没有正确指向新父节点；从原父节点视角看，它的孩子指针有没有被覆盖成新子节点。三个方向都对了，旋转才算真的写完。
4. 插入：从普通 BST 插入到红黑恢复
红黑树的插入分两个阶段。第一阶段是普通的 BST 插入——按大小比较找到合适位置，挂上新节点。第二阶段是调用修复函数fixInsert，恢复红黑性质。第一阶段不需要我多讲，第二阶段是重点。
4.1 插入后冲突的根源
新节点记为z，初始为红色。插入后可能的违规情况只有一种：z是红的，且它的父节点也是红的。因为根是黑的，所以这种冲突必然发生在非根节点上。
修复的思路围绕z的叔叔节点uncle的颜色展开。叔叔是父节点的兄弟，也就是祖父的另一个孩子。为什么叔叔的颜色如此关键？因为黑高的约束决定了我们只能通过两种手段修复：把红色冲突向上传递，或者通过旋转和重新着色一次性解决。
4.2 Case 1：叔叔是红色
这是最简单的场景，也是红黑树插入里教科书必讲的第一种情况。假设z是红，z.p是红，uncle也是红，祖父g必然是黑（否则原来的树就已经违规了，也就是红节点不能有红孩子）。此时我们把祖父变红，把父亲和叔叔变黑，再把冲突上移到祖父。
为什么要这样处理？这一步的本质是把“两个红孩子”转变成“祖父红、二十个孙全黑”，等于把红色向上推了两层。红黑树的第五条规定，每条路径黑高必须相同。修改后，从祖父出去的每条路径，黑色节点数跟修改前完全一样——原来祖父是黑，父和叔是红，现在祖父是红，父和叔是黑，经过这三个节点的路径上黑节点总数没有变化。所以这次变色只是把违规位置从z转移到祖父。接下来把z指向祖父，继续循环，直到根为止。
如果祖父是根，循环到根时直接把根染黑即可，这就是为什么修复函数的最后一行永远是无条件root->color = BLACK。这行代码同时保证了根节点为黑的规则，并且因为根变黑，所有路径的黑高统一加 1，整棵树的性质依然满足。
4.3 Case 2 + Case 3：叔叔是黑色，需要旋转
如果叔叔是黑色，那就不能靠单纯的变色解决了。因为把父亲变黑会改变该路径的黑高，导致与其他路径的黑色数量不相等。这时候必须旋转。
这里的调整还分两种情况。先说 Case 3，也就是最直接的场景：z是红色，z.p是红色，uncle是黑色，且z与z.p的孩子方向一致（比如z是左孩子，z.p也是左孩子）。这种情况下，我们对祖父做一次右旋，然后把z.p染黑、祖父染红。
你可能想问，为什么右旋之后颜色要这么安排？我们来推演一下。右旋后，原来的父亲p变成子树根，原来的祖父g变成p的右孩子。为了保证这个局部子树不违反规则，新的子树根应该是黑色——二叉树的每一条经过这个子树的路径，都会经过这个根，如果根是红色，它可能和外面的红色祖先冲突。而g变成红色，是因为g原本的右子树（也就是叔叔uncle）是黑色，g变红后，经过g和uncle这一路的黑节点数量正好和经过p、z的黑节点数量相等。所以 Case 3 的染色不是随便定的，它是为了继续维持黑高相等这个硬约束。
Case 2 则是z与z.p孩子方向相反的情况。比如z的父是左孩子但z是右孩子。此时不能直接对祖父旋转，因为旋转后z.p和z的位置会让结构变得别扭，无法通过一次旋转完成修复。标准做法是：先对父节点做一次左旋，把z提升到父的位置，然后我们就瞬间得到了 Case 3 的格局——z与z.p（现在指向原来的祖父）方向一致了。之后套用 Case 3 处理即可。这个“先转成 Case 3”的技巧，本质是把非对称情况统一成对称情况，减少代码分支。
4.4 插入修复完整实现
综合上面的分析，插入修复完整代码如下：
void fixInsert(Node*& root, Node* z) { while (z->parent != nullptr && z->parent->color == RED) { Node* grand = z->parent->parent; if (z->parent == grand->left) { Node* uncle = grand->right; if (uncle != nullptr && uncle->color == RED) { // Case 1: 叔叔红色，变色后向上回溯 z->parent->color = BLACK; uncle->color = BLACK; grand->color = RED; z = grand; } else { if (z == z->parent->right) { // Case 2: 当前节点是右孩子，先左旋父节点变成 Case 3 z = z->parent; leftRotate(root, z); } // Case 3: 当前节点是左孩子，右旋祖父并变色 z->parent->color = BLACK; grand->color = RED; rightRotate(root, grand); } } else { Node* uncle = grand->left; if (uncle != nullptr && uncle->color == RED) { z->parent->color = BLACK; uncle->color = BLACK; grand->color = RED; z = grand; } else { if (z == z->parent->left) { z = z->parent; rightRotate(root, z); } z->parent->color = BLACK; grand->color = RED; leftRotate(root, grand); } } } root->color = BLACK; }插入接口很直接：按 BST 规则找插入位置，构造红节点挂上去，然后调用fixInsert。
void insert(Node*& root, int key) { Node* z = new Node(key); Node* y = nullptr; Node* x = root; while (x != nullptr) { y = x; if (key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y == nullptr) { root = z; } else if (key < y->key) { y->left = z; } else { y->right = z; } fixInsert(root, z); }注意这里没处理重复 key。实际使用中你可以根据需求改成“重复时覆盖”或“插入左/右子树”，面试时指出这个细节，反而能加分。
4.5 插入操作的时间复杂度
插入的循环最坏情况下沿着树向上回溯，每次回溯一层。因为树高是O(log n)，所以循环最多执行O(log n)次。但要注意，Case 3 执行完一次旋转后立即终止循环，只有 Case 1 会继续向上回溯。所以严格说，插入最多执行 2 次旋转（一次 Case 2 的预旋转，一次 Case 3 的正式旋转），其它都是变色。这正是红黑树在工程上高效的依据——变色是 O(1) 的指针操作，旋转也是 O(1) 的指针操作，常数很小。
5. 删除：最容易被问倒的硬骨头
如果说红黑树插入是“热身”，那么删除就是真正的“修罗场”。网上关于删除的教程满天飞，但大多数要么只是贴代码，要么用让人头晕的宗门图例。这一节我会换一种思路，先把删除带来的问题定性，再逐个 CASE 分析。
5.1 先看 BST 删除的三种情况
普通 BST 删除节点有三种情况：
- 被删节点没有孩子：直接摘掉，让父节点的相应孩子置空。
- 被删节点只有一个孩子：用孩子顶替被删节点。
- 被删节点有两个孩子：用中序后继节点的 key 覆盖被删节点的 key，然后删掉后继节点。后继节点必然没有左孩子，这样就把问题化简成了“删除一个最多只有一个孩子的节点”。
红黑树的删除同样遵循这套逻辑，只是删除完成后需要检查红黑性质有没有被破坏。
5.2 删除后的问题定性
删除操作的麻烦点在于：如果被删节点（或实际被删的后继节点）原来是黑色，那么某条路径上的黑色节点数就会少 1，第五条规则被破坏。我们把“少了 1 个黑”的感觉抽象成：这个位置出现了一个“双黑”节点，表示这条路径比其它路径少一个黑色。修复的过程就是想办法把这个多余的黑“消化”掉，直到整个树重新平衡。
如果被删节点是红色，事情就简单了。红色节点不影响黑高，删除后红黑性质基本不会被破坏，只可能破坏“红节点不能有红孩子”这条。但因为被删节点如果是红色，它的父节点和孩子节点都必须是黑色（否则原树已经违规），直接摘除不会制造新的红冲突。所以一句话：删红节点，什么都不用修。真正的修复只发生在被删节点是黑色且它所在路径黑高减少时。我们把实际删除后顶替上来的节点记为x，如果x是红色，直接染黑就完事；如果x是黑色，需要走进删除修复循环。
5.3 删除修复的四种情形
删除修复的核心是：保持x节点所在路径的黑高不比其他路径少。x被视为“额外携带一层黑色”，它的兄弟是w。根据w的颜色以及w的孩子颜色，分成四个 Case。
Case 1：兄弟是红色
这时候x的父节点必然是黑色（否则红节点不能有红孩子）。做法是：把父节点染红，兄弟染黑，然后对父节点做一次旋转（如果x是左孩子，就左旋父节点）。旋转后，x的兄弟变成了原来w的一个黑色孩子，于是问题转化为兄弟是黑色的其它 Case。
这一步的目的是在不改变黑高的前提下，把红兄弟转化成黑兄弟。为什么可以这样变换？因为旋转后，x的路径上多了一个黑节点（原来的w下来了），我们通过把w变黑、父变红，抵消了旋转造成的变化。
Case 2：兄弟是黑色，且兄弟的两个孩子都是黑色
这说明w的整棵子树无法“借”出多余的黑色。做法是：把w染红，然后把多出来的那层黑上移到父节点。如果父节点原来是红色，循环在此结束，把父节点染黑即可；如果父节点是黑色，则父节点成为新的x，继续循环。
这个 Case 的直觉是：兄弟子树里所有路径都少一个黑，那么把兄弟变红后，兄弟子树的黑高减 1，正好和x路径持平。剩下的问题是父节点这整棵子树相对外部少了 1 层黑，所以把问题抛给父节点。
Case 3：兄弟是黑色，兄弟的左侧孩子是红色，右侧孩子是黑色
这是个“过渡 Case”。做法是：把兄弟染红，把兄弟的左孩子染黑，然后右旋兄弟。旋转后，新的兄弟是原来兄弟的左孩子，它是黑色且它的右孩子是红色。这就转化成了 Case 4。
这个转换的目的是构造出 Case 4 需要的结构——一个黑色兄弟，兄弟的右孩子是红色。注意这个 Case 只调整兄弟子树内部，不涉及x路径的黑高，所以不会让情况变得更糟。
Case 4：兄弟是黑色，兄弟的右侧孩子是红色（x是左孩子的前提下）
这是直接解决问题的 Case。做法是：把父节点的颜色赋给兄弟，把父节点染黑，兄弟的右孩子染黑，然后左旋父节点。旋转后，x路径上多了一个黑色节点，双黑被消除。整个树重新平衡，修复结束。
这里的颜色安排需要仔细推敲。父节点p原来的颜色是未知的，可能是红也可能是黑。旋转后w取代了p成为子树根，为了不破坏外部黑高，w必须继承p的原色。p变成黑色是为了给x路径补上缺失的黑；w的右孩子变黑是为了维持w右子树的黑高。这个 Case 执行完后，从w的视角看，两条子路径的黑高都恢复平衡，循环终止。
对称地，如果x是右孩子，处理方式镜像翻转即可。
5.4 删除修复的实现与图解对照
直接看代码。这段实现我加入了哨兵判断：实际工程里可以用nullptr配合 careful 判空，也可以用一个静态 NIL 节点。为了简洁这里用nullptr，但你要清楚面试手写时，判空是容易出错的点。
void fixDelete(Node*& root, Node* x) { while (x != root && (x == nullptr || x->color == BLACK)) { Node* parent = x->parent; if (x == parent->left) { Node* w = parent->right; if (w != nullptr && w->color == RED) { // Case 1 w->color = BLACK; parent->color = RED; leftRotate(root, parent); w = parent->right; } if ((w->left == nullptr || w->left->color == BLACK) && (w->right == nullptr || w->right->color == BLACK)) { // Case 2 w->color = RED; x = parent; } else { if (w->right == nullptr || w->right->color == BLACK) { // Case 3 if (w->left != nullptr) w->left->color = BLACK; w->color = RED; rightRotate(root, w); w = parent->right; } // Case 4 w->color = parent->color; parent->color = BLACK; if (w->right != nullptr) w->right->color = BLACK; leftRotate(root, parent); x = root; } } else { // 对称逻辑省略，和上面完全镜像 Node* w = parent->left; if (w != nullptr && w->color == RED) { w->color = BLACK; parent->color = RED; rightRotate(root, parent); w = parent->left; } if ((w->left == nullptr || w->left->color == BLACK) && (w->right == nullptr || w->right->color == BLACK)) { w->color = RED; x = parent; } else { if (w->left == nullptr || w->left->color == BLACK) { if (w->right != nullptr) w->right->color = BLACK; w->color = RED; leftRotate(root, w); w = parent->left; } w->color = parent->color; parent->color = BLACK; if (w->left != nullptr) w->left->color = BLACK; rightRotate(root, parent); x = root; } } } if (x != nullptr) x->color = BLACK; }这里有一个非常容易踩的坑：当x是nullptr时，进入循环的条件判定会依赖x->color的读取。我上面写的是(x == nullptr || x->color == BLACK)来避免空指针访问。但在循环体内，w->left或w->right也可能为空，所以在 Case 3 访问w->right->color之前必须先判空。很多初学者在删除一个只有一个孩子且为黑色的节点时，x就是那个唯一的子节点，长大后为空，此时判空逻辑必须处理好，否则直接段错误。
5.5 删除主逻辑
有了修复函数，删除主逻辑的核心反而是找到实际要删除的节点并正确摘除：
void transplant(Node*& root, Node* u, Node* v) { if (u->parent == nullptr) root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; if (v != nullptr) v->parent = u->parent; } void deleteNode(Node*& root, int key) { Node* z = search(root, key); if (z == nullptr) return; Node* y = z; Color y_original_color = y->color; Node* x; if (z->left == nullptr) { x = z->right; transplant(root, z, z->right); } else if (z->right == nullptr) { x = z->left; transplant(root, z, z->left); } else { y = minimum(z->right); y_original_color = y->color; x = y->right; if (y->parent == z) { if (x != nullptr) x->parent = y; } else { transplant(root, y, y->right); y->right = z->right; y->right->parent = y; } transplant(root, z, y); y->left = z->left; y->left->parent = y; y->color = z->color; } delete z; if (y_original_color == BLACK) { fixDelete(root, x); } }这里要注意x的初始化。当z有右孩子且我们使用后继y时，x = y->right可能为空。如果y的父节点不是z，transplant(root, y, y->right)之后y被摘除，y->right成了自由节点。后续fixDelete需要用x作为“携带双黑”的起点。如果x为空，fixDelete里要能够处理空的x节点。
关于minimum函数的实现，就是沿着右子树一路向左：
Node* minimum(Node* node) { while (node->left != nullptr) node = node->left; return node; }5.6 为什么说删除是面试分水岭
插入调整只有三种 case，而且逻辑相对直观，大多数人背一背能应付。删除调整有四种 case，还分左右对称，每种 case 内部还可能有嵌套转换。面试时能把删除 case 的原理解释清楚而不是单纯背代码的人，说实话不多。我见过的候选人里，能讲清楚“Case 2 为什么把兄弟染红，然后问题为什么上移到父节点”的，基本上都能过算法轮。
我的建议是，练习时不要对着代码硬读，而是按“兄弟是什么颜色→兄弟的孩子是什么颜色”这个决策树走。自己画一颗失衡的树，手动按 case 推演一遍，再用代码验证。推演四五遍之后，你会发现删除其实比插入更有规律——它本质上就是不断想办法从兄弟子树“借一个黑色”。
6. 完整代码与调试技巧
到这里，核心逻辑都讲完了。下面是完整可编译的 C++ 实现，包含中序遍历和查找接口。为了可读性，异常处理和内存管理我做了简化，实际项目里请务必用 RAII 或智能指针。
#include <iostream> enum Color { RED, BLACK }; struct Node { int key; Color color; Node *left, *right, *parent; explicit Node(int k) : key(k), color(RED), left(nullptr), right(nullptr), parent(nullptr) {} }; class RBTree { public: RBTree() : root(nullptr) {} void insert(int key) { Node* z = new Node(key); Node* y = nullptr; Node* x = root; while (x != nullptr) { y = x; if (key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y == nullptr) root = z; else if (key < y->key) y->left = z; else y->right = z; fixInsert(z); } void remove(int key) { Node* z = search(root, key); if (z == nullptr) return; Node* y = z; Color y_original_color = y->color; Node* x; if (z->left == nullptr) { x = z->right; transplant(z, z->right); } else if (z->right == nullptr) { x = z->left; transplant(z, z->left); } else { y = minimum(z->right); y_original_color = y->color; x = y->right; if (y->parent == z) { if (x != nullptr) 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; } delete z; if (y_original_color == BLACK) fixDelete(x); } void inorder() { inorderHelper(root); std::cout << std::endl; } private: Node* root; void leftRotate(Node* x) { Node* y = x->right; x->right = y->left; if (y->left != nullptr) y->left->parent = x; y->parent = x->parent; if (x->parent == nullptr) 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* y) { Node* x = y->left; y->left = x->right; if (x->right != nullptr) x->right->parent = y; x->parent = y->parent; if (y->parent == nullptr) root = x; else if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; x->right = y; y->parent = x; } void fixInsert(Node* z) { while (z->parent != nullptr && z->parent->color == RED) { Node* grand = z->parent->parent; if (z->parent == grand->left) { Node* uncle = grand->right; if (uncle != nullptr && uncle->color == RED) { z->parent->color = BLACK; uncle->color = BLACK; grand->color = RED; z = grand; } else { if (z == z->parent->right) { z = z->parent; leftRotate(z); } z->parent->color = BLACK; grand->color = RED; rightRotate(grand); } } else { Node* uncle = grand->left; if (uncle != nullptr && uncle->color == RED) { z->parent->color = BLACK; uncle->color = BLACK; grand->color = RED; z = grand; } else { if (z == z->parent->left) { z = z->parent; rightRotate(z); } z->parent->color = BLACK; grand->color = RED; leftRotate(grand); } } } root->color = BLACK; } void fixDelete(Node* x) { while (x != root && (x == nullptr || x->color == BLACK)) { Node* parent = x->parent; if (x == parent->left) { Node* w = parent->right; if (w != nullptr && w->color == RED) { w->color = BLACK; parent->color = RED; leftRotate(parent); w = parent->right; } if ((w->left == nullptr || w->left->color == BLACK) && (w->right == nullptr || w->right->color == BLACK)) { w->color = RED; x = parent; } else { if (w->right == nullptr || w->right->color == BLACK) { if (w->left != nullptr) w->left->color = BLACK; w->color = RED; rightRotate(w); w = parent->right; } w->color = parent->color; parent->color = BLACK; if (w->right != nullptr) w->right->color = BLACK; leftRotate(parent); x = root; } } else { Node* w = parent->left; if (w != nullptr && w->color == RED) { w->color = BLACK; parent->color = RED; rightRotate(parent); w = parent->left; } if ((w->left == nullptr || w->left->color == BLACK) && (w->right == nullptr || w->right->color == BLACK)) { w->color = RED; x = parent; } else { if (w->left == nullptr || w->left->color == BLACK) { if (w->right != nullptr) w->right->color = BLACK; w->color = RED; leftRotate(w); w = parent->left; } w->color = parent->color; parent->color = BLACK; if (w->left != nullptr) w->left->color = BLACK; rightRotate(parent); x = root; } } } if (x != nullptr) x->color = BLACK; } void transplant(Node* u, Node* v) { if (u->parent == nullptr) root = v; else if (u == u->parent->left) u->parent->left = v; else u->parent->right = v; if (v != nullptr) v->parent = u->parent; } Node* search(Node* node, int key) { while (node != nullptr && node->key != key) { if (key < node->key) node = node->left; else node = node->right; } return node; } Node* minimum(Node* node) { while (node->left != nullptr) node = node->left; return node; } void inorderHelper(Node* node) { if (node == nullptr) return; inorderHelper(node->left); std::cout << node->key << (node->color == RED ? "(R) " : "(B) "); inorderHelper(node->right); } }; int main() { RBTree tree; for (int k : {10, 20, 30, 15, 25, 5, 1, 2, 3, 4}) tree.insert(k); tree.inorder(); tree.remove(20); tree.remove(10); tree.inorder(); return 0; }这段代码我按标准教材的方式封装成了类，旋转函数在类内部直接访问root，相比前面的全局函数风格更贴近实际工程。你编译运行后，应该能看到中序遍历始终有序，而且删除前后都满足红黑性质。怎么验证性质是否正确？中序遍历只能验证 BST 有序性，不能验证红黑规则。我建议你写一个validate()递归函数，检查组件的五条规则，这是调试红黑树最重要的工具：
int validateHelper(Node* node, int blackCount, int& rootBlackHeight) { // 递归检查黑高一致性，并返回本路径的黑节点数 }粗调思路：插入后用中序遍历确认有序性；删除后用验证函数检查黑高一致性。这两条过了，红黑树基本不会有大问题。
调试时还有一个非常实用的技巧：最小复现。当你发现删除后性质被破坏，不要在大树上调试，而是尝试找到一个key序列，插入后删除某个值能稳定复现问题，然后把序列缩到最短。红黑树出现 bug 的最常见原因不外乎三类：旋转时父指针没更新全、fixDelete的 Case 顺序写错（比如先判 Case 3 再判 Case 2）、以及对nullptr节点颜色的处理不对。记住这三类，排查时间能缩短一半以上。
7. 扩展思考：红黑树之外的选择
红黑树讲完，你可能想问：那 AVL 树呢？B 树呢？跳表呢？它们在工程里哪里用得上？这里我简单梳理一下，方便你在面试时展示全局视野，而不是只会背红黑树。
选择树形结构的核心就看两个指标：查询是内存中还是磁盘上，以及写入频率是高是低。
- 如果写入少、查询极频繁，AVL 树更合适。它的高度更矮，查找更快，但每次插入删除的旋转成本更高。典型场景是内存中的只读元数据索引。
- 如果数据规模巨大、存在磁盘上，B 树 / B+ 树才是主角。因为磁盘 IO 的代价远高于内存比较，B 树的“多路分支”让树高降到极低，一次磁盘读页能带走大量索引。MySQL InnoDB 的聚簇索引就是 B+ 树。
- 如果写多读少、并发环境，跳表也很好。Redis 的有序集合底层就是跳表，因为它实现简单、无锁化改造容易，查找效率平均也有 O(log n)。
红黑树的优势在于均衡：无论读写都稳定在 O(log n)，旋转次数平均比 AVL 少，实现又不像 B 树那样要考虑分页和分裂。这也是 C++ 标准库选它作为关联容器底层实现的原因。
如果你还想进一步挑战自己，可以考虑实现以下扩展：
- 支持迭代器，做成类似
std::map的接口。 - 用模版泛化 key 类型，支持任意可比较类型。
- 加入哨兵 NIL 节点，省去大量空指针判断，这是工业级实现的常见做法。
- 做随机插入删除压测，对比
std::map的性能，找出实现上的可优化点。
我在做第 3 项时最大的体会是：哨兵节点虽然代码更优雅，但写parent指针时很容易忘记把 NIL 的 parent 也维护好，反而引入隐蔽 bug。所以如果你第一次写，用nullptr+ 判空的方式更不容易出错。等完全想明白了，再改哨兵实现也不迟。
红黑树的本质不是那几组旋转动作，而是“用局部变换维护全局平衡”的思维模型。我把这个模型学会之后，再看 B 树的分裂合并、看跳表的多层级联更新，都觉得背后有相通之处。这也是我希望这篇文章能达到的效果——不是让你背代码，而是让你真正理解它为什么这样转、为什么这样染，从而在面试中对答如流，更在工程选型时心里有数。
