1. 概述
红黑树（Red-Black Tree）是一种自平衡的二叉查找树（BST），广泛用于实现高效查找、插入和删除操作的场景。它通过引入颜色规则和旋转操作，确保树在任意插入或删除操作后仍保持近似平衡。
本文将从二叉查找树和 2-3 树讲起，逐步引出红黑树的设计思想，并解释其如何通过简单的旋转和颜色翻转操作，实现对树结构的高效维护。
2. 二叉查找树（BST）
2.1 基本结构
二叉查找树是一种每个节点最多有两个子节点的树结构：
- 左子节点的值 < 当前节点的值
- 右子节点的值 > 当前节点的值
树的高度决定了查找效率。理想情况下，树的高度为 *O(log n)*，查找效率高。
2.2 平衡与不平衡 BST 示例
我们插入如下元素：4, 8, 12, 16, 18, 24, 32，构建出一棵平衡的 BST：
此时树高度为 log n，查找效率为 *O(log n)*。
但如果插入顺序为：24, 32, 16, 18, 12, 8, 4，则树会变得不平衡：
最坏情况下，BST 退化成链表，查找效率为 *O(n)*。
2.3 踩坑点
BST 的性能高度依赖插入顺序，不加控制的插入会导致性能急剧下降，因此需要引入平衡机制。
3. 平衡的 2-3 树
3.1 2-3 树定义
2-3 树是一种平衡多路查找树，节点类型有两种：
- 2-节点：一个值 + 两个子节点
- 3-节点：两个值 + 三个子节点
2-3 树通过节点分裂和合并来保持树的平衡。
3.2 插入过程示例
以插入顺序 32, 24, 18, 16, 12, 8, 4 为例：
插入 32 和 24 后形成一个 3-节点：
插入 18 后，树不平衡，需要调整：
后续插入 16, 12, 8, 4，每一步都可能触发节点分裂和上提操作，最终形成一棵平衡的 2-3 树。
3.3 插入复杂度分析
2-3 树的插入操作虽然能保证平衡，但实现复杂，需要处理 2-节点、3-节点、4-节点等多种情况。
4. 红黑树详解
4.1 红黑树与 2-3 树的对应关系
红黑树本质上是 2-3 树的一种等价表示方式。通过将 3-节点拆分为两个 2-节点，并用红色链接连接它们，即可得到红黑树。
例如，下面是一个 2-3 树与对应的红黑树：
4.2 红黑树的五大性质
红黑树满足以下五个性质：
✅ 每个节点要么是红色，要么是黑色
✅ 根节点是黑色
✅ 所有叶子节点（null）是黑色
✅ 不能有两个连续的红色节点（即红节点的子节点必须是黑的）
✅ 从任一节点到其每个叶子的所有路径都包含相同数目的黑节点
4.3 插入操作
新节点总是插入为叶子节点，并标记为红色。插入后可能导致红黑性质被破坏，需通过以下三种操作进行调整：
4.3.1 左旋（Left Rotate）
4.3.2 右旋（Right Rotate）
4.3.3 颜色翻转（Color Flip）
这三种操作都是局部操作，不会影响整棵树结构。
4.4 插入示例
以插入元素 37 为例：
初始状态：
插入后，进行颜色翻转：
继续调整：
最后进行左旋，完成插入：
4.5 删除操作
删除操作也依赖上述三种操作进行调整。对于非叶子节点，先将其转换为叶子节点（通过交换最大/最小值），再进行删除。
删除示例：删除 2
叶子节点且为红色，直接删除即可：
删除示例：删除 36
也是叶子节点，但为右子节点，删除后需重新连接父节点：
删除示例：删除 8
先将 8 移动为叶子节点（与左子树最大值 4 交换），再删除：
最终树仍保持红黑性质：
删除示例：删除 24
删除后需进行旋转操作以恢复平衡：
旋转后恢复平衡：
5. 时间复杂度分析
| 操作 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 查找 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) |
| 重平衡操作 | O(1) | O(log n) |
此外，红黑树在并行操作和批量构建方面也有良好表现。
6. 应用场景
红黑树广泛应用于底层系统和库中：
- ✅ Java 集合框架：
TreeSet,TreeMap,HashMap（链表转红黑树） - ✅ Linux 内核调度器（CFS）
- ✅ Linux 的内存映射操作（
mmap,munmap） - ✅ 几何范围查找、K-Means 聚类、文本挖掘等算法中
虽然开发者很少直接操作红黑树，但其在底层性能优化中扮演重要角色。
7. 总结
红黑树是 2-3 树的一种等价实现，通过颜色标记和旋转操作，实现高效的插入、查找和删除。其优势在于：
- ✅ 插入和删除的平均性能优于 AVL 树
- ✅ 保证最坏时间复杂度为 O(log n)
- ✅ 适用于频繁更新的场景
选择数据结构时应综合考虑业务需求，红黑树适合对插入、查找性能要求较高，且更新频繁的场景。