红黑树三个字可以说是算法面试里的老熟人。面试官一句讲一讲红黑树的性质很多人当场卡壳五条性质明明背过可一张嘴只能挤出节点要么红要么黑剩下的全是模糊感。我这些年面过不少候选人也带过团队发现能把红黑树性质讲得层次分明的人几乎都有一套自己的口诀或记忆锚点。问题不是你不努力而是这五条性质天然容易记混NIL 叶子、黑高这些概念又被教材讲得特别绕。我压箱底的这套红黑树性质口诀核心就四个词三黑一红。把它和插入、删除的修复场景串起来理解半小时就能把五条性质焊进脑子里面试时还能顺着口诀一路展开直接和只会背答案的候选人拉开差距。这篇文章就干三件事给你口诀、讲透原理、把面试里可能被追问的点全部排掉。适合正在准备的候选人、刚学数据结构的新手以及想真正看懂 TreeMap、HashMap 树化逻辑的开发者。1. 先解决一个前置问题红黑树到底在平衡什么1.1 二叉搜索树最怕的一种输入要理解红黑树的性质得先回到它要解决的问题。普通的二叉搜索树BST有一个致命弱点插入顺序一旦不理想树的高度就会失控。比如你按 1、2、3、4、5…… 的顺序依次插入这棵树会直接长成一条链表查找一个元素的时间从 O(log n) 退化到 O(n)。这个差距在实际生产中非常恐怖。100 万个有序节点平衡状态下的查找只需要大约 20 次比较链表形态却要老老实实比较 100 万次。你可以把平衡树类比成一本会自动整理索引的字典BST 退化后这本字典就变成了逐页翻找。红黑树的全部意义就是把这个最坏情况从 O(n) 锁死在 O(log n)。1.2 从 AVL 到红黑树平衡程度的不同选择平衡二叉树的思路有好几条路线。教科书里最经典的 AVL 树追求严格平衡任意节点的左右子树高度差不超过 1。AVL 的缺点是维护成本高插入或删除后很可能需要多次旋转写操作频繁的场景下性能并不好看。红黑树走的是另一条路线不追求完美平衡而是用颜色约束来保证最长路径不超过最短路径的两倍。这种弱平衡让它的旋转次数大幅减少同时最坏情况下的高度依然只有 O(log n)。你可以把 AVL 理解成洁癖选手红黑树则是性价比选手——查多写少的场景选 AVL读写比较均匀的场景红黑树明显更稳。1.3 红黑树的业务场景谁在生产环境用它如果只是面试考点红黑树不值得你花这么多时间。真正让它吃香的是工业界的广泛使用Java 的 TreeMap 和 TreeSet底层就是红黑树保证键的遍历有序。Java 8 及以后的 HashMap当单个桶的链表长度超过阈值默认 8时会把链表转成红黑树把极端冲突下的查询从 O(n) 降到 O(log n)。Linux 内核的 CFS 调度器、Nginx 的定时器管理底层也能看到红黑树的身影。C STL 里的 map、set绝大多数实现也基于红黑树。换句话说你平时写的代码底层可能正在跑一棵红黑树。理解了它的性质看这些源码时会顺畅得多。2. 红黑树五条性质原文翻译每个字都有用2.1 性质原文与人话对照先看官方表述红黑树一共五条性质每个节点是红色或黑色。根节点是黑色。每个叶子节点NIL是黑色。如果一个节点是红色那么它的两个子节点都是黑色。对每个节点从该节点到其所有后代叶子节点的简单路径上黑色节点的数目相同。这五条每一条翻译成人话都不难性质 1 是定义节点颜色只有两种性质 2 是门面树顶必须是黑色性质 3 的叶子指的是那些不存在的空节点代码里就是 null 指针统一按黑色处理性质 4 禁止红色节点连续出现性质 5 是说从任意节点往下走到任意一个空叶子沿途的黑色节点数必须完全一样。大多数人的记忆难点集中在 3 和 5。性质 3 让人疑惑叶子在哪——一棵树不是只有根节点和若干子节点吗这里必须引入 NIL 哨兵的概念。2.2 两个最容易被忽略的细节NIL 叶子与黑高红黑树在逻辑上给每个空指针都补了一个黑色的 NIL 叶子节点。你去画红黑树时如果某个节点没有左孩子或右孩子那它对应的这个位置就站着一个黑色 NIL。实际工程实现里通常会共享一个 NIL 对象省内存又方便代码处理。有了 NIL才谈得上性质 5 里的路径到底从哪算到哪。这里引出第二个关键概念黑高black height。从某个节点 x 往下走到 NIL 叶子路径上经过的黑色节点个数不包含 x 本身就是 x 的黑高。性质 5 说的黑色节点数目相同翻译过来就是从任意节点出发所有路径的黑高都相等。很多人一开始会把 NIL 当成透明空气于是怎么数都数不对。记住NIL 是黑色的实体节点每次数黑高都必须把它算进去。这是红黑树最容易踩的坑没有之一。2.3 五条性质是怎么联合起来保平安的五条性质放在一起核心效果是控制树高。直觉上可以这样推性质 5 保证了任意路径的黑高一致那么从根到叶子最短的那条路径理论上可以全是黑色节点性质 4 又限制了红色不能连续出现所以一条更长的路径只能在两个黑色节点中间穿插一个红色节点最长路径最多就是最短路径的两倍。两倍这个上限意味着整棵树的形状再歪也歪不到哪去最终推导出的结论是一棵有 n 个内部节点的红黑树高度不会超过 2·log₂(n1)。这就是性质 2 到 5 存在的意义——它们不是互相独立的怪规则而是一套互相配合、把树高锁死的约束体系。3. 红黑树性质口诀三黑一红四句全部拿下3.1 最简版口诀三黑一红我把五条性质压缩成一个更好记的口诀就四个字三黑一红。三黑之一根黑性质 2。三黑之二叶黑性质 3NIL 是黑色。三黑之三黑径同性质 5所有路径黑色节点数一样。一红红不连红性质 4红色节点的子节点必须是黑色。性质 1 的非红即黑是总前提不需要单独背。这样五条性质就变成了四个记忆点其中三个都带黑字唯一带红的那条是最容易违规的重点盯防。你可以在纸上写三遍根黑、叶黑、黑径同、红不连基本上就印在脑子里了。3.2 扩展版顺口溜带节奏感更好记如果四个词嫌干巴巴我再给一个稍微带节奏感的版本红黑树两色分根定黑色不用问空叶子也是黑数路径时莫放行红节点子必黑连续红色是违规任意路黑等身树高稳稳 log 内。这个顺口溜的每一句都对应一条性质最后一句树高稳稳 log 内是性质 2 到 5 联合推导出来的结果提醒自己这些性质最终是为了什么。我当年复习时每天默写一遍口诀再随手画一棵树验证黑高一周之后就再也没忘过。3.3 面试中怎么把口诀翻译成有分量的表达面试时光背口诀是不够的你得用口诀做骨架往外铺为什么。我建议的表达框架是这样红黑树的判定性质可以记成三黑一红根是黑的叶子NIL是黑的每条根到叶路径的黑色节点数一样红色节点不能连续出现。前三条负责控制黑高一致第四条把路径长度收紧到两倍以内所以整棵树不会退化最坏操作复杂度保持在 O(log n)。这样一段话说出来既体现了记忆功底又展示了理解深度。面试官如果继续追问自然就进入插入和删除的修复环节了。4. 口诀的实战演练插入修复三个场景4.1 新节点为什么默认染红红黑树做插入操作时第一个决定就是新节点涂什么颜色。答案永远是红色。原因很简单如果新节点涂成黑色那么经过它的那条路径凭空多出一个黑色节点直接违反性质 5而性质 5 是全局约束修起来代价极大。涂成红色则只可能违反性质 4如果父节点正好是红色而性质 4 是局部约束修起来方便得多。这个选择本身就是红黑树设计精妙的地方把问题引向最容易修复的方向。插入后的修复逻辑绕来绕去本质上都是在处理红不连红这条口诀。4.2 插入口诀看父亲、看叔叔变色或旋转插入修复的标准过程可以用三句话概括父亲是黑的不违规收工。父亲是红的立刻看叔叔的颜色。叔叔是红的变色叔叔是黑的旋转。叔叔红时的处理是变色把父亲和叔叔都涂黑把祖父涂红然后从祖父的位置继续向上检查。因为祖父变红后可能和更上面的红色节点又形成红不连红的冲突所以要把问题往上层层传递。叔叔黑或 NIL 黑时变色解决不了问题必须旋转。这里还分两种情况如果插入节点、父亲、祖父连成一条直线LL 或 RR直接对祖父做一次旋转如果是折线LR 或 RL先对父亲旋转一次变成直线再按直线处理。口诀就是叔叔红变色上顶叔叔黑先折后直再旋转。4.3 现场走一遍连续插入 10、20、30、40、50、60光说不练没有用我带你完整走一遍插入过程。初始是空树我们依次插入 10、20、30、40、50、60。第一步插入 10。作为根节点按口诀根黑直接涂黑。第二步插入 20涂红。父节点 10 是黑色不违规收工。第三步插入 30涂红。父节点 20 是红色看叔叔20 的叔叔是 10 的左孩子 NIL黑色。叔叔黑属于叔叔黑、直线场景30 是 20 的右孩子20 是 10 的右孩子RR 直线。对祖父 10 做左旋然后把原父节点 20 涂黑、原祖父 10 涂红。此时 20 成为新根左右孩子分别是 10 和 30都是红色合法。第四步插入 40涂红。父节点 30 是红色看叔叔叔叔是 10红色。叔叔红就走变色把 30 和 10 都涂黑祖父 20 涂红。祖父 20 是根按根黑原则涂回黑色。最后 20 黑色根10、30 黑色40 红色合法。第五步插入 50涂红。父节点 40 是红色叔叔是 30 的左孩子 NIL黑色。这是叔叔黑、RR 直线对祖父 30 左旋把 40 涂黑、30 涂红。此时 20 黑色根左侧 10 黑色右侧 40 黑色40 的左孩子 30 红色、右孩子 50 红色合法。第六步插入 60涂红。父节点 50 是红色叔叔是 30红色。叔叔红就变色50 和 30 都涂黑祖父 40 涂红。40 的父节点是黑色的 20没有继续冲突收工。最终树形20 黑色根左 10 黑色右 40 红色40 的左 30 黑色、右 50 黑色50 的右 60 红色。走完这个过程你会发现整个修复只在变色和旋转两种动作之间切换而判断入口就是那句口诀叔叔红变色叔叔黑旋转。4.4 源码对照TreeMap 的 fixAfterInsertion 长什么样理解口诀后再看源码豁然开朗。Java TreeMap 里插入修复的核心逻辑简化下来就是这样一个结构private void fixAfterInsertion(NodeK,V z) { while (z.parent ! null colorOf(z.parent) RED) { // 分支一父节点是祖父的左孩子 if (z.parent leftOf(grandpOf(z))) { NodeK,V y rightOf(grandpOf(z)); // 叔叔 if (colorOf(y) RED) { // 口诀叔叔红变色 setColor(z.parent, BLACK); setColor(y, BLACK); setColor(grandpOf(z), RED); z grandpOf(z); // 冲突向上传递 } else { // 口诀叔叔黑旋转 if (z rightOf(z.parent)) { // 折线先转直线 z z.parent; rotateLeft(z); } setColor(z.parent, BLACK); setColor(grandpOf(z), RED); rotateRight(grandpOf(z)); } } else { // 分支二父节点是祖父的右孩子逻辑完全对称 } } setColor(root, BLACK); // 兜底根永远是黑的 }你对照注释看代码的每个 if 分支都和口诀一一对应。这也是我推荐大家不要死背代码、而是先背口诀的原因口诀是操作系统的穴位图代码只是穴位图的实现。5. 删除修复口诀体系的终极考验5.1 为什么删除黑节点比插入麻烦一个量级插入违规只动红不连红删除则可能直接捅破黑径同这层窗户纸。想想看如果删掉的是一个黑色节点那么经过它子孙的所有路径都会少一个黑色节点性质 5 全局崩溃。如果删掉的是红色节点黑色数量完全不受影响直接收工。真正的噩梦是删黑色节点这时你需要引入双黑概念被删除节点的位置上的替代节点被看成携带了两份黑色一份是自己的一份是从被删节点继承来的。整个删除修复过程都是在想办法把多余的这份黑色还回去。可以这么说插入是处理多余的红色删除是处理短缺的黑色。5.2 双黑概念与删除四 case 口诀删除修复的标准 case 有四种全部围绕被删节点 x 的兄弟节点sibling展开。我整理了一个方便记忆的口诀删黑生双黑找兄弟来解决兄弟若为红变黑旋父换角色兄弟全黑子兄弟变红双黑向上走远侄红父兄换色再一旋双黑当场消近侄红先旋近侄变远侄重复上一招。这四句对应四类情况兄弟红、兄弟黑但两个侄子全黑、兄弟黑且远侄子红、兄弟黑且近侄子红远侄子黑。你不需要在面试时把四句话一字不差背出来但一定要能说出三个关键词双黑、借黑色、把双黑上移。这三个词一出面试官就知道你真的理解删除修复的本质。5.3 一个删除示例的完整修复过程用前面插入完的树继续演示。树形是20 黑色根左孩子 10 黑色右孩子 40 红色40 的左孩子 30 黑色、右孩子 50 黑色50 的右孩子 60 红色。现在删除黑色节点 10。10 是没有孩子的黑色叶子删掉之后它原来的 NIL 位置变成了携带双黑的节点 x。看 x 的兄弟10 的父节点是 20兄弟是 40红色。套口诀兄弟若为红变黑旋父换角色先把兄弟 40 涂黑父节点 20 涂红再对 20 做左旋。旋转后 40 上升为根20 变成 40 的左孩子20 的右孩子变成原来的 30。现在的双黑节点 x20 的左 NIL父节点是红色的 20兄弟是 30兄弟 30 是黑色而且 30 的两个孩子都是 NIL 黑色。套口诀兄弟全黑子兄弟变红双黑向上走把 30 涂红双黑状态上移给父节点 20。但 20 本身是红色红色节点携带双黑时直接把双黑消化掉——给 20 涂回黑色全部修复完成。最终树形40 黑色根左孩子 20 黑色右孩子 50 黑色20 的右孩子 30 红色50 的右孩子 60 红色。我建议你随手验证一下这棵树的五条性质会发现全部满足。这个验证过程本身就是最好的复习。6. 面试高频追问与记忆排雷6.1 五个高频问题的标准答案面试官在红黑树性质之外最爱追问以下五个问题Map 为什么用红黑树而不用 AVL答写操作多红黑树旋转少摊还性能更好AVL 对读操作更友好但写频繁时旋转开销大。HashMap 为什么链表长度到了 8 就转红黑树答链表的查询是 O(n)红黑树是 O(log n)阈值 8 结合泊松分布模型绝大多数桶不会触发树化遇到极端哈希冲突时有兜底方案。TreeMap 怎么保证有序答红黑树是中序遍历天然有序的二叉搜索树TreeMap 的键迭代器就是按红黑树中序输出。红黑树的查找复杂度是多少答最坏 O(log n)这也是性质 2 到 5 联合保证的结论。空树是红黑树吗答是空树视为一个黑色 NIL 根满足全部五条性质。6.2 三个普遍误解踩中一个就露馅第一个误解是把 NIL 当作不存在。性质 3 里的叶子特指 NIL不是普通意义上的叶子节点计算黑高时必须把它算作一个黑色节点。第二个误解是认为红黑树是平衡二叉树。严格说AVL 那种左右子树高度差不超过 1 才叫平衡二叉树红黑树是弱平衡或近似平衡面试时用词严谨会加分。第三个误解是以为红色节点的父节点不能是红色和红节点不能连续是两条性质其实它们是性质 4 的两种等价说法别在表述上自我混乱。另外补充一个冷知识性质 4 其实是包含在性质 5 的延伸里的红黑树的很多变体简化版只用根黑和黑高一致两条即可推导出基本平衡但传统定义仍然保留五条面试以五条为准。6.3 考前冲刺两分钟自检法如果你马上要面试我建议用这个方法做最后的临门一脚。每天花两分钟依次做三件事第一默写口诀根黑、叶黑、黑径同、红不连不到十秒第二随手画一棵树给每条路径数一遍黑高看是否相等第三口述一遍插入修复的逻辑链路查询父红不红、看叔叔红不黑、红则变色、黑则旋转。我自己带过的新人里坚持这套自检一周的没有一个在红黑树性质上翻车。你甚至可以把它变成一种习惯等电梯、午休前、排队时脑子里过一遍这四组词成本极低回报极稳。最后再分享一个我个人的经验红黑树这种知识点永远不要先背代码永远先背性质口诀。口诀是骨架代码只是骨架上长的肉。等你把三黑一红和插入删除的修复套路融为一体再看任何一处红黑树源码都会有种看地图的清晰感。这个感受只有自己真正走一遍流程才能体会到。
红黑树三个字可以说是算法面试里的老熟人。面试官一句讲一讲红黑树的性质很多人当场卡壳五条性质明明背过可一张嘴只能挤出节点要么红要么黑剩下的全是模糊感。我这些年面过不少候选人也带过团队发现能把红黑树性质讲得层次分明的人几乎都有一套自己的口诀或记忆锚点。问题不是你不努力而是这五条性质天然容易记混NIL 叶子、黑高这些概念又被教材讲得特别绕。我压箱底的这套红黑树性质口诀核心就四个词三黑一红。把它和插入、删除的修复场景串起来理解半小时就能把五条性质焊进脑子里面试时还能顺着口诀一路展开直接和只会背答案的候选人拉开差距。这篇文章就干三件事给你口诀、讲透原理、把面试里可能被追问的点全部排掉。适合正在准备的候选人、刚学数据结构的新手以及想真正看懂 TreeMap、HashMap 树化逻辑的开发者。1. 先解决一个前置问题红黑树到底在平衡什么1.1 二叉搜索树最怕的一种输入要理解红黑树的性质得先回到它要解决的问题。普通的二叉搜索树BST有一个致命弱点插入顺序一旦不理想树的高度就会失控。比如你按 1、2、3、4、5…… 的顺序依次插入这棵树会直接长成一条链表查找一个元素的时间从 O(log n) 退化到 O(n)。这个差距在实际生产中非常恐怖。100 万个有序节点平衡状态下的查找只需要大约 20 次比较链表形态却要老老实实比较 100 万次。你可以把平衡树类比成一本会自动整理索引的字典BST 退化后这本字典就变成了逐页翻找。红黑树的全部意义就是把这个最坏情况从 O(n) 锁死在 O(log n)。1.2 从 AVL 到红黑树平衡程度的不同选择平衡二叉树的思路有好几条路线。教科书里最经典的 AVL 树追求严格平衡任意节点的左右子树高度差不超过 1。AVL 的缺点是维护成本高插入或删除后很可能需要多次旋转写操作频繁的场景下性能并不好看。红黑树走的是另一条路线不追求完美平衡而是用颜色约束来保证最长路径不超过最短路径的两倍。这种弱平衡让它的旋转次数大幅减少同时最坏情况下的高度依然只有 O(log n)。你可以把 AVL 理解成洁癖选手红黑树则是性价比选手——查多写少的场景选 AVL读写比较均匀的场景红黑树明显更稳。1.3 红黑树的业务场景谁在生产环境用它如果只是面试考点红黑树不值得你花这么多时间。真正让它吃香的是工业界的广泛使用Java 的 TreeMap 和 TreeSet底层就是红黑树保证键的遍历有序。Java 8 及以后的 HashMap当单个桶的链表长度超过阈值默认 8时会把链表转成红黑树把极端冲突下的查询从 O(n) 降到 O(log n)。Linux 内核的 CFS 调度器、Nginx 的定时器管理底层也能看到红黑树的身影。C STL 里的 map、set绝大多数实现也基于红黑树。换句话说你平时写的代码底层可能正在跑一棵红黑树。理解了它的性质看这些源码时会顺畅得多。2. 红黑树五条性质原文翻译每个字都有用2.1 性质原文与人话对照先看官方表述红黑树一共五条性质每个节点是红色或黑色。根节点是黑色。每个叶子节点NIL是黑色。如果一个节点是红色那么它的两个子节点都是黑色。对每个节点从该节点到其所有后代叶子节点的简单路径上黑色节点的数目相同。这五条每一条翻译成人话都不难性质 1 是定义节点颜色只有两种性质 2 是门面树顶必须是黑色性质 3 的叶子指的是那些不存在的空节点代码里就是 null 指针统一按黑色处理性质 4 禁止红色节点连续出现性质 5 是说从任意节点往下走到任意一个空叶子沿途的黑色节点数必须完全一样。大多数人的记忆难点集中在 3 和 5。性质 3 让人疑惑叶子在哪——一棵树不是只有根节点和若干子节点吗这里必须引入 NIL 哨兵的概念。2.2 两个最容易被忽略的细节NIL 叶子与黑高红黑树在逻辑上给每个空指针都补了一个黑色的 NIL 叶子节点。你去画红黑树时如果某个节点没有左孩子或右孩子那它对应的这个位置就站着一个黑色 NIL。实际工程实现里通常会共享一个 NIL 对象省内存又方便代码处理。有了 NIL才谈得上性质 5 里的路径到底从哪算到哪。这里引出第二个关键概念黑高black height。从某个节点 x 往下走到 NIL 叶子路径上经过的黑色节点个数不包含 x 本身就是 x 的黑高。性质 5 说的黑色节点数目相同翻译过来就是从任意节点出发所有路径的黑高都相等。很多人一开始会把 NIL 当成透明空气于是怎么数都数不对。记住NIL 是黑色的实体节点每次数黑高都必须把它算进去。这是红黑树最容易踩的坑没有之一。2.3 五条性质是怎么联合起来保平安的五条性质放在一起核心效果是控制树高。直觉上可以这样推性质 5 保证了任意路径的黑高一致那么从根到叶子最短的那条路径理论上可以全是黑色节点性质 4 又限制了红色不能连续出现所以一条更长的路径只能在两个黑色节点中间穿插一个红色节点最长路径最多就是最短路径的两倍。两倍这个上限意味着整棵树的形状再歪也歪不到哪去最终推导出的结论是一棵有 n 个内部节点的红黑树高度不会超过 2·log₂(n1)。这就是性质 2 到 5 存在的意义——它们不是互相独立的怪规则而是一套互相配合、把树高锁死的约束体系。3. 红黑树性质口诀三黑一红四句全部拿下3.1 最简版口诀三黑一红我把五条性质压缩成一个更好记的口诀就四个字三黑一红。三黑之一根黑性质 2。三黑之二叶黑性质 3NIL 是黑色。三黑之三黑径同性质 5所有路径黑色节点数一样。一红红不连红性质 4红色节点的子节点必须是黑色。性质 1 的非红即黑是总前提不需要单独背。这样五条性质就变成了四个记忆点其中三个都带黑字唯一带红的那条是最容易违规的重点盯防。你可以在纸上写三遍根黑、叶黑、黑径同、红不连基本上就印在脑子里了。3.2 扩展版顺口溜带节奏感更好记如果四个词嫌干巴巴我再给一个稍微带节奏感的版本红黑树两色分根定黑色不用问空叶子也是黑数路径时莫放行红节点子必黑连续红色是违规任意路黑等身树高稳稳 log 内。这个顺口溜的每一句都对应一条性质最后一句树高稳稳 log 内是性质 2 到 5 联合推导出来的结果提醒自己这些性质最终是为了什么。我当年复习时每天默写一遍口诀再随手画一棵树验证黑高一周之后就再也没忘过。3.3 面试中怎么把口诀翻译成有分量的表达面试时光背口诀是不够的你得用口诀做骨架往外铺为什么。我建议的表达框架是这样红黑树的判定性质可以记成三黑一红根是黑的叶子NIL是黑的每条根到叶路径的黑色节点数一样红色节点不能连续出现。前三条负责控制黑高一致第四条把路径长度收紧到两倍以内所以整棵树不会退化最坏操作复杂度保持在 O(log n)。这样一段话说出来既体现了记忆功底又展示了理解深度。面试官如果继续追问自然就进入插入和删除的修复环节了。4. 口诀的实战演练插入修复三个场景4.1 新节点为什么默认染红红黑树做插入操作时第一个决定就是新节点涂什么颜色。答案永远是红色。原因很简单如果新节点涂成黑色那么经过它的那条路径凭空多出一个黑色节点直接违反性质 5而性质 5 是全局约束修起来代价极大。涂成红色则只可能违反性质 4如果父节点正好是红色而性质 4 是局部约束修起来方便得多。这个选择本身就是红黑树设计精妙的地方把问题引向最容易修复的方向。插入后的修复逻辑绕来绕去本质上都是在处理红不连红这条口诀。4.2 插入口诀看父亲、看叔叔变色或旋转插入修复的标准过程可以用三句话概括父亲是黑的不违规收工。父亲是红的立刻看叔叔的颜色。叔叔是红的变色叔叔是黑的旋转。叔叔红时的处理是变色把父亲和叔叔都涂黑把祖父涂红然后从祖父的位置继续向上检查。因为祖父变红后可能和更上面的红色节点又形成红不连红的冲突所以要把问题往上层层传递。叔叔黑或 NIL 黑时变色解决不了问题必须旋转。这里还分两种情况如果插入节点、父亲、祖父连成一条直线LL 或 RR直接对祖父做一次旋转如果是折线LR 或 RL先对父亲旋转一次变成直线再按直线处理。口诀就是叔叔红变色上顶叔叔黑先折后直再旋转。4.3 现场走一遍连续插入 10、20、30、40、50、60光说不练没有用我带你完整走一遍插入过程。初始是空树我们依次插入 10、20、30、40、50、60。第一步插入 10。作为根节点按口诀根黑直接涂黑。第二步插入 20涂红。父节点 10 是黑色不违规收工。第三步插入 30涂红。父节点 20 是红色看叔叔20 的叔叔是 10 的左孩子 NIL黑色。叔叔黑属于叔叔黑、直线场景30 是 20 的右孩子20 是 10 的右孩子RR 直线。对祖父 10 做左旋然后把原父节点 20 涂黑、原祖父 10 涂红。此时 20 成为新根左右孩子分别是 10 和 30都是红色合法。第四步插入 40涂红。父节点 30 是红色看叔叔叔叔是 10红色。叔叔红就走变色把 30 和 10 都涂黑祖父 20 涂红。祖父 20 是根按根黑原则涂回黑色。最后 20 黑色根10、30 黑色40 红色合法。第五步插入 50涂红。父节点 40 是红色叔叔是 30 的左孩子 NIL黑色。这是叔叔黑、RR 直线对祖父 30 左旋把 40 涂黑、30 涂红。此时 20 黑色根左侧 10 黑色右侧 40 黑色40 的左孩子 30 红色、右孩子 50 红色合法。第六步插入 60涂红。父节点 50 是红色叔叔是 30红色。叔叔红就变色50 和 30 都涂黑祖父 40 涂红。40 的父节点是黑色的 20没有继续冲突收工。最终树形20 黑色根左 10 黑色右 40 红色40 的左 30 黑色、右 50 黑色50 的右 60 红色。走完这个过程你会发现整个修复只在变色和旋转两种动作之间切换而判断入口就是那句口诀叔叔红变色叔叔黑旋转。4.4 源码对照TreeMap 的 fixAfterInsertion 长什么样理解口诀后再看源码豁然开朗。Java TreeMap 里插入修复的核心逻辑简化下来就是这样一个结构private void fixAfterInsertion(NodeK,V z) { while (z.parent ! null colorOf(z.parent) RED) { // 分支一父节点是祖父的左孩子 if (z.parent leftOf(grandpOf(z))) { NodeK,V y rightOf(grandpOf(z)); // 叔叔 if (colorOf(y) RED) { // 口诀叔叔红变色 setColor(z.parent, BLACK); setColor(y, BLACK); setColor(grandpOf(z), RED); z grandpOf(z); // 冲突向上传递 } else { // 口诀叔叔黑旋转 if (z rightOf(z.parent)) { // 折线先转直线 z z.parent; rotateLeft(z); } setColor(z.parent, BLACK); setColor(grandpOf(z), RED); rotateRight(grandpOf(z)); } } else { // 分支二父节点是祖父的右孩子逻辑完全对称 } } setColor(root, BLACK); // 兜底根永远是黑的 }你对照注释看代码的每个 if 分支都和口诀一一对应。这也是我推荐大家不要死背代码、而是先背口诀的原因口诀是操作系统的穴位图代码只是穴位图的实现。5. 删除修复口诀体系的终极考验5.1 为什么删除黑节点比插入麻烦一个量级插入违规只动红不连红删除则可能直接捅破黑径同这层窗户纸。想想看如果删掉的是一个黑色节点那么经过它子孙的所有路径都会少一个黑色节点性质 5 全局崩溃。如果删掉的是红色节点黑色数量完全不受影响直接收工。真正的噩梦是删黑色节点这时你需要引入双黑概念被删除节点的位置上的替代节点被看成携带了两份黑色一份是自己的一份是从被删节点继承来的。整个删除修复过程都是在想办法把多余的这份黑色还回去。可以这么说插入是处理多余的红色删除是处理短缺的黑色。5.2 双黑概念与删除四 case 口诀删除修复的标准 case 有四种全部围绕被删节点 x 的兄弟节点sibling展开。我整理了一个方便记忆的口诀删黑生双黑找兄弟来解决兄弟若为红变黑旋父换角色兄弟全黑子兄弟变红双黑向上走远侄红父兄换色再一旋双黑当场消近侄红先旋近侄变远侄重复上一招。这四句对应四类情况兄弟红、兄弟黑但两个侄子全黑、兄弟黑且远侄子红、兄弟黑且近侄子红远侄子黑。你不需要在面试时把四句话一字不差背出来但一定要能说出三个关键词双黑、借黑色、把双黑上移。这三个词一出面试官就知道你真的理解删除修复的本质。5.3 一个删除示例的完整修复过程用前面插入完的树继续演示。树形是20 黑色根左孩子 10 黑色右孩子 40 红色40 的左孩子 30 黑色、右孩子 50 黑色50 的右孩子 60 红色。现在删除黑色节点 10。10 是没有孩子的黑色叶子删掉之后它原来的 NIL 位置变成了携带双黑的节点 x。看 x 的兄弟10 的父节点是 20兄弟是 40红色。套口诀兄弟若为红变黑旋父换角色先把兄弟 40 涂黑父节点 20 涂红再对 20 做左旋。旋转后 40 上升为根20 变成 40 的左孩子20 的右孩子变成原来的 30。现在的双黑节点 x20 的左 NIL父节点是红色的 20兄弟是 30兄弟 30 是黑色而且 30 的两个孩子都是 NIL 黑色。套口诀兄弟全黑子兄弟变红双黑向上走把 30 涂红双黑状态上移给父节点 20。但 20 本身是红色红色节点携带双黑时直接把双黑消化掉——给 20 涂回黑色全部修复完成。最终树形40 黑色根左孩子 20 黑色右孩子 50 黑色20 的右孩子 30 红色50 的右孩子 60 红色。我建议你随手验证一下这棵树的五条性质会发现全部满足。这个验证过程本身就是最好的复习。6. 面试高频追问与记忆排雷6.1 五个高频问题的标准答案面试官在红黑树性质之外最爱追问以下五个问题Map 为什么用红黑树而不用 AVL答写操作多红黑树旋转少摊还性能更好AVL 对读操作更友好但写频繁时旋转开销大。HashMap 为什么链表长度到了 8 就转红黑树答链表的查询是 O(n)红黑树是 O(log n)阈值 8 结合泊松分布模型绝大多数桶不会触发树化遇到极端哈希冲突时有兜底方案。TreeMap 怎么保证有序答红黑树是中序遍历天然有序的二叉搜索树TreeMap 的键迭代器就是按红黑树中序输出。红黑树的查找复杂度是多少答最坏 O(log n)这也是性质 2 到 5 联合保证的结论。空树是红黑树吗答是空树视为一个黑色 NIL 根满足全部五条性质。6.2 三个普遍误解踩中一个就露馅第一个误解是把 NIL 当作不存在。性质 3 里的叶子特指 NIL不是普通意义上的叶子节点计算黑高时必须把它算作一个黑色节点。第二个误解是认为红黑树是平衡二叉树。严格说AVL 那种左右子树高度差不超过 1 才叫平衡二叉树红黑树是弱平衡或近似平衡面试时用词严谨会加分。第三个误解是以为红色节点的父节点不能是红色和红节点不能连续是两条性质其实它们是性质 4 的两种等价说法别在表述上自我混乱。另外补充一个冷知识性质 4 其实是包含在性质 5 的延伸里的红黑树的很多变体简化版只用根黑和黑高一致两条即可推导出基本平衡但传统定义仍然保留五条面试以五条为准。6.3 考前冲刺两分钟自检法如果你马上要面试我建议用这个方法做最后的临门一脚。每天花两分钟依次做三件事第一默写口诀根黑、叶黑、黑径同、红不连不到十秒第二随手画一棵树给每条路径数一遍黑高看是否相等第三口述一遍插入修复的逻辑链路查询父红不红、看叔叔红不黑、红则变色、黑则旋转。我自己带过的新人里坚持这套自检一周的没有一个在红黑树性质上翻车。你甚至可以把它变成一种习惯等电梯、午休前、排队时脑子里过一遍这四组词成本极低回报极稳。最后再分享一个我个人的经验红黑树这种知识点永远不要先背代码永远先背性质口诀。口诀是骨架代码只是骨架上长的肉。等你把三黑一红和插入删除的修复套路融为一体再看任何一处红黑树源码都会有种看地图的清晰感。这个感受只有自己真正走一遍流程才能体会到。
