算法基础 -- 红黑树初识
红黑树初识
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它通过对每个节点增加颜色属性，以及在插入和删除节点时使用特定规则调整树结构来保持平衡。红黑树的特点是，在任何情况下，其树高都可以保持在 (O(\log n)) 的级别，从而确保了高效的查找、插入和删除操作。
红黑树的五大性质
- 节点颜色：每个节点要么是红色，要么是黑色。
- 根节点为黑色：树的根节点始终是黑色。
- 叶子节点为黑色：所有叶子节点（NIL，哨兵节点）都是黑色。
- 红色节点不能相邻：红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。
- 每个节点到其后代叶子的黑色节点数相同：对于任意节点，从该节点到叶子的所有路径上，黑色节点的数量相同，这一性质确保了红黑树的平衡性。
红黑树的操作
1. 查找（Search）
查找操作与普通的二叉搜索树相同，根据键值大小递归或迭代寻找目标节点。由于红黑树具有自平衡特性，查找的时间复杂度为 (O(\log n))。
2. 插入（Insertion）
红黑树插入新节点的过程分为两步：
- 按照普通二叉搜索树的规则插入新节点，初始将新节点设为红色。
- 根据红黑树的五大性质，对树结构进行修复，确保红黑性质不被破坏。
插入操作可能触发以下三种修复情况：
Case 1：叔节点是红色
如果新节点的父节点和叔节点均为红色：
- 将父节点和叔节点涂黑。
- 将祖父节点涂红。
- 将祖父节点作为新节点，继续向上检查修复。
Case 2：叔节点是黑色，且新节点是右子节点
如果新节点的父节点是红色，叔节点是黑色，且新节点是右子节点：
- 对父节点进行左旋，将新节点调整到外侧。
- 转化为 Case 3。
Case 3：叔节点是黑色，且新节点是左子节点
如果新节点的父节点是红色，叔节点是黑色，且新节点是左子节点：
- 对祖父节点进行右旋。
- 交换祖父节点和父节点的颜色。
3. 删除（Deletion）
删除操作首先按普通二叉搜索树规则找到目标节点，然后：
- 如果删除的节点是红色：直接删除。
- 如果删除的节点是黑色：会破坏黑高平衡，需要进行修复。
删除操作的修复场景包括以下四种：
Case 1：兄弟节点是红色
- 将兄弟节点涂黑，父节点涂红。
- 对父节点进行旋转。
- 转化为其他情况处理。
Case 2：兄弟节点是黑色，且兄弟的两个子节点均为黑色
- 将兄弟节点涂红。
- 将父节点作为新节点，向上递归修复。
Case 3：兄弟节点是黑色，兄弟的左子节点是红色，右子节点是黑色
- 将兄弟节点涂红，兄弟的左子节点涂黑。
- 对兄弟节点进行右旋。
- 转化为 Case 4。
Case 4：兄弟节点是黑色，兄弟的右子节点是红色
- 将兄弟节点的颜色设置为父节点的颜色。
- 将父节点涂黑，兄弟的右子节点涂黑。
- 对父节点进行旋转，修复完成。
插入操作示例
以插入以下节点序列为例：[7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13]
初始插入
- 插入 7：树为空，7 作为根节点，设为黑色。
- 插入 3：3 小于 7，挂到左侧，设为红色。
- 插入 18：18 大于 7，挂到右侧，设为红色。
修复插入冲突
- 插入 10：10 < 18，挂到 18 左侧；10 为红色，与父节点 18 同为红色，触发 Case 1。
- 祖父节点 7 变红，父节点 18 和叔节点 3 变黑。
- 根节点 7 重新涂黑。
- 插入 22：直接插入，无需修复。
- 插入 8：8 挂到 10 左侧，触发 Case 2 -> Case 3。
- 左旋父节点 10，将 8 调整为外侧。
- 右旋祖父节点 18，完成修复。
删除操作示例
以删除以下节点为例：[18, 3]
删除 18
- 删除后，18 的后继节点（或直接替换节点）补位。
- 如果删除的节点是黑色，触发 Case 1~4 中的修复规则，最终平衡树。
删除 3
- 删除 3，修复兄弟节点颜色冲突。
- 如果兄弟节点为黑色，且其子节点为黑色，触发 Case 2。
- 递归向上调整，直到根节点或不再有冲突。
红黑树的实现与优化
- 工程应用：
- C++ 的
std::map和std::set。 - Java 的
TreeMap和TreeSet。
- C++ 的
- 红黑树 vs AVL 树：
- AVL 树高度更严格平衡，查询性能稍优。
- 红黑树插入、删除效率更高，工程中更常用。
总结
红黑树的核心是通过“颜色约束”和“旋转”保持平衡，插入与删除的修复逻辑基于几种典型场景（Case 1~4）。虽然实现上需要细心处理，但由于其高效的时间复杂度和广泛的工程应用价值，红黑树是二叉搜索树中非常重要的一种变体。