红黑树

红黑树介绍

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，在插入和删除操作时通过特定的规则保持树的平衡，从而保证高效的查找、插入和删除操作。其时间复杂度通常为 ( O(\log n) )，适用于需要频繁动态更新的场景。

红黑树的性质

红黑树在普通二叉搜索树（BST）的基础上增加了颜色属性（红或黑），并通过以下五条性质保持平衡：

1. 节点颜色：每个节点要么是红色，要么是黑色。
2. 根节点：根节点始终是黑色。
3. 红色节点约束：红色节点的子节点必须是黑色（即红色节点不能连续）。
4. 黑色路径等价：从根节点到每个叶子节点（或 NULL 节点）的路径上，黑色节点数量相同（称为黑色高度）。
5. 叶子节点：所有叶子节点（通常是 NULL 节点）视为黑色。

这些性质确保红黑树的高度不会超过 ( 2 \log (n+1) )，从而保证高效的操作。

红黑树的操作

1. 查找：

   • 与普通二叉搜索树相同，根据键值比较沿树向下搜索，时间复杂度为 ( O(\log n) )。

2. 插入：

   • 新节点插入时默认标记为红色（以最小化对黑色高度的影响）。
   • 插入后可能违反性质（如红色节点连续），需要通过旋转和重新着色修复：
     • 旋转：分为左旋和右旋，调整子树结构以恢复平衡。
     • 重新着色：调整节点的颜色以满足红黑树性质。
   • 修复场景包括：父节点为红色时的几种情况（取决于叔节点、父节点和祖父节点的颜色与位置）。
   • 时间复杂度：( O(\log n) )。

3. 删除：

   • 删除节点后可能破坏黑色高度或颜色约束，需通过旋转和重新着色修复。
   • 删除操作比插入复杂，涉及“双黑”节点（黑色节点被删除后路径黑色高度减少）处理。
   • 时间复杂度：( O(\log n) )。

红黑树的优点

• 高效性：通过自平衡机制，查找、插入、删除操作的时间复杂度均为 ( O(\log n) )。
• 稳定性：相比 AVL 树，红黑树在插入和删除时旋转次数较少，适合频繁更新的场景。
• 广泛应用：常用于实现关联容器（如 C++ 的 std::map 和 std::set）、内存管理、数据库索引等。

红黑树与 AVL 树的对比

• AVL 树：严格平衡（左右子树高度差不超过 1），查找更快，但插入/删除需要更多旋转。
• 红黑树：较宽松的平衡（通过颜色和黑色高度约束），插入/删除效率更高，适合动态更新场景。

示例

假设插入序列为 {7, 3, 18, 10, 22, 8, 11, 26}，红黑树可能如下（简化表示）：

   7(B)
  /   \
3(R)  18(B)
     /  \
   10(R) 22(R)
   /       \
  8(B)    26(B)
          /
        11(R)

（B 表示黑色，R 表示红色）