红黑树是一种用颜色规则维持「近似平衡」的二叉搜索树：它不追求严格等高，而是用五条性质把最长路径限制在最短路径的两倍以内，从而让查找、插入、删除稳定保持 O(log n)，同时把调整代价压到足够低。这正是它被 TreeMap、Linux 内核广泛采用的原因。

它解决什么问题

二叉搜索树的性能完全由形状决定，而形状由插入顺序决定。最坏情况是按升序或降序连续插入——树退化成一条斜链，查找从 O(log n) 跌回 O(n)，有序性带来的优势荡然无存。

要堵住这个漏洞，思路是在更新时主动修形。AVL 树选择了最强硬的方案：每个节点左右子树高度差不得超过 1。代价是插入删除可能触发沿路径向上的多次旋转，写得越多，维护越贵。红黑树给出了另一个答案：放宽平衡标准，只要求「最长路径不超过最短路径的两倍」。这个近似平衡足够把高度钉在 O(log n)，又宽松到大多数插入只需变色、少数才旋转，一次插入最多两次旋转。读性能略让，写性能大赚——这是它在工程界击败 AVL 的根本原因。

核心原理

五条性质

  1. 每个节点非红即黑；
  2. 根节点是黑色；
  3. 所有空叶子（NIL）视为黑色；
  4. 红节点的两个孩子必须是黑色，即不存在两个相邻的红节点；
  5. 从任一节点到其每个后代 NIL 的所有路径，包含相同数目的黑节点（黑高一致）。

前四条好记，第五条才是灵魂。性质 4 保证红色不能连续出现，性质 5 保证各路径的黑色配额相同，两者合起来推出关键结论：一条路径上红节点数最多与黑节点数相等，所以最长路径至多是最短路径的 2 倍，树高 h ≤ 2log(n+1)。这就是「近似平衡」的严格含义。

与 2-3-4 树的对应：颜色在编码什么

理解红黑树最透彻的视角是把它看成 2-3-4 树的二叉编码：把一个黑节点和它的红孩子纵向捏合，就还原出一个最多存 3 个键的多路节点。2-3-4 树是完美平衡的（所有叶子同层），这个性质被红黑树继承为「黑高一致」。插入时的变色对应 2-3-4 树节点的键合并，旋转对应节点分裂——所谓调整，不过是在二叉形态下重演多路树的自平衡动作。抓住这条主线，就不必死背 case 表。

深入机制

旋转：保序的局部重构

所有修复都建立在旋转之上。左旋让右孩子上位、自己降为其左孩子，右旋完全对称：

void rotateLeft(Node x) {
    Node y = x.right;        // y 即将上位
    x.right = y.left;        // y 的左子树过继给 x
    if (y.left != null) y.left.parent = x;
    y.parent = x.parent;     // y 接管 x 原来的父指针
    if (x.parent == null)      root = y;
    else if (x == x.parent.left) x.parent.left = y;
    else                       x.parent.right = y;
    y.left = x;
    x.parent = y;
}

旋转只改动常数个指针，且严格保持中序遍历结果不变——它改变的是形状，不是顺序。这是它能充当「修形工具」的数学基础。

插入修复：看叔叔脸色行事

新节点一律按 BST 规则落到叶子位置并染红。染红是经过计算的：红色不改变任何路径的黑高，所以性质 5 天然安全，唯一可能被破坏的是性质 4（父节点恰好也是红）。于是修复只需要围绕「父子双红」展开，分两大主线：

  • 叔叔是红：父、叔、祖父三人中祖父是唯一的黑。处理办法是把黑「往下分」——父叔染黑、祖父染红。双红就地消除，但祖父变红后可能与更上一层构成新双红，问题向上传播两层，循环继续。整条路径最多走 O(log n) 次变色，零旋转。
  • 叔叔是黑（或 NIL）：分黑不够用，必须靠旋转重塑局部。若新节点与父、祖构成折线（如父是左孩子、新节点是右孩子），先对父旋转把折线拉成直线；再对祖父反向旋转并交换祖与父的颜色。直线情形下黑节点上位接管，双红消失且黑高复原，修复就此终止——这是与叔红情形的本质区别。

汇总：叔红靠变色向上推，至多推到根；叔黑靠旋转就地解决，最多两次旋转（一次拉直 + 一次定型）。所以插入的最坏代价是 O(log n) 次变色加常数次旋转。

删除修复：双黑的消化

删除的复杂性在于：被移走的若是黑节点，某条路径的黑高就缺了 1，性质 5 被破坏。常用的思考模型是给「缺黑」的路径挂一个临时的「双黑」标记，然后尝试消化它：

  • 兄弟是红：先旋转父亲并换色，把兄弟转黑，转化为下面的情形；
  • 兄弟是黑且兄弟有红孩子：借兄弟的红孩子「补黑」，一次旋转加变色即可偿还，修复结束；
  • 兄弟是黑且其孩子全黑：把兄弟染红，相当于该子树整体让出一个黑，双黑标记上移到父亲，继续向上消化，最坏到根后整体黑高减一，全树依然合法。

不需要背全部排列组合，只要记住「红兄弟先转黑、黑侄子能还债、黑兄弟先染红再上报」这三句口诀，其余都是对称推演。

工程实践

  • JDK 的有序容器：TreeMap、TreeSet 直接以红黑树为骨架，保证 firstKey、floorKey 等有序操作 O(log n)。JDK 8 的 HashMap 在桶内链表长度达到 8 且容量不小于 64 时树化为红黑树，把恶意哈希碰撞下的查找从 O(n) 兜底到 O(log n)。
  • Linux epoll：用红黑树组织被监听的文件描述符，fd 的增删查都稳定 O(log n)，配合就绪链表实现高效的事件通知。
  • CFS 进程调度器：以虚拟运行时间 vruntime 为键，把可运行进程挂在红黑树上，调度时直接取最左节点（vruntime 最小者），O(1) 找到「最亏欠 CPU」的进程，插入新进程 O(log n)。
  • 共性很明确：这些场景都要求最坏情况上界稳定，且写操作频繁——恰好是红黑树对 AVL 的比较优势所在。

对比与权衡

维度 AVL 树 红黑树
平衡标准 左右子树高度差 ≤ 1，严格平衡 最长路径 ≤ 2×最短路径，近似平衡
树高上界 约 1.44log(n+2) 2log(n+1)
查找效率 树更矮，略快 略慢，常数差异
插入旋转 可能逐层向上，次数较多 最多 2 次
删除调整 最多 O(log n) 次旋转 最多 3 次旋转
平衡信息 每节点存高度/平衡因子 每节点 1 bit 颜色
适用场景 读远多于写的字典 读写均衡、写敏感的有序结构

一句话选型：读多写少、查询延迟敏感选 AVL；写操作频繁或要求稳定的删除上界选红黑树。

面试视角

为什么新插入的节点要染红而不是染黑？ 染黑会让所在路径黑高立刻加一，直接破坏性质 5，且破坏点可能离根很远、难以修复；染红不动黑高，最坏只是引入一对相邻红节点，而双红是局部问题，可以靠变色和旋转就地消化。

红黑树为什么叫近似平衡？ 性质 4 限制红色不连续，性质 5 锁定黑高一致，合起来保证最长路径不超过最短路径两倍，树高被压在 2log(n+1) 以内。它允许一定程度的高矮不齐，换取插入删除时少得多的结构调整。

红黑树相比 AVL 的优势在哪？ AVL 平衡更严、树更矮，查询略快，但插入删除的旋转频率明显更高。红黑树用稍高的树换取插入最多 2 次、删除最多 3 次旋转的硬上界，写频繁场景总体更划算，这也是工程实现普遍选它的原因。

HashMap 树化为什么选红黑树而不是 AVL？ 树化是为哈希碰撞兜底，触发后还会有频繁的插入和删除，AVL 的严格平衡会让这些写操作付出更多旋转；红黑树的宽松约束足以把查找压到 O(log n)，调整成本更低。

小结

  • 红黑树用五条性质维持近似平衡：红色不连续 + 黑高一致，推出最长路径 ≤ 2×最短路径，树高稳定 O(log n)。
  • 颜色是对平衡信息的紧凑编码，旋转是保序的局部重构，变色负责恢复黑高——三者分工明确。
  • 插入看叔叔：叔红变色上推、叔黑旋转定型；删除围绕「双黑」标记消化，口诀是红兄弟先转黑、红侄子来还债、黑兄弟染红上报。
  • 工程上它赢在写操作调整少、最坏上界稳，因此成为 TreeMap、epoll、CFS 的共同选择；与 AVL 的取舍本质是读略慢换写更省。