红黑树详解：性质、旋转、插入删除与工程实践

红黑树，咕咕咕！—— 聊聊这颗让无数人“学废了”的平衡树

我猜你点进这篇文章，多半是因为看到了“咕咕咕”这三个字。这词儿在咱们程序员圈子里太亲切了——说好的周末看红黑树，结果刷了一下午短视频；说好的下周一投简历，结果拖到下下周一。而“红黑树”这颗数据结构里的硬骨头，更是不知道让多少人立了flag然后又“咕咕咕”了过去。

说起来很应景，红黑树本身就像那个一直放你鸽子的朋友：你翻开《算法导论》准备啃它，它用一堆黑节点红节点、左旋右旋把你绕晕；你刷题刷到“手撕红黑树”，它又用插入删除的一堆Case让你怀疑自己到底有没有学过二叉树。但另一方面，它又是我们每天都在用、却完全感知不到的东西——Java的TreeMap、C++的std::map、Linux内核的调度器、Nginx的定时器，底层都是红黑树在默默干活。

这篇文章专门写给那些“想学红黑树但一直咕咕咕”的朋友。我会用偏工程实践的视角，把红黑树的来历、五个性质、旋转操作、插入删除的全部分支场景，以及我在实际手写过程中踩过的坑，掰开揉碎讲清楚。讲完理论之后，还会给出可复现的实现思路和测试方法。目标很朴素：让你看完之后，能亲手写出一颗能跑的红黑树，而不是只在背面试题。

1. 为什么“红黑树”这名字这么劝退

1.1 它到底在解决什么问题

先聊点轻松的。其实红黑树不是凭空冒出来的怪东西，它本质上是“平衡二叉搜索树”这个大家族里的一名成员。它的老祖宗是二叉搜索树（BST）：左子树比根小、右子树比根大，查找的时候从根一路往下走，理论上每次能排除掉一半的节点。

但BST有个致命弱点：如果数据是按顺序插入的，比如1、2、3、4、5……它就会长成一棵“瘸腿树”，深度从log n退化到n，查找效率从O(log n)退化到O(n)。换句话说，本来一分钟能查完的东西，数据量一大就要一小时。

为了解决BST退化的问题，人们发明了“自平衡二叉搜索树”。这里有两个著名选手：一个是AVL树，它严格要求任意节点的左右子树高度差不超过1；另一个就是红黑树，它用“颜色”这种状态来约束树的形态，保证从根到叶子节点的最长路径不超过最短路径的2倍。

为什么不用AVL？因为AVL查得快，但插入删除时为了维持那严格的“高度差不超过1”，经常需要做很多次旋转，写起来也啰嗦。红黑树则更“佛系”：它不要求左右子树绝对等高，只要求全局路径长度有个2倍的宽松上限。这带来一个直接好处——插入删除时的调整次数更少，实际操作中红黑树的综合性能往往比AVL树更稳定，尤其在写多读少的场景下优势更明显。

1.2 “咕咕咕”背后其实是三大难点

我观察了一下，大家学红黑树“咕咕咕”的理由，翻来覆去就是这三个：

第一个难点是“红黑树的五个性质背了又忘”。什么“根是黑的”“红节点不能有红孩子”“每条路径黑节点数相同”……背的时候觉得不难，一到用的时候就乱了。

第二个难点是“旋转操作看着明白，一动手就蒙”。左旋右旋其实是对称的，但很多教程一上来就丢给你一大段伪代码，没有讲清楚“旋转到底在干嘛”。

第三个难点是“插入和删除的分支情况太多”。光插入就有双红冲突、叔父节点颜色不同等好几种Case，删除更是有“双重黑”这种劝退概念。不把原理吃透，光靠背Case，转头就忘。

这篇文章最大的价值，就是帮你把这三大难点一个个拆掉。我会用一些比较接地气的比喻和场景来解释原理，让你从“背结论”变成“理解推导过程”，这样你就不会再咕咕咕了。

2. 五个性质：不是背口诀，是看门道

2.1 逐个拆解性质的真正含义

红黑树的官方定义就是五个性质，我先把原文列出来：

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

很多人到这一步就脑壳疼了：这五条到底图个啥？

我给你翻译成人话。性质1和性质3是基础设定，不用管。性质2规定根必须黑，是为了让树的顶部有一个“稳定的锚点”，避免根和它的孩子出现连续红节点。然后最关键的就是性质4和性质5。

性质4叫“红色约束”，它强制红节点的孩子必须是黑的，所以连续两个红的绝不允许出现，这意味着一条路径上红节点不能“扎堆”。性质5叫“黑色高度”约束，它要求所有路径上经过的黑节点数量完全一样。这两条搭配起来的数学结果就是：一条路径上最多只能有一半的节点是红的，其余都是黑的，所以最短路径是全黑路径，最长路径是“黑红黑红”交替路径，最长就是最短的2倍。

这就是为什么红黑树不像AVL那样严格要求左右子树高度差不超过1，但依然能保证全局的O(log n)深度。它就像一个没那么自律但足够稳定的员工：不要求每天精确工作8小时，但保证一周工作不超过某个上限，所以整体效率和可靠性都有兜底。

2.2 别死记硬背：用实际例子感受性质

我给你举个具体例子。假设树上有条路径经过了3个黑色节点，那么红色节点最多能穿插几个？根据性质4，红节点不能连续，所以最长的情况就是“黑、红、黑、红、黑”，红色最多2个。你看，这个推导一点都不难。

同理，如果某条路径有5个黑节点，最长的“黑红交替”路径也就是9个节点左右，最短的全黑路径就是5个节点。所以任意路径的长度都控制在2倍以内。这就是红黑树名字里“黑”的底气——真正决定树高度的是黑色节点的分布，红色节点只是“装饰品”和“调节阀”。

我在带新人时特别喜欢让他们先别看代码，先拿笔在纸上画一颗合法的红黑树，画个七八颗，把五条性质套上去检查，画多了你自然就有感觉了。这个热身过程比直接上代码重要得多。

3. 左旋右旋到底在旋转什么

3.1 一次搞懂旋转的本质

旋转这个概念，很多教程写得像天书，其实你把它想成“换爹”就行了。

二叉搜索树有一个铁律：左子树所有节点小于根，右子树所有节点大于根，中序遍历结果是有序的。旋转操作的意义在于——在不破坏这个铁律的前提下，调整局部父子关系，从而改变子树高度。

我们以“左旋”举例。假设节点x有一个右孩子y，左旋就是把y提升到x原来的位置，把x降成y的左孩子。那y原来的左孩子b怎么办？它的值比y小、比x大（因为b在y的左子树里，而x是y的左子树中某个路径上的祖先），所以它被“过继”给x当右孩子。旋转完成后，整棵子树的中序遍历顺序完全不变，但高度分布变样了。

反过来，“右旋”是完全对称的操作：把x的左孩子y提升上来，x变成y的右孩子，y原来的右孩子过继给x当左孩子。

我用一个生活化类比来帮你记住：左旋就像把压在最底下的那个大个子“扶正”到领导岗位，原来在他上面的领导降级成他的副手，副手原来的重要下属也重新划归领导管理。人员级别变了，但公司里的汇报关系依然清晰，职级顺序没有乱。

3.2 旋转的代码实现与常见错误

旋转的代码并不长，我贴一段方便你参考的伪代码：

function rotateLeft(tree, x) { const y = x.right; // 锁定要提上来的节点 x.right = y.left; // y的左孩子过继给x当右孩子 if (y.left !== null) { y.left.parent = x; } y.parent = x.parent; // y接管x的上级关系 if (x.parent === null) { tree.root = y; // x是根的话，y成为新根 } else if (x === x.parent.left) { x.parent.left = y; } else { x.parent.right = y; } y.left = x; // x变成y的左孩子 x.parent = y; }

这段代码里有几个特别容易翻车的地方。第一，处理那个“过继”节点时，一定要记得更新它的parent指针，很多初学者漏掉这一步，结果遍历时直接死循环。第二，判断x是父节点的左孩子还是右孩子时，必须先判断“x是不是根”，否则会空指针异常。第三，旋转操作本身不改变节点颜色，颜色调整是旋转之后另外做的事。

我早期手写红黑树时，在旋转上花的时间比在插入Case上花的还多，就是因为每次写完之后，树的形状看着不对，一调试才发现某个节点的parent没指对。所以强烈建议你写完旋转函数后，别急着写插入，先单独测试旋转：构建一棵随机二叉搜索树，任意选几个节点做旋转，然后中序遍历对比旋转前后的结果，序列只要发生变化就是Bug。

4. 插入操作：从裸BST到红黑树的“染色仪式”

4.1 为什么新插入的节点默认是红色

这个细节很多教程一笔带过，但它特别关键。我们为什么不把新节点染成黑色？因为性质5要求每条路径的黑色节点数相同，如果新节点直接是黑色，那它所在的那条路径就比其他路径多了一个黑节点，相当于“全局违约”，调整成本会很大。

但如果你把新节点染成红色，情况就简单多了：黑色路径数量不变，性质5天然满足，唯一的风险是性质4——万一新节点的父节点也是红色，就出现了“双红冲突”。所以插入操作的核心工作就一句话：新节点先默认红，然后有冲突就修复，没冲突就完事。

这个策略的本质是“把问题尽量局部化”：新节点是红的时候，它只可能破坏自己和父节点之间的颜色约束，不会一下子牵动整棵树的黑高平衡。调整起来最多只需要往上追几层，所以效率高。

4.2 插入后的三大类修复场景

我们先约定一下符号：新插入的节点叫X，它的父节点叫P，祖父节点叫G，叔父节点（P的兄弟）叫U。在实际代码里，通常还要特别判断P是G的左孩子还是右孩子，因为两个方向的修复是对称的。为了方便，这里以P是G的左孩子为例来讲，右孩子的情况你做镜像处理即可。

第一类：父节点P是黑色。这太完美了，新节点是红的，两个红不能连续的条件没有被打破，黑色数量也没变化，什么都不用做，直接结束。

第二类：父节点P是红色，叔父节点U也是红色。这是我们遇到的第一个大Case。此时祖父节点G必然是黑色（因为P是红的，它的父节点不能也是红的）。我们把G的黑色“下放”给P和U，让P和U变成黑色，G变成红色。这样就消解了“X和P连续双红”的问题，保持了黑色高度不变。但G变成红色后，G和它的父节点说不定又撞车了，所以把G当作“新插入的节点”，继续往上循环处理。

第三类：父节点P是红色，叔父节点U是黑色（或者为空NIL）。这时候不能像第二类那样耍赖染色了，因为如果硬把G的黑色下放，黑高就被破坏了。此时必须动用旋转大法。具体还能细分两个子场景：如果X是P的左孩子，执行一次右旋，把P提上去，再把P染黑、G染红；如果X是P的右孩子，先以P为支点左旋，把X转到左边来，然后按上面同样的方式处理。核心就是通过旋转加染色，把那个“红-红冲突”的节点转到父辈位置并改色，彻底消解冲突。

4.3 图解插入过程的完整走读

我建议你拿这四个节点练手：依次插入值[10, 20, 30, 15]，我们一步步看会发生什么。

插入10：根为空，直接创建节点，按性质2染黑。这颗树只有一个黑节点，合法。

插入20：新节点20是红的，父节点10是黑，无冲突，结束。树变成10（黑）-> 20（红）。

插入30：30的父节点20是红色，叔父节点是10的左孩子NIL（算黑色），触发第三类。因为30是20的右孩子，而20是10的右孩子，形成“右右”链，执行一次左旋：20提升为根，10变成20的左孩子，20染黑，10染红。此时树形是20（黑）作为根，左孩子10（红），右孩子30（红）。所有性质都满足。

插入15：15的父节点是20（黑）？不对，15比20小，它应该先找左孩子10，10是红，10比15小，所以往右走，15成为10的右孩子。15是红，但父节点10也是红，冲突了。再看叔父节点：10的兄弟是30，颜色是红，属于第二类。处理方式是把祖父20的黑色下放：10和30变黑，20变红。但20是根，根必须黑，所以再把20染黑。最终树是：20（黑）、10（黑）、15（红）、30（黑），完全合法。

你看，整个过程其实就是“能染色解决就染色，染色解决不了就旋转，旋转完再染色”。理解了这点，红黑树的插入就没有背Case的负担了。

5. 删除操作：最难啃的“双重黑”是什么鬼

5.1 删除操作为什么比插入麻烦

插入的麻烦在于“新增一个节点”，它只影响局部颜色，调整起来相对顺手。删除不一样，删掉一个节点如果恰好是黑的，那这条路径上的黑节点数量就少了一个，直接破坏了性质5。这就是“黑高失衡”，比“双红冲突”更棘手。

正常删BST节点的逻辑大家都懂：叶子直接删，只有一个孩子就让孩子顶上来，有两个孩子就找后继节点替换值然后删掉后继节点。红黑树也沿用这套逻辑，但是删完之后要根据被删节点的颜色决定要不要修复。如果删的是红节点，什么影响都没有，直接结束。如果删的是黑节点，那就要开始“高难度操作”了。

为了描述方便，我们把“顶替被删节点位置”的那个节点称为M，M的父节点称为P，M的兄弟节点称为S，S的左孩子为SL，S的右孩子为SR。由于删了一个黑节点，以M为中心的那条路径少了一个黑，相当于M“欠了一笔黑账”。我们要么还上这笔账，要么通过旋转和染色把这笔账分摊出去。

5.2 借“双重黑”概念理解修复逻辑

很多教材会引入一个叫“双重黑”的概念：把M这个节点视为带了两层黑色，它在试图填补缺失的黑节点数量。修复的目标就是遍历整个树，直到遇到某个节点变成红色为止，或者把多余的那层黑推给根节点。

这个思路很划算，因为引入双重黑之后，删除修复的众多Case就能用“向兄弟节点借黑”、“把红节点染黑”等少数手段统一处理了。我来梳理一下主场景，还是假设M是P的左孩子，右侧场景对称。

场景一：兄弟节点S是红色。此时P必为黑色，我们把S旋转上来：以P为支点左旋，然后S变黑，P变红。这个操作本身没有直接解决黑高问题，但它的目的是把“红色兄弟”变成“黑色兄弟”的情形，好让我们能用后续的标准手段处理。

场景二：兄弟节点S是黑色，S的两个孩子也都是黑色（或NIL）。这时候S这边也没法借黑了，只能把S染红。这样S这条路径的黑高和M这边一起减一，两家一起变矮，大家重新平衡。但P本身的黑高减了一，相当于P欠账了，所以把P当作新的“问题节点”，继续往根方向处理。

场景三：兄弟节点S是黑色，S的左孩子SL是红色，S的右孩子SR是黑色（或者兄弟右孩子这种情况）。这个形态是“内侧红”的情况，需要先做一次小旋转把它转成“外侧红”，目的还是归一化到下一个场景。

场景四：兄弟节点S是黑色，S的右孩子SR是红色（外侧红）。这是最理想的情况：以P为支点左旋，把S提上来，然后让S继承P原来的颜色，P改成黑色，SR改成黑色。这样M这边多了一个黑节点，账就还上了，而且整棵树的性质全部恢复，循环结束。

初看这四个场景确实让人头大，但你抓住主线就会觉得有迹可循：“红色兄弟要先进化，没孩子可借就同归于尽降高度，内侧兄弟要先转正，外侧兄弟直接借黑”。这四句话基本可以把删除的Case给串起来。

5.3 删除修复的实际走读

我们用前面那颗树来实验：根20（黑），左10（黑），左的右孩子15（红），右30（黑）。现在尝试删除节点30。30是黑色叶子，删掉之后，它父亲20的右子树NIL就少了一个黑节点，出现失衡。

删除后，双黑节点M是NIL，M是P=20的右孩子，NIL兄弟S是10（黑）。S=10的两个孩子中，15是红，SL=15是红，而左孩子是NIL。这种情况对应右侧镜像的“内侧红”场景三，但又有点特殊。实际处理是先看右侧镜像：S=10，S的左孩子NIL，S的右孩子15是红，这其实是“兄弟节点的内侧孩子是黑、外侧孩子是红”，对应场景四（因为对于右侧场景，外侧是左孩子……这里容易搞混）。

不管你是用哪个Case，最终的标准解法是：以20为支点右旋，10提为根，20变成10的右孩子，15变成20的左孩子，10继承20原来的黑色，20染黑，15保持红。删除后整棵树变成：根10（黑），左NIL，右20（黑），20的左孩子15（红），完全合法。

有没有觉得，其实没必要死记每一个Case属于第几类，但是你必须理解每个Case的旋转和染色是怎么配合的，以及为什么要这么配合。理解了“借黑”和“降高”两个核心动作，删除操作的逻辑你就能独立推导了。

6. 手写红黑树的关键工程细节

6.1 用NIL节点代替null是个好习惯

很多新手写红黑树时直接拿null表示空节点，写到删除的Case判断时就会疯狂空指针报错。我强烈建议你专门定义一个NIL节点对象，它是黑色的，左右孩子parent都为null。这样所有“空位置”都是一个实实在在的对象，你可以直接访问NIL.parent、NIL.color等属性，判断逻辑会简单很多。

定义一个NIL节点还有一个额外好处：叶子节点黑色这个性质4、5的判断可以统一处理，不用每个地方都写“if node === null”。这在删除操作的双重黑循环里尤其省事。

我的习惯是在构造函数里初始化：

class RBTree { constructor() { this.NIL = new Node(null); this.NIL.color = 'BLACK'; this.NIL.left = null; this.NIL.right = null; this.NIL.parent = null; this.root = this.NIL; } }

然后所有的新节点创建，左右孩子都指向this.NIL。这样后续的代码里就不用判断“节点是否存在”了，只需要判断“节点是否是NIL”。

6.2 调试红黑树不能只靠肉眼看

手写红黑树的过程中，你一定会遇到树看起来合法但实际违法的诡异情况。怎么破？靠肉眼一行行看肯定不靠谱，我建议你写三个辅助函数来支撑验证。

第一个是中序遍历，判断输出是否有序。红黑树首先得是二叉搜索树，如果中序遍历结果不是递增的，说明树的搜索结构已经被旋转搞坏了。第二个是计算黑高，递归统计每条路径的黑节点数，看看是否每条路径都一样。第三个是检查红色冲突，递归遍历所有节点，遇到红节点就检查它的父节点是否为红。

我在写完插入后就是这么测试的：随机插入几千个数，每插入一个就调用验证函数跑一遍。刚开始跑两下就报错，后来我把报错的节点和它的key打印出来，就能快速定位是哪条Case没处理对。别嫌验证函数跑得慢，黑盒验证能帮你省下至少两倍的调试时间。

6.3 性能测试不能只看能跑通

手写红黑树还有一个容易被忽略的环节：性能验证。很多人的树能跑通测试，但插入几万个数据就明显卡顿。这时候你要看一下是不是递归深度过大，或者旋转次数异常。

我自己的做法是：生成一个从1到100万的有序序列，依次插入红黑树，观察树的高度变化。红黑树理论高度大约在2log2(n)以内，对100万数据来说应该在40左右。如果你插入完发现高度涨到100多了，那大概率是删除或插入Case判断有误，导致某些路径没有被正确平衡。

另一个性能指标是“旋转次数”。红黑树插入平均旋转次数是常数级别的，删除也类似。如果你感觉旋转特别频繁，可以加个计数器打出来看看，数量级异常就说明代码逻辑有偏差。

7. 红黑树在真实世界的应用图谱

7.1 语言库与框架层面的红黑树

你可能已经在很多地方“无意识”地用着红黑树了。Java的TreeMap和TreeSet，底层就是红黑树；C++ STL里的std::map、std::set、std::multimap、std::multiset，底层也是红黑树。也就是说，你在C++里随便声明一个std::map<string, int>存配置，往里面插入删除数据，背后都是红黑树在维护有序性。

这些库之所以选红黑树而不是AVL树，除了平衡性能好，还有一个重要原因：它对“树旋转”的次数容忍度高，而AVL树在删除时可能要一路旋转到根。红黑树删除旋转次数相对较少，日常开发里删除操作又没有想象中那么稀有，所以综合下来红黑树更合适。

除了通用库，Linux内核的完全公平调度器（CFS）也用了红黑树来管理进程的虚拟运行时间，Nginx用红黑树管理定时器事件，nginx的频率限制模块也会用到红黑树来追踪客户端访问频率。包括Redis的有序集合，在数据量较大时也用了跳表（和红黑树性能近似但实现更简单）。可以看到，凡是需要“持续插入删除、还要保持有序查找”的场景，红黑树几乎都是首选。

7.2 红黑树与跳表、B树的横向对比

面试经常问“为什么不用红黑树？为什么用跳表？”这里我给大家梳理一个简单对比。

跳表的核心优势是“实现简单、支持高效的区间扫描和O(1)的“前驱后继”访问”。所以Redis的有序集合用跳表，因为它想要快速的区间查询和排名操作。红黑树的中序后继查找虽然也是O(log n)，但实现起来指针操作多、容易出错。

B树和B+树则主要用于磁盘或SSD这类块存储场景，因为它们的节点可以保存多个键值，一次IO就能读出大量数据，减少磁盘访问次数。而红黑树是内存数据结构，一个节点只存一个键值，直接用在磁盘上会导致频繁的IO。可以看出，数据结构选型从来不是“谁最好”，而是“谁最匹配当前硬件和操作模式”。

7.3 手写红黑树对工程能力的真实提升

我知道很多人觉得“手写红黑树在工作中根本用不到”，这话有一定道理，但我不建议你因此跳过它。因为我带过的很多开发者在手写完红黑树后，对指针操作、边界条件、递归思维和调试能力的提升是立竿见影的。

尤其是调试红黑树时，你会在一个很复杂的系统里同时追踪多个状态（颜色、指针、高度、顺序），这比平时写业务代码更能锻炼你“系统式思考”的能力。就算你以后永远不写数据结构库，你会发现自己在处理链表、处理树形数据、处理带状态的递归逻辑时，心里会踏实很多。

8. 一个可运行的最小红黑树实现框架

8.1 代码结构总览

考虑到文章篇幅，我不贴完整的生产级实现，但是我会给你一个极简但可运行的框架，你可以顺着这个框架自己补全。

项目的类结构大概分三块：Node节点、RBTree主类、以及内部实现插入删除修复的私有方法。我这里用JavaScript展示，因为它的指针操作相对直观，你换到C++或Java也只是语法差异。

class Node { constructor(key, color = 'RED') { this.key = key; this.color = color; this.left = null; this.right = null; this.parent = null; } } class RBTree { constructor() { this.NIL = new Node(null, 'BLACK'); this.NIL.left = this.NIL.right = this.NIL.parent = null; this.root = this.NIL; } insert(key) { // 1. 普通BST插入 // 2. 新节点默认红色 // 3. 调用insertFixup } insertFixup(node) { // 循环处理双红冲突 } delete(key) { // 1. 找到节点 // 2. 执行BST删除逻辑 // 3. 记录被删节点颜色 // 4. 若为黑色，调用deleteFixup } deleteFixup(node) { // 处理双重黑问题 } rotateLeft(x) { ... } rotateRight(x) { ... } }

8.2 快速验证的小脚本

补全实现之后，你可以用下面这个小脚本做快速验证：

const tree = new RBTree(); for (let i = 1; i <= 10000; i++) { tree.insert(Math.floor(Math.random() * 100000)); } console.log('树高:', height(tree.root)); console.log('节点数:', countNodes(tree.root)); console.log('中序有序:', isSorted(traverseInOrder(tree.root)));

随机插入一万个数，如果树高控制在30以内、中序有序、没有红色冲突，那这颗红黑树基本就是正确的。然后再补一个删除测试：随机删除一半节点，每删完一个就验证全树性质。能跑完这个脚本，你的红黑树就可以拿出去用了。

8.3 从单测到量产：还要补齐什么

如果你想把这颗红黑树用在自己的项目里而不是练习，那还得补三块内容。第一是前驱后继查询，即找某key的上一个和下一个节点，这在有序集合场景很常用。第二是查找区间，比如返回所有在[a,b]之间的节点。第三是迭代器，支持中序遍历不重不漏地访问所有节点。

这三块其实是红黑树的“配套设施”，很多人手写红黑树只写了插入删除，结果一用就发现取前驱后继自己还得现写。面试时如果被问到“红黑树你有什么能落地的亮点吗”，你把这几个功能说出来，配合前面实现的扎实验证，就能体现出“我不仅是背了代码，而是做了一套完整的数据结构”。

9. 常见误区、坑点与速查表

9.1 我见过的翻车现场

我面试过不少候选人，也在论坛里看到过很多手写红黑树的帖子，翻车现场总是那几个。

第一个翻车现场是把“节点颜色”和“插入路径”混为一谈。有人插入节点后，看父节点是黑就直接返回，完全忘了还要检查祖父节点是否需要旋转。这样插入个别数据可能没问题，但只要连续插入有序数据，树就会越变越高。

第二个翻车现场是删除操作时没有保存被删节点的原始颜色。在BST删除里，如果你选的是后继节点替换，那真正物理删掉的其实是后继节点，要用这个后继节点的颜色来决定是否修复。代码写成“return替换节点的颜色”就是致命的BUG。

第三个翻车现场是旋转后没有更新“过继”节点的parent。这个我在前面强调过，但每次实际写的时候还是容易漏。我的建议是旋转函数里凡是见到“某.left = 某”的赋值，后面必须紧跟一行对应的parent赋值。

9.2 红黑树面试常见问题速查

我整理了一份面试准备速查表，你可以照着自查。

9.3 给正在“咕咕咕”的你三点实操建议

如果你看完文章仍然觉得心里没底，我给你三个立刻能落地的实操建议。

第一步，别急着写代码。先在纸上画一颗红黑树，用五个性质检查它。然后手动模拟插入10、20、30、15这几个值，把每一步的节点颜色和旋转都画出来。这一遍做下来，你对插入的Case基本就建立了肌肉记忆。

第二步，写一个“验证器”，不要直接写红黑树完整实现。你的代码只要能插入、能验证性质就够了，等验证器测试通过，再继续补充删除。把一个大项目拆成多个小步骤，是克服“咕咕咕”的最好办法。

第三步，看别人的实现，但别照抄。我建议你看懂思路后，合上别人的代码，自己从零写一遍。抄代码只会得到代码，重写代码才会得到能力。

我在带人的时候见过太多这种情况：读教程感觉全会，合上书直接大脑空白。这不是你的问题，是这门知识本来就需要“用手学”。红黑树不是一个靠看就能学会的知识点，它必须靠亲手写、亲手调、亲手验证，才能真正扎根。

最后再分享一个我的个人习惯：我每次重写红黑树，都会把插入场景的三大类和删除场景的四类修复写成注释，放在代码顶部。这样一年之后再翻代码，我扫一眼注释就能立刻回忆起整个修复流程。这个做法帮我省了非常多复习成本，你也不妨试试。