企业官网建设流程全解析

红黑树这名字听起来像某种园艺植物，但搞过底层开发的人都明白，它其实是计算机科学里量产最高的平衡树结构。日常开发中，HashMap在链表长度超过阈值后会把链表转成红黑树，TreeMap和TreeSet底层就是红黑树，Linux内核的CFS调度器、Nginx的定时器也有它的身影。面试时“红黑树的插入删除原理”更是被问烂了的高频题。这篇文章我结合自己的阅读和实现经验，把红黑树的定义、旋转、插入删除修复、以及和B+树的区别一次讲清楚，适合正在啃算法、写中间件、或者准备面试的同学。

很多人觉得红黑树难，是因为它规则多、分支多，看着像一棵树状的 if-else。但真正上手之后你会发现，它的核心就两个动作：旋转和变色，再加一条“黑色高度守恒”的约束。只要你理解了每个 case 在修什么，剩下的都是肌肉记忆。下面我从头拆一遍。

1. 先搞懂红黑树是什么：5条性质与设计初衷

1.1 五条性质怎么背才不会忘

红黑树是一棵满足额外着色规则的二叉搜索树，任何一颗红黑树都必须同时满足五条性质：

1. 节点非红即黑。
2. 根节点是黑色。
3. 所有叶子节点（NIL）是黑色。注意，这里的叶子不是带数据的节点，而是挂在每个真实节点下面的空节点。
4. 红色节点的两个子节点都是黑色，也就是说红色节点不能连续出现。
5. 从任意节点到它每个叶子节点的路径上，黑色节点的数量相同，工程上叫“黑高相等”。

这五条里，性质 5 是最核心的。它保证了任意一条路径不会明显长于其他路径。因为红色不能连续，所以最长路径也就是红黑交替的情况，不会超过最短路径的两倍。对比严格的平衡二叉树，这个平衡条件要宽松不少，但复杂度依然稳定在 O(logN)。

记忆上不需要死记。我自己的土办法是把它压缩成十六个字：非红即黑、根黑叶黑、红不相邻、黑高相等。后面写代码时反复对照这四句话，很多 bug 都能一眼看出来。实现里还会把所有的 NIL 节点统一成一个哨兵节点，颜色为黑色，这样在判断叔叔节点、兄弟节点颜色时很方便，少写一堆 null 判断。

1.2 为什么是红黑两色，和AVL比有什么优势

大多数教科书在讲完 AVL 树之后才上红黑树，所以很多人会下意识地问：已经有 AVL 了，为什么还要红黑树？答案是两者对“平衡”的定义不同，牺牲了一点严格性，换来更低的维护成本。

AVL 要求任何节点的左右子树高度差不超过 1，所以树的高度非常接近理论最小值，查找路径很矮。但为了维持这种严格平衡，插入和删除后可能需要回溯到根节点反复旋转，最坏情况下开销很大。红黑树只要求黑高一致，允许一定的红色节点堆积，因此插入删除时的旋转次数更少，整体吞吐量更稳定。

这也就是为什么 Java 的 TreeMap、TreeSet，C++ 的 std::map、std::set，以及 Linux 内核的很多结构都选了红黑树。如果你在做纯内存的有序数据结构，并且操作频率不低，红黑树的综合体验通常比 AVL 好。当然 AVL 也不是没有位置，当你的场景是“数据基本不变、只反复查询”，AVL 因为高度更低，缓存命中率可能更好看。

2. 左旋、右旋与变色：红黑树的基本动作

2.1 旋转的本质是保持中序遍历不变

红黑树的插入删除修复，说穿了就是在一小片区域里反复做旋转和变色。旋转本身是二叉搜索树通用的操作，不只在红黑树里出现。左旋的直观效果是：以某个节点 x 为轴，把它的右孩子 y 提上来，x 变成 y 的左孩子，y 原来的左子树变成 x 的右子树。右旋完全对称。

为什么要旋转？因为它可以在不破坏“左小右大”顺序的前提下，改变局部树的高度差。你可以把旋转想成用手拎住树根抖一抖，让几个节点换个位置，但中序遍历的顺序完全不变。这一点特别重要：旋转前是一个合法的 BST，旋转后仍然是一个合法的 BST，只是形态变了，为后面的变色创造条件。

红黑树修复里旋转经常发生在“爷爷、爸爸、儿子”三代之间。比如父节点和叔节点都收拢到一个方向后，一次旋转能把三层结构捋直，再配合变色把红色节点分散开。第一次接触时，我建议花半小时在白板上画一棵三层红黑树，用手工模拟一遍左旋和右旋，把所有指针变化写出来，比直接看代码记得牢。

2.2 旋转实操：用指针修改模拟

以经典 C++ 风格伪代码为例，左旋的核心操作是这样的：

void leftRotate(Node* x) { Node* y = x->right; x->right = y->left; if (y->left != NIL) 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; }

这段代码容易忽略的地方有三个。第一，x->right 换成 y->left 之后，一定要回填 y->left 的 parent 指针；第二，y->parent 要指向 x 的父节点，注意这里判断的是 x 在父节点的哪一侧；第三，最后把 x->parent 改成 y 时，顺手把 x 挂到 y->left。漏掉任何一个 parent 更新，后面的删除修复就会像多米诺骨牌一样连环出错。

我自己初学时是直接在纸上画一个四层小树，把节点从 a 到 f 标好，然后照着代码一步一步改颜色、改指针。右旋不用单独记，把 leftRotate 里所有 left 和 right 对调，再看一遍中序序列是否和旋转前一致，就能确认写对了。

3. 插入操作全解析：从叶子到根的染色修复

3.1 标准插入流程

红黑树的插入分两步走：先按普通 BST 的规则把节点挂到一个空位，然后把节点染成红色，再逐层向上修复颜色冲突。为什么不直接染黑？因为插入一个黑色节点会立刻让这条路径比其他路径多一个黑色，直接违反黑高相等的性质。染红则不会影响黑高，唯一要操心的就是可能出现“红色父节点 + 红色子节点”的连续红问题。

新插入的节点在真实代码里通常左右孩子都指向 NIL，而 NIL 是黑的。所以插入后的初始状态，要么整棵树完全合法，要么就有且只有一个违规点：新节点和它的父节点都是红色。这个违规情况非常集中，所以我们只需要盯着这一条红色链路往根方向修。

如果父节点是黑色，插入直接结束，什么都不用做。只有当父节点也是红色时，才需要进入修复循环。父节点为红，意味着祖父节点一定是黑（因为红节点不能连续），所以修复的目标其实是“在爷爷、爸爸、新节点”这三个节点之间做文章，顺带看叔叔节点是什么颜色。

3.2 三种需要修复的情况

假设当前节点是 x，它的父节点是 p，祖父节点是 g，叔叔节点是 u。因为 p 是红、g 是黑，所以按照 p 是 g 的左孩子还是右孩子，以及 x 是 p 的左孩子还是右孩子，可以组合出四种对称情况。这里以 p 是 g 的左孩子为例来说明，右侧对称处理即可。

Case 1：叔叔节点是红色

当 u 是红色时，最省事的办法是变色。把 p 和 u 都涂成黑色，把 g 涂成红色。这样一来，原本 p 和 u 两个红色孩子顶掉了 g 的黑色，g 变成红色后继续向上检查。从局部看，黑高没有任何变化：进入子树前是黑色 g，出去后是黑色 p 和 u，黑高一样。如果 g 的父节点也是红色，就把 g 作为新的当前节点继续循环。如果 g 是根节点，最后统一再把它涂黑。

这个 case 的实际效果是把红色“上移”了两层，而不是直接消除。所以它可能在最坏情况下一直传播到根。但因为每次循环都会把当前节点提升两层，复杂度依然是 O(logN)。

Case 2：叔叔节点是黑色，当前节点与父节点方向不一致

如果 u 是黑色，单纯变色解决不了问题，因为把 p 变黑会增加 p 这一侧的黑高，另一侧 u 子树的黑高就短了。这时要先看形态。比如 x 是 p 的右孩子，p 是 g 的左孩子，形成“左右”形状。我们的做法是：先对 p 做一次左旋，得到“左左”形状，然后把当前节点换成原来的 p。旋转本身不改颜色，只改形态。

这个 case 的目的很简单：把三代节点从“之字形”变成“一条直线”，好让下一步用一次旋转同时调整高度和颜色。你可以把它理解成 Case 3 的前置步骤，单独出现时并不结束修复。

Case 3：叔叔节点是黑色，当前节点与父节点方向一致

现在形态是“左左”，也就是 x 是 p 的左孩子，p 是 g 的左孩子。做法是对 g 做一次右旋，然后交换 p 和 g 的颜色：p 变黑，g 变红。旋转后 p 占据了 g 原来的位置，它的左子树是 x，右子树是 g，g 的左子树是原来的右兄弟子树。因为 p 变黑、g 变红，从这条路径看，红色不连续了，黑高也恢复了。

完成 Case 3 后整棵红黑树就是合法的，循环可以直接退出。所以插入修复最多做两次旋转：一次 Case 2 的预处理旋转 + 一次 Case 3 的主旋转。

伪代码逻辑如下：

while parent_of(x) is RED: g = parent_of(parent_of(x)) if parent_of(x) == g.left: u = g.right if u is RED: # Case 1 parent_of(x).color = BLACK u.color = BLACK g.color = RED x = g else: if x == parent_of(x).right: # Case 2 x = parent_of(x) left_rotate(x) # Case 3 parent_of(x).color = BLACK g.color = RED right_rotate(g) else: # 对称处理 root.color = BLACK

3.3 插入修复的规律总结

插入过程中颜色冲突只可能发生在“红父红子”之间，修复方向从下往上。Case 1 不断把祖父变成红色向上传递，Case 2 和 Case 3 在遇到黑色叔叔时通过旋转一次搞定。整个过程旋转次数有上限，而这正是红黑树工程价值的重要来源。

如果你去读 JDK 里 TreeMap 的 fixAfterInsertion，会发现它实际只有 while 循环和几个 if 分支，代码并不长。难的不是读懂每一行，而是理解为什么每个 case 都恰好把违规点消掉，又不会引入新的黑高不一致。我的经验是：把每个 case 的局部黑高逐层算一遍，确认修复前后从祖父出去的每条路径黑高一样，这样就踏实了。

4. 删除操作全解析：双黑节点的处理艺术

4.1 删除流程与双黑的由来

删除比插入难，难在删除一个黑色节点会直接破坏黑高相等。如果删的是红色节点，那就没什么好修复的，红色节点本来就不贡献黑高，直接用它的非空孩子顶上来，或者让 NIL 顶上来就行。麻烦的是删黑色节点。

常见的删除做法是走 BST 删除流程：先找到目标节点，如果它有两个孩子，就用中序后继节点的值覆盖它，然后改成删除那个后继节点。这样处理之后，真正被删除的节点最多只有一个非空孩子。这个技巧能把删除问题简化，不需要写各种复杂的孩子组合。

如果被删节点是黑色，且它的非空孩子是红色，那也很简单：让孩子顶替位置，然后把这个孩子染黑。这样虽然少了一个黑色节点，但孩子变黑补上了，黑高不变。真正麻烦的是被删节点是黑色，同时它的孩子也是黑色，或者孩子是 NIL。这时顶替上来的节点本身也是黑色，路径上等于少了两个黑色，我们就说这个顶替节点带上了“双黑”，需要向兄弟方向借一个黑色。

4.2 删除修复的四种情况

删除修复的四种 case 是红黑树里最容易让人绕晕的部分。以下假设 x 是双黑节点，p 是 x 的父节点，w 是 x 的兄弟节点，且 x 是 p 的左孩子，右侧对称处理。

Case 1：兄弟节点 w 是红色

w 为红，那么 p 必为黑，w 的两个孩子都是黑。此时对 p 做左旋，然后把 w 变黑、p 变红。旋转后，x 的新兄弟变成本来 w 的左孩子，而 w 的左孩子是黑的。于是问题从“兄弟为红”化成“兄弟为黑”的情况，继续用下面几个 case 处理。这一步其实是把危险的红色兄弟移走，让黑兄弟站到桌面上来。

Case 2：兄弟节点 w 是黑色，且 w 的两个孩子都是黑色

这种情况下，w 自身是黑，两个侄子也是黑，x 又带着双黑。我们把 w 直接变红，然后把 x 的双黑身份上移给 p。为什么可以这样？因为 w 变红后，原来通过 w 的这条路径黑高减了 1，恰好和 x 这边多出来的黑高抵消，局部就恢复平衡了。但整体上 p 这个子树比原来少了一个黑，所以如果 p 是红色，直接把 p 变黑即可结束；如果 p 是黑色，p 就变成新的双黑节点，继续向上循环。

Case 3：兄弟节点 w 是黑色，w 的左孩子是红色，右孩子是黑色

这个形态下，w 自己是黑，但它的左红右黑，还不能直接用 Case 4。我们先把 w 右旋，把 w 的左孩子顶到 w 的位置，w 自己变成红色，原来的左孩子变成黑色。旋转后 x 的新兄弟变成原来 w 的左孩子，这个新兄弟是黑，而且它的右孩子是原来的 w，w 是红色。于是形态变成了“兄弟黑 + 右侄子红”，正好进入 Case 4。

Case 4：兄弟节点 w 是黑色，且 w 的右孩子是红色

这是收尾的 case。以 p 为轴左旋，让 w 顶替 p 的位置，然后 w 的颜色改成 p 原来的颜色，p 变黑，w 的右孩子变黑。做完后，x 的额外黑色被消除，整棵树恢复平衡，循环可以退出。这里的一个关键点是 w 继承 p 的颜色，而不是固定变黑，这样才能保证旋转后不会破坏上层对颜色的要求。

工程上的删除修复代码通常长这样：

while (x != root && x.color == BLACK) { if (x == x.parent.left) { Node* w = x.parent.right; if (w.color == RED) { // Case 1 w.color = BLACK; x.parent.color = RED; leftRotate(x.parent); w = x.parent.right; } if (w.left.color == BLACK && w.right.color == BLACK) { // Case 2 w.color = RED; x = x.parent; } else { if (w.right.color == BLACK) { // Case 3 w.left.color = BLACK; w.color = RED; rightRotate(w); w = x.parent.right; } // Case 4 w.color = x.parent.color; x.parent.color = BLACK; w.right.color = BLACK; leftRotate(x.parent); x = root; } } else { // 对称处理 } } x.color = BLACK;

4.3 为什么删除修复比插入难

插入的修复一眼能看出在修“红红冲突”，目标单一；删除的修复是在“黑色缺失”的前提下做平衡，属于一个隐性约束被破坏，而且 Case 2 会把问题持续向上抛，像递归的债一样越滚越远。初学者最大的误区是忘了删除完成后根节点可能变成红色，或者忘了 Case 4 中兄弟节点需要继承父节点颜色。

我建议第一次学删除时不要直接写代码，先找几个在线红黑树演示网站，手动构造一棵树，依次删除黑色叶子节点，观察每个 case 的旋转和变色。等你把 Case 1 如何转化为 Case 2/3/4、Case 2 如何上推看清楚了，再去看 TreeMap 的 fixAfterDeletion 源码，会发现逻辑其实非常连贯。

5. B+树是红黑树吗？别把它们混为一谈

5.1 B+树的结构与红黑树的关键差异

先说结论：B+树不是红黑树。很多人在聊数据库索引时会不禁问一句“B+树是红黑树吗”，因为它们名字里都带“树”，但二者根本不是一个物种。红黑树是二叉平衡搜索树，每个节点最多一个 key、两个孩子；B+树是多路搜索树，每个节点可以放很多个 key，并且有大量孩子指针。

B+树最鲜明的特点是：内部节点只放索引 key，不存实际数据；数据全部集中在叶子节点层，并且叶子节点之间用链表串起来。这样一来，数据库做范围查询时，只要找到起始叶子，然后顺着链表一路往后读就好，非常高效。而红黑树本身不具备叶子链表，范围查询必须靠中序遍历，从根开始一步一步走。

为什么数据库用 B+树而不用红黑树？核心原因是存储介质不一样。数据库索引存在磁盘上，磁盘 IO 按页读写，一次 IO 的成本远高于内存访问。B+树可以把一个节点设计成一个页的大小，一次磁盘 IO 就扫描一堆 key；红黑树一个节点只有两个分支，树高会明显更高，查询一次可能要读十几个页，IO 次数受不了。而红黑树适合纯内存场景，因为内存访问不存在按页对齐的成本，指针跳来跳去无所谓。

5.2 不同场景下的选型建议

选择哪种树，本质是选择“存储介质 + 操作模式”下的最优解。

如果你的应用在内存里管理一批有序数据，写多读也多，红黑树是稳妥选择。如果你在写数据库或文件系统，想用红黑树替代 B+树，那抗住并发 IO 的成本会很高。还有一点，B+树和红黑树不是替代关系，而是各自在自己的地盘上发光发热。理解了这套取舍，你在系统设计时就能少走弯路。

6. 常见问题与调试心得

6.1 实现红黑树容易踩的坑

我把自己实现红黑树时踩过以及看别人踩过的坑总结一下，基本都是指针细节和 case 顺序问题：

• parent 指针更新不完整。旋转后漏掉某个节点的 parent，后续删除修复会死循环或者丢节点。建议每次旋转后都画图核对所有受影响的父指针。
• NIL 不统一。把空节点写成 null，代码里到处都需要判断是否为 null，很容易在处理叔叔节点时出错。用一个静态哨兵 NIL 节点统一表示空叶子，能让代码简洁很多。
• 插入时先做 Case 3 再做 Case 2。应该先判断叔叔为红，再处理之字形，再处理直线形。顺序反了之后，Case 2 旋转完可能找不到正确的叔叔节点。
• 删除循环的条件写错。常见的是 while (x != root && x.color == BLACK)，但 x 可能为 NIL，NIL 的 parent 字段必须正确指向真实节点，否则循环里访问 x.parent 就是空指针。
• 根节点忘记染黑。插入和删除的修复过程中根节点可能变红，循环结束后必须显式执行 root.color = BLACK，否则性质 2 不满足。
• 调试时只打印数值不打印颜色。红黑树的高度信息藏在颜色里，建议打印出类似“key: 42 color: R parent: 36”这样的文本，或者直接画树形结构带颜色。

6.2 如何验证自己的红黑树实现

红黑树代码容易出一两种隐蔽的逻辑错误，但靠肉眼很难看出来。我推荐准备三个测试层次：

第一层是结构校验。写一个 check() 方法，返回布尔值，校验五条性质。中序遍历是否从小到大、根是否黑、是否存在连续红节点、每条路径黑高是否一致。这个校验每次插入删除后都跑一遍，最慢也来得及。

第二层是对照测试。如果你在 Java 环境，直接用 TreeMap 做黑盒对拍：随机插入一批 key 到红黑树和自己的 TreeMap，再随机删除，每次操作后比较中序序列是否一致。任何不一致都意味着树结构不是合法 BST。这个测试能快速暴露指针断裂问题。

第三层是压力测试。连续插入几十万个随机数，然后随机删除，最后再全部删除，全程开着结构校验。如果这几个循环能跑下来，你的实现基本就稳了。我自己试过，在第三层最容易暴露的是删除 Case 2 向上传播时 NIL 的 parent 指向不对，以及旋转后兄弟节点引用没刷新。

6.3 面试官真正想问的是什么

面试时被追问红黑树不用慌，对方通常不是真想让你几十分钟内手写一棵能跑的红黑树，而是考察你有没有真正理解平衡树的取舍。常见的追问包括：为什么选中红黑树而不是 AVL？插入时三种 case 分别处理什么？删除时的双黑是什么意思？HashMap 为什么在链表过长时转红黑树？

如果你能画出插入的三种情况，说明删除的双黑思想，再结合 HashMap 和 TreeMap 的工程背景展开，面试官就基本满意了。我最建议大家准备一张 A4 纸，把五条性质、左旋右旋、插入 case、删除 case 都画一遍，比背二十行代码有效得多。画图的过程会把很多“我以为会了但其实不会”的细节暴露出来。

我自己在实现红黑树之后，最大的体会是：红黑树不适合靠记忆硬写，它更适合用白板先把每个 case 的指针变化画清，再落到代码里。强烈建议你亲手把插入和删除的六七个 case 画一遍，哪怕不写代码，理解也会上一个大台阶。后续如果要做内存索引、定时器或者有序数据结构，红黑树都仍然是那个值得信赖的默认选择。