红黑树
含AI生成内容
红黑树
定义与五条性质
红黑树（Red-Black Tree, RBT）是一种自平衡的二叉排序树，每个结点增加一个存储位表示颜色（红色或黑色）。它通过颜色约束维持弱平衡，保证在最坏情况下基本操作的时间复杂度为 O(log n)。
五条性质
- 非红即黑：每个结点要么是红色，要么是黑色
- 根黑：根结点是黑色的
- 叶(NIL)黑：所有叶子结点（外部结点、NULL 结点）都是黑色的
- 不红红：红色结点的两个子结点都是黑色的（即不存在两个连续的红色结点）
- 黑高相等：从任一结点到其每个叶子的所有路径上包含相同数目的黑色结点
黑高（Black Height）
黑高（bh）是指从某个结点出发（不含该结点）到达任意一个叶子结点的路径上黑色结点的个数。性质 5 确保任一结点的所有叶子路径具有相同的黑高。
重要推论：如果一棵红黑树根结点的黑高为 bh，则它至少有 2^bh - 1 个内部结点（即一棵完全由黑色结点构成的满二叉树）。
红黑树的高度保证
红黑树的高度 h 满足：
h ≤ 2log₂(n + 1)证明思路：性质 4 和 5 共同保证了从根到叶子的最长路径不会超过最短路径的 2 倍。具体来说，任何路径上黑色结点数至少为 h/2（因为红色不能连续），又根据性质 5 所有路径黑色结点数相同设为 bh，则 h ≤ 2·bh。而 bh 对应的全黑树至少有 2^bh - 1 个结点，因此 n ≥ 2^bh - 1 ≥ 2^(h/2) - 1，得 h ≤ 2log₂(n+1)。
这说明红黑树虽然不如 AVL 严格平衡，但仍然是 O(log n) 的高度，且常数因子（2）可接受。
红黑树的基本操作
红黑树是二叉排序树（BST）的一种，查找过程与 BST 完全相同。插入和删除需要在 BST 操作后通过颜色调整和旋转来维持五条性质。
红黑树 vs AVL 树的对比
| 对比维度 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡条件 | 红黑约束（弱平衡） | |
| 高度 | ≤ 2log₂(n+1) | ≈ 1.44log₂(n+2) |
| 查找效率 | O(log n) | O(log n)，略快（更矮） |
| 插入旋转次数 | 最多 2 次 | 最多 1 次 |
| 删除旋转次数 | 最多 3 次 | O(log n) 次 |
| 插入/删除染色次数 | O(log n) 次染色 | 不涉及染色 |
| 实现复杂度 | 较复杂 | 中等 |
| 适用场景 | 频繁插入/删除 | 查找密集、插入删除少 |
考研结论：处理大量插入删除时用红黑树，查找密集时用 AVL 树。红黑树通过放宽平衡条件减少了旋转次数，以略微牺牲查找性能换取更优的写入性能。
红黑树的插入
核心规则
- 新插入的结点初始染为红色
- 如果插入后违背了性质 4（不红红），则需要进行调整
- 调整策略取决于叔父结点（父结点的兄弟）的颜色
插入调整（记忆口诀：插入看叔父）
情况 1：叔父为红色 → 染色
将父结点和叔父结点染为黑色，祖父结点染为红色，然后将当前结点上移至祖父结点继续检查。
B(黑) B(红) / \ / \ R(红) R(红) → 黑(黑) 黑(黑) ↓ ↓ 新插入 新插入情况 2：叔父为黑色 → 旋转 + 染色
这种情况需要根据新结点、父结点、祖父结点的相对位置，进行 LL/RR/LR/RL 旋转（旋转方法与 AVL 树 相同），然后染色。
以 LL 型为例（父在左、新结点在左）：
G(黑) P(黑) / \ / \ P(红) U(黑) → 新(红) G(红) / \ \新(红) U(黑)旋转后将父结点染黑、祖父结点染红。
插入总结
| 情况 | 叔父颜色 | 操作 | 旋转次数 |
|---|---|---|---|
| 1 | 红色 | 染色（父、叔染黑，祖父染红）后上移 | 0 |
| 2 | 黑色 | 旋转 + 染色 | 1 或 2 |
插入最多需要 2 次旋转（LR 或 RL 双旋）。如果持续出现情况 1，实际只需要染色，不涉及旋转，但最多上溯 O(log n) 层。
红黑树的删除
核心规则
- 删除操作比插入更复杂，调整策略取决于兄弟结点的颜色
- 删除操作本质上是在 BST 删除的基础上，对红黑性质进行修复
删除调整（记忆口诀：删除看兄弟）
兄弟为红色
兄弟染黑，父染红，左旋（或右旋）父结点，使兄弟变为黑色（转换为兄弟为黑色的情况）。
兄弟为黑色
根据兄弟的孩子颜色又细分为 4 种情况：
| 情况 | 兄弟的孩子 | 操作 |
|---|---|---|
| 1 | 兄弟有红色远侄（与兄弟方向一致的侄子） | 旋转 + 染色，直接结束 |
| 2 | 兄弟有红色近侄（与兄弟方向相反的侄子） | 先小旋转转换为情况 1 |
| 3 | 兄弟的两个孩子都是黑色 | 兄弟染红，上移当前结点 |
| 4 | （以上均不满足，兄弟为红色的情况） | 先旋转转换为 1-3 |
结论：红黑树的删除最多需要 3 次旋转，但可能需要进行 O(log n) 次染色。
红黑树的应用
| 应用场景 | 具体使用 |
|---|---|
| Linux 内核 | 完全公平调度器（CFS）、虚拟内存管理 |
| C++ STL | map、set、multimap、multiset（红黑树实现） |
| Java | HashMap（冲突链表 > 8 且数组长度 ≥ 64 时转为红黑树）、TreeMap、TreeSet |
| Nginx | 定时器管理 |
红黑树之所以在工程中广泛使用，是因为它在查找、插入、删除之间取得了良好的平衡——三种操作的时间复杂度都是 O(log n)，且插入最多 2 次旋转、删除最多 3 次旋转，适合写入频繁的场景。
考研高频考点
- 红黑树五条性质的记忆（特别是”不红红”和”黑高相等”）
- 给定红黑树，判断某结点插入/删除后的颜色变化
- 插入调整的分情况讨论（叔父颜色决定操作类型）
- 红黑树与 AVL 树的详细对比（选择题和简答题都可能考）
- 红黑树的高度上界 h ≤ 2log₂(n+1) 的推导
- 红黑树在实际系统中的应用实例
关联页面
- 二叉排序树与平衡二叉树 — 红黑树的基础（BST 性质）与 AVL 对比
- 树与二叉树基础 — 二叉树定义与存储结构
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
评论区
