企业官网建设流程全解析

一棵树怎么做到"自平衡还不太费力"？——红黑树的旋转与染色

408 · 数据结构（45 分）· 树。红黑树的五条性质、与 AVL 的取舍、旋转与染色，是查找章节的高频选择题来源。

先把一棵树"插歪"给你看

假设你手写一棵普通的二叉查找树（BST），按1, 2, 3, 4, 5, 6, 7的顺序往里插。插完之后你会发现，这棵"树"长得跟一条斜线没什么两样——查找第 7 个节点要走 7 步，退化成了链表，O(n)。

问题出在哪？BST 只管"左小右大"，却不管树高。于是人们发明了各种"自平衡"二叉查找树：AVL 树是最早的一批，它要求左右子树高度差不超过 1，把树压得足够矮，代价是每次插入删除可能要多次旋转，维护成本不低。

红黑树（Red-Black Tree）走了另一条路：不追求"绝对最矮"，而是用一套"染色规则"保证树"矮得足够快、维护还不贵"。这篇文章就讲这套规则。

五条性质，一条都不能少

一棵红黑树，每个节点不是红就是黑，同时满足：

1. 每个节点要么是红色，要么是黑色；
2. 根节点是黑色；
3. 每个叶子（NIL 空节点）是黑色；
4. 红色节点的两个子节点必须是黑色（不能出现连续两个红）；
5. 从任一节点到其每个叶子的所有路径上，黑色节点数量相同（这条最关键，叫"黑高"一致）。

正是第 4、5 条，逼着树保持"大致平衡"。可以证明：

树高 ≤ 2 log ⁡ 2 ( n + 1 ) \text{树高} \le 2\log_2(n+1)树高≤2log2​(n+1)

也就是说，红黑树的最坏高度是2 log ⁡ ( n + 1 ) 2\log(n+1)2log(n+1)，查找、插入、删除都能保证O ( log ⁡ n ) O(\log n)O(logn)。虽然它没 AVL 那么"矮"（AVL 约1.44 log ⁡ n 1.44\log n1.44logn），但换来了更少的旋转次数——插入最多 2 次旋转，删除最多 3 次，比 AVL 的多次旋转省事得多。

染色与旋转：它平衡的两件工具

红黑树维持平衡，靠两个动作交替进行：

染色（recolor）：把某个节点从红变黑或从黑变红，用来调整"黑高"。

旋转（rotate）：和 AVL 一样，分左旋和右旋，用来调整树的结构。旋转不改变"中序遍历顺序"，只改变父子关系——所以旋转后它仍是合法的 BST。

插入一个新节点时，惯例先把它染成红色（这样不破坏第 5 条"黑高一致"），然后看它的"叔叔节点"（父节点的兄弟）是什么颜色，分几种情况修补：

情形 1：叔叔是红色 → 父、叔变黑，祖父变红，把问题上移到祖父继续处理 情形 2：叔叔是黑色，且新节点是父的"外侧" → 旋转父节点 + 重新染色，一次搞定 情形 3：叔叔是黑色，且新节点是父的"内侧" → 先旋转到外侧，再按情形 2 处理

细节不必全背，抓住一句话就够：“红红冲突就转一转、染一染，黑高始终不乱。”删除更复杂（要处理"少了一个黑"的情况），但思想和插入一样，都是"破坏哪条性质，就针对性修补哪条"。

红黑树 vs AVL，到底选谁

这是面试最爱问的对比题，答案其实藏在"读写比例"里：

一句话：AVL 是"查得极致"，红黑树是"写起来省心"。所以 Linux 的进程调度、Java 的TreeMap、C++ 的std::map，这些"插删频繁"的场合，清一色选了红黑树。

一个会出在选择题里的细节

408 选择题常考红黑树的性质判断题，比如：

一棵红黑树，从根到叶的最长路径，最多是最短路径的几倍？

根据性质 4（不能连续两个红）和性质 5（黑高一致），最长路径是"红黑红黑"交替，最短路径是"全黑"，所以最长最多是：

2 × 黑高 黑高 = 2 倍 \frac{2 \times \text{黑高}}{\text{黑高}} = 2 \text{ 倍}黑高2×黑高​=2倍

答案：2 倍。这就是"大致平衡"的量化含义——它没有 AVL 那么紧（AVL 最多约 1.44 倍），但换来的是插入删除的廉价。

回到开头那棵插歪的树：红黑树用"两条染色规则 + 几次旋转"，就换来了"任何时刻最坏O ( log ⁡ n ) O(\log n)O(logn)“的承诺。它不追求绝对最矮，只追求"矮得够用、维护还便宜”。下次再在源码里撞见rb_insert、rb_erase这样的函数名，你会知道——那团红黑相间里，藏着一套用"约束换效率"的平衡术。

红黑树、AVL 是数据结构"查找"一章的常客，想系统跟学，B站【408实验室】的《数据结构》里有从 BST 到红黑树的完整推导。