7.4 红黑树

红黑树的五条性质、黑高与树高的关系，插入时的变色与旋转调整，以及与 AVL 树的比较。

考查要求 ★★☆ 理解五条性质黑高高度上界插入调整与 AVL 比较

为什么需要红黑树

为了保持 AVL 树的平衡性，插入和删除操作后，非常频繁地调整全树整体拓扑结构，代价较大。为此在 AVL 树的平衡标准上进一步放宽条件，引入了红黑树的结构：红黑树的插入、删除操作很少会破坏全局的平衡，即使破坏，最多只需要三次旋转就能解决（插入最多两次）。

口诀：“左根右，根叶黑，不红红，黑路同”。

与折半查找树和 B 树类似，为了便于对红黑树的实现和理解，引入了 $n + 1$ 个外部叶结点，以保证红黑树中每个结点（内部结点）的左、右孩子均非空。

从某结点出发（不含该结点）到达一个叶结点的任意一个简单路径上的黑结点总数称为该结点的黑高（记为 $bh$ ），根结点的黑高称为红黑树的黑高。

两个重要结论

从根到叶结点的最长路径不大于最短路径的 2 倍。由性质 5，从根到任意一个叶结点的简单路径最短时，这条路径必然全由黑结点构成；由性质 4，当某条路径最长时，这条路径必然是由黑结点和红结点相间构成的，此时红结点和黑结点的数量相同。
有 $n$ 个内部结点的红黑树的高度 $h \le 2\log_2(n+1)$ 。若红黑树的总高度为 $h$ ，则根结点黑高 $\ge h/2$ ，因此内部结点数 $n \ge 2^{h/2} - 1$ ，即 $h \le 2\log_2(n+1)$ 。

由此可见，红黑树的”适度平衡”，由 AVL 树的”高度平衡”降低到”任意一个结点左右子树的高度，相差不超过 2 倍”，也降低了动态操作时调整的频率。

此外还有一些推论：根结点黑高为 $h$ 的红黑树，内部结点数（关键字）至少有 $2^h - 1$ 个（全黑满树）；至多有 $2^{2h} - 1$ 个（红黑相间的满树）。

红黑树的插入过程和二叉查找树的插入过程基本类似，不同之处在于，在红黑树中插入新结点后需要进行调整（主要通过重新着色或旋转操作进行），以满足红黑树的性质。

设新插入的结点为 z，调整规则如下：

若 z 是根结点：把 z 染成黑色，结束；
若 z 的父结点是黑色：没有破坏任何性质，结束；
若 z 的父结点是红色（此时爷爷一定是黑色），看叔叔结点的颜色：
- 叔叔为红：父、叔染黑，爷爷染红，然后把爷爷当作新的 z，继续向上检查；
- 叔叔为黑（含 NIL）：根据 z、父、爷的相对位置旋转：LL/RR 型——对爷爷做一次右/左旋，然后父、爷交换颜色；LR/RL 型——先对父亲做左/右旋转化为 LL/RR 型，再对爷爷旋转，然后 z、爷交换颜色。

动画演示红黑树的插入

插入序列

z：当前检查的结点

1/32依次插入序列：10, 20, 30, 15, 25, 5, 1

红黑树的删除操作比插入复杂得多：先按二叉排序树的方法删除，若删除的是黑结点，则会破坏性质 5，需要根据兄弟结点的颜色及其孩子的情况分多种情况进行调整。删除操作的时间复杂度同样为 $O(\log_2 n)$ ，最多需要三次旋转。408 中对红黑树删除的具体过程考查较少，掌握插入即可。

	AVL 树	红黑树
平衡标准	任一结点左右子树高度差 ≤ 1	任一结点左右子树高度相差不超过 2 倍
查找	$O(\log_2 n)$ ，略快	$O(\log_2 n)$
插入/删除的调整代价	可能需要多次旋转（删除时可能一直传到根）	插入最多 2 次旋转，删除最多 3 次旋转
适用场景	查找多、修改少	插入删除频繁（如 C++ STL 的 `map`/`set`、Java 的 `TreeMap`）

即时练习4 题

点击选项即可作答

学完了吗？

标记完成后，侧栏会显示进度。进度仅保存在本浏览器中。