红黑树这名字听起来像某种园艺植物但搞过底层开发的人都明白它其实是计算机科学里量产最高的平衡树结构。日常开发中HashMap在链表长度超过阈值后会把链表转成红黑树TreeMap和TreeSet底层就是红黑树Linux内核的CFS调度器、Nginx的定时器也有它的身影。面试时“红黑树的插入删除原理”更是被问烂了的高频题。这篇文章我结合自己的阅读和实现经验把红黑树的定义、旋转、插入删除修复、以及和B树的区别一次讲清楚适合正在啃算法、写中间件、或者准备面试的同学。很多人觉得红黑树难是因为它规则多、分支多看着像一棵树状的 if-else。但真正上手之后你会发现它的核心就两个动作旋转和变色再加一条“黑色高度守恒”的约束。只要你理解了每个 case 在修什么剩下的都是肌肉记忆。下面我从头拆一遍。1. 先搞懂红黑树是什么5条性质与设计初衷1.1 五条性质怎么背才不会忘红黑树是一棵满足额外着色规则的二叉搜索树任何一颗红黑树都必须同时满足五条性质节点非红即黑。根节点是黑色。所有叶子节点NIL是黑色。注意这里的叶子不是带数据的节点而是挂在每个真实节点下面的空节点。红色节点的两个子节点都是黑色也就是说红色节点不能连续出现。从任意节点到它每个叶子节点的路径上黑色节点的数量相同工程上叫“黑高相等”。这五条里性质 5 是最核心的。它保证了任意一条路径不会明显长于其他路径。因为红色不能连续所以最长路径也就是红黑交替的情况不会超过最短路径的两倍。对比严格的平衡二叉树这个平衡条件要宽松不少但复杂度依然稳定在 O(logN)。记忆上不需要死记。我自己的土办法是把它压缩成十六个字非红即黑、根黑叶黑、红不相邻、黑高相等。后面写代码时反复对照这四句话很多 bug 都能一眼看出来。实现里还会把所有的 NIL 节点统一成一个哨兵节点颜色为黑色这样在判断叔叔节点、兄弟节点颜色时很方便少写一堆 null 判断。1.2 为什么是红黑两色和AVL比有什么优势大多数教科书在讲完 AVL 树之后才上红黑树所以很多人会下意识地问已经有 AVL 了为什么还要红黑树答案是两者对“平衡”的定义不同牺牲了一点严格性换来更低的维护成本。AVL 要求任何节点的左右子树高度差不超过 1所以树的高度非常接近理论最小值查找路径很矮。但为了维持这种严格平衡插入和删除后可能需要回溯到根节点反复旋转最坏情况下开销很大。红黑树只要求黑高一致允许一定的红色节点堆积因此插入删除时的旋转次数更少整体吞吐量更稳定。比较项红黑树AVL树平衡条件每条路径黑高相同左右子树高度差不超过1树高约 2logN稍高约 1.44logN更矮插入修复最多旋转2次可能多次旋转回溯删除修复最多旋转3次可能一直回溯到根适用场景读写混合、工程库首选读多写少、追求极致查询这也就是为什么 Java 的 TreeMap、TreeSetC 的 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右子树是 gg 的左子树是原来的右兄弟子树。因为 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 BLACK3.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 的左孩子这个新兄弟是黑而且它的右孩子是原来的 ww 是红色。于是形态变成了“兄弟黑 右侄子红”正好进入 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 不同场景下的选型建议选择哪种树本质是选择“存储介质 操作模式”下的最优解。使用场景推荐结构理由内存中的有序集合/映射红黑树操作 O(logN)旋转开销小HashMap 冲突链表过长时红黑树链表的查找 O(N) 不可接受红黑树能在 O(logN) 内兜底数据库 InnoDB 索引B树节点对齐磁盘页IO 次数少支持高效范围扫描LSM Tree 的 memtable红黑树写入稳定中序遍历直接输出有序数据给 SSTable文件系统目录B树/B树索引规模大且持久化磁盘友好优先如果你的应用在内存里管理一批有序数据写多读也多红黑树是稳妥选择。如果你在写数据库或文件系统想用红黑树替代 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 可能为 NILNIL 的 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 画一遍哪怕不写代码理解也会上一个大台阶。后续如果要做内存索引、定时器或者有序数据结构红黑树都仍然是那个值得信赖的默认选择。