数据结构

红黑树（Red-Black Tree）是一种自平衡二叉搜索树，通过在每个节点上维护一个颜色属性（红色或黑色），并满足一系列约束条件来保持树的平衡。红黑树在插入、删除和查找操作中都能保证时间复杂度为 O(log n)，使其成为广泛应用的数据结构之一。下面详细介绍红黑树的特点、约束条件以及实现方法。

1. 红黑树的基本特点

  • 颜色属性：

    • 每个节点要么是红色，要么是黑色。

  • 根节点和叶子节点（NIL） ：

    • 根节点始终是黑色。
    • 所有的NIL节点（空节点或叶节点的子节点）都是黑色。

  • 红节点的子节点：

    • 红色节点的所有子节点必须是黑色。也就是说，红色节点不能有红色子节点（不会出现“红红相连”的情况）。

  • 从任一节点到其所有叶子节点的简单路径：

    • 所有从任意节点 ( x ) 到其所有叶子节点（NIL节点）的简单路径上，都包含相同数目的黑色节点。这个数目被称为该节点的黑色高度或黑色平衡因子。

2. 红黑树的约束条件

  1. 每个节点要么是红的，要么是黑的。

    • node.color = RED || BLACK

  2. 根节点是黑的。

    • root.color = BLACK

  3. 所有的NIL节点（叶子节点）是黑的。

    • NIL.color = BLACK

  4. 如果一个节点是红的，那么它的两个子节点都是黑的。

    • 如果 node.color = RED，则 node.left.color = BLACK 且 node.right.color = BLACK

  5. 从任一节点到其所有叶子（NIL节点）的简单路径上，都包含相同数目的黑色节点。

    • 这个数目被称为黑色平衡因子。

3. 红黑树的操作

红黑树在插入和删除操作中会通过旋转和重新着色来保持平衡。以下是主要操作：

插入操作

  1. 插入新节点为红色：

    • 新插入的节点总是被涂成红色，以避免违反红黑树的性质。

  2. 调整颜色和进行旋转：

    • 如果父节点是黑色，则插入操作完成。

    • 如果父节点是红色，则需要通过旋转和重新着色来修复平衡。主要的调整规则包括：

      • 左旋（Left Rotation） ：
          |         |
    x         y
   / \       / \
  a   y    x   c
     / \  / \
    b   c a   b
      • 右旋（Right Rotation） ：
          |         |
    y         x
   / \       / \
  x   c    a   y
 / \         / \
a   b        b   c

      • 重新着色：

      • 如果插入节点的叔叔节点是红色，则需要将父节点和叔叔节点涂成黑色，祖父节点涂成红色，并对祖父节点进行递归调整。

      • 如果叔叔节点是黑色或不存在（NIL），则需要通过左旋、右旋和重新着色来调整。

删除操作

  1. 删除节点：

    • 如果被删除的节点有两个子节点，则找到其后继节点（中序遍历的下一个节点），用后继节点替换要删除的节点，然后删除后继节点。

  2. 调整颜色和进行旋转：

    • 删除后的树可能会失去平衡。通过旋转和重新着色来恢复红黑树的性质。
    • 具体调整规则类似于插入操作，包括左旋、右旋和重新着色。

4. 红黑树的优点

  • 平衡性好：高度保持在O(\log n)，保证了基本操作的时间复杂度为 O(\log n) 。

  • 实现简单：虽然红黑树的调整规则相对复杂，但其实现相对稳定且易于理解。

5. 红黑树的缺点

  • 实现复杂：需要处理多种情况下的旋转和重新着色操作，增加了代码的复杂性。
  • 内存消耗：每个节点多了一个颜色属性，可能会增加一定的内存开销。

6. 示例

假设我们要在红黑树中插入以下值：

10, 20, 30, 40, 50

初始状态为空树。插入过程如下：

  1. 插入 10：

    • 新节点总是红色 
      10 (RED)

  2. 插入 20：

    • 父节点 10 是红色，需要进行调整。

        10 (BLACK)
 /
20 (RED)

  3. 插入 30：

    • 父节点 20 是红色，需要进行调整。由于叔叔节点是NIL（黑色），进行左旋和重新着色。
        20 (BLACK)
   / \
10 (RED) 30 (RED)

  4. 插入 40：

    • 父节点 30 是红色，需要进行调整。由于叔叔节点是NIL（黑色），进行左旋和重新着色。
          20 (BLACK)
     / \
   10 (RED) 30 (BLACK)
              \
             40 (RED)

  5. 插入 50：

    • 父节点 40 是红色，需要进行调整。由于叔叔节点是NIL（黑色），进行左旋和重新着色。

        20 (BLACK)
 / \
10 (RED) 30 (BLACK)
          \
         40 (BLACK)
            \
           50 (RED)

发表评论