红黑树初识

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它通过对每个节点增加颜色属性，以及在插入和删除节点时使用特定规则调整树结构来保持平衡。红黑树的特点是，在任何情况下，其树高都可以保持在 (O(\log n)) 的级别，从而确保了高效的查找、插入和删除操作。

---

红黑树的五大性质

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点为黑色：树的根节点始终是黑色。
3. 叶子节点为黑色：所有叶子节点（NIL，哨兵节点）都是黑色。
4. 红色节点不能相邻：红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。
5. 每个节点到其后代叶子的黑色节点数相同：对于任意节点，从该节点到叶子的所有路径上，黑色节点的数量相同，这一性质确保了红黑树的平衡性。

---

红黑树的操作

1. 查找（Search）

查找操作与普通的二叉搜索树相同，根据键值大小递归或迭代寻找目标节点。由于红黑树具有自平衡特性，查找的时间复杂度为 (O(\log n))。

2. 插入（Insertion）

红黑树插入新节点的过程分为两步：

1. 按照普通二叉搜索树的规则插入新节点，初始将新节点设为红色。
2. 根据红黑树的五大性质，对树结构进行修复，确保红黑性质不被破坏。

插入操作可能触发以下三种修复情况：

Case 1：叔节点是红色

如果新节点的父节点和叔节点均为红色：

1. 将父节点和叔节点涂黑。
2. 将祖父节点涂红。
3. 将祖父节点作为新节点，继续向上检查修复。

Case 2：叔节点是黑色，且新节点是右子节点

如果新节点的父节点是红色，叔节点是黑色，且新节点是右子节点：

1. 对父节点进行左旋，将新节点调整到外侧。
2. 转化为 Case 3。

Case 3：叔节点是黑色，且新节点是左子节点

如果新节点的父节点是红色，叔节点是黑色，且新节点是左子节点：

1. 对祖父节点进行右旋。
2. 交换祖父节点和父节点的颜色。

3. 删除（Deletion）

删除操作首先按普通二叉搜索树规则找到目标节点，然后：

1. 如果删除的节点是红色：直接删除。
2. 如果删除的节点是黑色：会破坏黑高平衡，需要进行修复。

删除操作的修复场景包括以下四种：

Case 1：兄弟节点是红色

1. 将兄弟节点涂黑，父节点涂红。
2. 对父节点进行旋转。
3. 转化为其他情况处理。

Case 2：兄弟节点是黑色，且兄弟的两个子节点均为黑色

1. 将兄弟节点涂红。
2. 将父节点作为新节点，向上递归修复。

Case 3：兄弟节点是黑色，兄弟的左子节点是红色，右子节点是黑色

1. 将兄弟节点涂红，兄弟的左子节点涂黑。
2. 对兄弟节点进行右旋。
3. 转化为 Case 4。

Case 4：兄弟节点是黑色，兄弟的右子节点是红色

1. 将兄弟节点的颜色设置为父节点的颜色。
2. 将父节点涂黑，兄弟的右子节点涂黑。
3. 对父节点进行旋转，修复完成。

---

插入操作示例

以插入以下节点序列为例：[7, 3, 18, 10, 22, 8, 11, 26, 2, 6, 13]

初始插入

1. 插入 7：树为空，7 作为根节点，设为黑色。
2. 插入 3：3 小于 7，挂到左侧，设为红色。
3. 插入 18：18 大于 7，挂到右侧，设为红色。

修复插入冲突

4. 插入 10：10 < 18，挂到 18 左侧；10 为红色，与父节点 18 同为红色，触发 Case 1。
   • 祖父节点 7 变红，父节点 18 和叔节点 3 变黑。
   • 根节点 7 重新涂黑。
5. 插入 22：直接插入，无需修复。
6. 插入 8：8 挂到 10 左侧，触发 Case 2 -> Case 3。
   • 左旋父节点 10，将 8 调整为外侧。
   • 右旋祖父节点 18，完成修复。

---

删除操作示例

以删除以下节点为例：[18, 3]

删除 18

1. 删除后，18 的后继节点（或直接替换节点）补位。
2. 如果删除的节点是黑色，触发 Case 1~4 中的修复规则，最终平衡树。

删除 3

1. 删除 3，修复兄弟节点颜色冲突。
2. 如果兄弟节点为黑色，且其子节点为黑色，触发 Case 2。
3. 递归向上调整，直到根节点或不再有冲突。

---

红黑树的实现与优化

1. 工程应用：
   • C++ 的 std::map 和 std::set。
   • Java 的 TreeMap 和 TreeSet。
2. 红黑树 vs AVL 树：
   • AVL 树高度更严格平衡，查询性能稍优。
   • 红黑树插入、删除效率更高，工程中更常用。

---

总结

红黑树的核心是通过“颜色约束”和“旋转”保持平衡，插入与删除的修复逻辑基于几种典型场景（Case 1~4）。虽然实现上需要细心处理，但由于其高效的时间复杂度和广泛的工程应用价值，红黑树是二叉搜索树中非常重要的一种变体。