第13章 红黑树 — 章节汇总
章节概览
本章是 Part III 数据结构的高潮章节，系统介绍了红黑树（Red-Black Tree）——一种通过着色约束保证 树高的自平衡二叉搜索树。红黑树是第12章BST的自然延伸：BST解决了”如何操作”的问题，红黑树解决了”如何保证高效”的问题。通过5条着色性质，红黑树使得搜索、插入、删除等所有动态集合操作在最坏情况下均为 ，同时保持相对简单的实现（插入最多2次旋转，删除最多3次旋转）。
13.1 红黑树的性质
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 13.1 红黑树的性质 | 5条性质、黑高度、高度上界 |
核心思路：红黑树是一种二叉搜索树，每个节点额外存储颜色（红/黑），通过5条性质约束树的结构，保证树高 。
核心定理：
- 引理13.1：以 为根的子树至少包含 个内部节点（数学归纳法）
- 推论13.2： 个内部节点的红黑树高度
13.2 旋转
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 13.2 旋转 | 左旋、右旋 | 时间，保持BST性质 |
核心思路：旋转是红黑树插入和删除修复操作的唯一结构性修改手段。左旋和右旋在 时间内改变树的局部结构，同时保持BST性质（中序遍历不变）。旋转本身不保持红黑性质，但为变色操作创造条件。
13.3 插入
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 13.3 插入 | RB-INSERT、RB-INSERT-FIXUP | ，最多2次旋转 |
核心思路：新节点着红色（保证黑高度不变），然后通过 RB-INSERT-FIXUP 向上回溯修复可能违反的性质2（根为黑）和性质4（红节点的孩子为黑）。
三种情况（+三种镜像）：
- Case 1：叔叔为红 → 变色上移
- Case 2：叔叔为黑+当前为右孩子 → 左旋转Case 3
- Case 3：叔叔为黑+当前为左孩子 → 变色+右旋完成
13.4 删除
| 小节 | 核心主题 | 关键结论 |
|---|---|---|
| 13.4 删除 | RB-DELETE、RB-DELETE-FIXUP、额外黑色 | ，最多3次旋转 |
核心思路：当被移动的节点 为黑色时，引发黑高度不一致。引入"额外黑色"概念，将问题节点 视为带有”双重黑色”，通过 RB-DELETE-FIXUP 将额外黑色沿树上移。
四种情况（+四种镜像）：
- Case 1：兄弟为红 → 变色+左旋转Case 2/3/4
- Case 2：兄弟为黑+两侄子为黑 → 变色上移
- Case 3：兄弟为黑+近侄子为红+远侄子为黑 → 旋转转Case 4
- Case 4：兄弟为黑+远侄子为红 → 变色+左旋完成
本章核心知识点
红黑树操作复杂度汇总
| 操作 | 时间复杂度 | 旋转次数 | 说明 |
|---|---|---|---|
| 搜索 | 0 | 纯BST搜索 | |
| 最小值/最大值 | 0 | 沿边界下降 | |
| 前驱/后继 | 0 | 两种情况 | |
| 插入 | 着红色+修复 | ||
| 删除 | TRANSPLANT+修复 | ||
| 旋转 | 1 | 左旋/右旋 |
红黑树 vs AVL树 vs B树 对比
| 特性 | 红黑树 | AVL树 | B树 |
|---|---|---|---|
| 平衡策略 | 着色+旋转 | 高度差≤1 | 节点度数约束 |
| 树高上界 | |||
| 插入旋转 | （≤2次） | ||
| 删除旋转 | （≤3次） | ||
| 查找性能 | 较好 | 最优 | 取决于扇出 |
| 适用场景 | 通用内存数据结构 | 查找密集型 | 磁盘存储 |
红黑树5条性质
| 编号 | 性质 | 作用 |
|---|---|---|
| 1 | 每个节点是红色或黑色 | 基础定义 |
| 2 | 根节点是黑色 | 锚定黑高度 |
| 3 | 每个叶节点（NIL）是黑色 | 统一边界 |
| 4 | 红色节点的孩子都是黑色 | 防止连续红色 |
| 5 | 所有路径黑节点数相同 | 保证平衡 |
与前序章节的知识关联
| 前序章节 | 关联方式 |
|---|---|
| 第12章 二叉搜索树 | 红黑树是BST的特例，继承所有BST操作；RB-INSERT基于TREE-INSERT，RB-DELETE基于TRANSPLANT和TREE-DELETE |
| 第10章 基本数据结构 | 10.3节有根树的表示（p/left/right指针）是红黑树节点结构的基础 |
| 第11章 散列表 | 散列 期望 vs 红黑树 最坏；红黑树支持有序操作 |
| 第6章 堆排序 | 二叉堆 vs 红黑树：同为二叉树但性质不同（堆：父≥子；红黑树：左<根<右+着色约束） |
学习路线
第13章学习路径：
13.1 红黑树的性质（5条性质→黑高度→引理13.1→推论13.2）
→ 13.2 旋转（左旋→右旋→BST性质保持→O(1)分析）
→ 13.3 插入（着红色→RB-INSERT-FIXUP→3种情况→最多2次旋转）
→ 13.4 删除（额外黑色→RB-DELETE-FIXUP→4种情况→最多3次旋转）
学习建议
本章是数据结构部分最难的一章。13.1 是基础，重点理解5条性质的协同作用和引理13.1的归纳法证明。13.2 旋转相对简单，但需要深刻理解”旋转保持BST性质但不保持红黑性质”这一关键区分。13.3 插入是考试重点，三种情况（Case 1/2/3）的转换逻辑需要反复推敲。13.4 删除是全书最复杂的算法，建议结合可视化工具（如Red-Black Tree Visualizer）逐步跟踪每种情况的状态变化。学完本章后，回顾第12章BST的退化问题，理解红黑树如何通过着色约束从根本上解决了这一问题。