算法基础 -- 红黑树初识

红黑树初识

红黑树（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。
    
  
  
• 红黑树 vs AVL 树：
  
  
  
  • AVL 树高度更严格平衡，查询性能稍优。
    
  • 红黑树插入、删除效率更高，工程中更常用。
    
  
  

---

总结

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。