红黑树

                                12(B)
                              /        \
                           6(R)          16(R)
                          /    \        /      \
                       2(B)   10(B)   14(B)    20(B)
                      /  \    /  \    /  \     /    \
                   NIL   5(R) NIL NIL NIL NIL 19(R) 25(R)
                        /  \                 /  \   /  \
                      NIL  NIL             NIL NIL NIL NIL

红黑树性质

红黑树本质上是一棵二叉排序树，除了具有二叉排序树所具备的特性外，还具有其他一些特性，下面对红黑树的性质做个总结：

1. 结点颜色是红色或黑色。
2. 根结点是黑色。
3. 所有叶子都是黑色[这里的叶子结点不保存数据信息，只保存颜色信息（黑色），标记为 NIL 结点]。
4. 每个红色结点必须有两个黑色的子结点（从每个叶子到根的所有路径上不能有两个连续的红色结点）。
5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。

性质 4) 和 5) 使得红黑树有了一个关键特性：从根到叶子的最长的可能路径不多于最短的可能路径的两倍。性质 4) 使得路径中不能有两个连续的红色结点，最短的可能路径中全是黑色结点，最长的可能路径中有交替的红色和黑色结点。性质 5) 规定所有结点到其每个叶子结点的所有简单路径都包含相同数目的黑色结点，这就表明了没有路径能多于任何其他路径的两倍。因此红黑树在结构上是一棵大致平衡的二叉排序树，具有很高的查找效率。一般含有 n 个结点的红黑树的高度至多为 2log(n+1)，红黑树上的查找时间复杂度为 O(logn)。

红黑树是一个附加了一些约束的二叉排序树，因此红黑树上的只读操作（查找）与普通的二叉查找树的只读操作相同。然而，在红黑树上进行插入和删除操作可能会导致其不再符合红黑树的特性，因此树在插入、删除结点之后可能需要一些调整操作使之恢复特性。恢复红黑树的特性需要少量的颜色变更[时间复杂度为 O(logn)]和不超过三次的旋转操作（需要两次插入操作）。插入和删除操作的总时间复杂度为 O(logn)。

三、红黑树的操作

（一）旋转操作

旋转是红黑树调整的核心操作，包含左旋转和右旋转两种，均能保持二叉排序树特性。

1. 左旋转：对结点A进行左旋转后，A变成原本其右孩子B的左孩子，需注意原本的X、Y、Z结点在调整后的位置。

旋转前：
                A(B)
               /      \
            X(B)      B(B)
                     /      \
                  Y(B)      Z(B)

旋转后：
                B(B)
               /      \
            A(B)      Z(B)
           /      \
        X(B)      Y(B)

1. 右旋转：对结点B进行右旋转后，B变成原本其左孩子A的右孩子，需注意原本的X、Y、Z结点在调整后的位置。

旋转前：
                B(B)
               /      \
            A(B)      Z(B)
           /      \
        X(B)      Y(B)

旋转后：
                A(B)
               /      \
            X(B)      B(B)
                     /      \
                  Y(B)      Z(B)

1. 特性：左旋转和右旋转是完全对称或相逆的操作。

左旋 ←→ 右旋（逆操作）：
                A(B)               B(B)               A(B)
               /      \           /      \           /      \
            X(B)      B(B)     A(B)      Z(B)     X(B)      B(B)
                     /      \  /      \                /      \
                  Y(B)      Z(B)      Y(B)          Y(B)      Z(B)

（二）结点插入

红黑树的插入操作基于二叉排序树插入规则，插入后需通过调整恢复红黑树特性，步骤如下：

1. 插入初始化：新插入结点初始化为红色（避免破坏特性5），按二叉排序树规则插入到合适位置，并为其挂上黑色NIL叶子结点。

插入前：
                10(R)
               /      \
            NIL(B)   NIL(B)

插入后：
                10(R)
               /      \
            NIL(B)   11(R)
                     /      \
                  NIL(B)   NIL(B)

1. 调整目标：插入后仅可能破坏特性4（出现连续红色结点），需通过着色和旋转恢复。

2. 调整场景及处理方法：

   • 场景1：被插入的结点是根结点→直接涂为黑色。
   • 场景2：被插入的结点的父结点是黑色结点→无需调整。
   • 场景3：被插入的结点的父结点为红色（此时存在祖父结点和叔叔结点），分3种情形：
     • 情形1：叔叔结点是红色→将父结点、叔叔结点涂为黑色，祖父结点涂为红色；将祖父结点设为当前结点，继续按上述规则处理。
     • 情形2：叔叔结点是黑色且当前结点是右孩子→将父结点作为新的当前结点，以其为支点进行左旋转。
     • 情形3：叔叔结点是黑色且当前结点是左孩子→将父结点涂为黑色，祖父结点涂为红色，以祖父结点为支点进行右旋转。

示例流程：插入结点6后，依次触发情形1、情形2、情形3调整，最终恢复红黑树特性。

初始红黑树（插入结点6前）

                                12(B)
                              /        \
                           4(R)          16(B)
                          /    \        /      \
                       2(B)    8(B)   NIL(B)   20(R)
                      /  \    /  \              /    \
                   NIL  NIL 5(R) 11(R)       NIL    NIL
                           / \   / \
                         NIL NIL NIL NIL

插入结点6后

                              12(B)
                             /        \
                          4(R)          16(B)
                         /    \        /      \
                      2(B)    8(B)   NIL(B)   20(R)
                     /  \    /  \              /    \
             NIL(B)  NIL(B) 5(R) 11(R)        NIL(B) NIL(B)
                            / \
                        NIL(B) 6(R)
                                / \
                            NIL(B) NIL(B)

按情形1调整后

                                12(B)
                              /        \
                           4(R)          16(B)
                          /    \        /      \
                       2(B)    8(R)   NIL(B)   20(R)
                      /  \    /  \              /    \
               NIL(B) NIL(B) 5(B) 11(B)     NIL(B) NIL(B)
                              / \
                          NIL(B) 6(R)
                                 / \
                             NIL(B) NIL(B)

按情形2调整后（左旋转）

                                12(B)
                              /        \
                           8(R)          16(B)
                          /    \        /      \
                       4(B)    11(B) NIL(B)   20(R)
                      /  \                    /    \
                   2(B)  5(B)             NIL(B) NIL(B)
                         / \
                    NIL(B) 6(R)
                          / \
                       NIL(B) NIL(B)

按情形3调整后（右旋转）

                                8(B)
                              /        \
                           4(R)          12(R)
                          /    \        /      \
                       2(B)    5(B)   NIL(B)  16(B)
                              / \              /    \
                         NIL(B) 6(R)      NIL(B)  20(R)
                                 / \              / \
                             NIL(B) NIL(B)  NIL(B) NIL(B)

（三）结点删除

红黑树的删除操作基于二叉排序树删除规则，删除后需通过调整恢复红黑树特性，核心逻辑如下：

1. 删除影响：删除后可能破坏特性2（根结点颜色）、特性4（连续红色结点）、特性5（黑色结点数）。
2. 调整前提：假设顶替被删结点的结点为x，x继承被删结点的黑色（被删结点必为黑色，否则不破坏特性），x颜色变为“红+黑”或“黑+黑”，以此保证特性5不被破坏。
3. 调整场景及处理方法：
   • 场景1：x颜色为“红+黑”→删除红色，保留黑色，特性恢复。
   • 场景2：x颜色为“黑+黑”且x是根结点→无需调整。
   • 场景3：x颜色为“黑+黑”且x不是根结点，分4种情形：
     • 情形1：x的兄弟结点是黑色，且兄弟结点的两个孩子都是黑色→将兄弟结点涂为红色；设父结点为新x，若新x是红色则涂为黑色，否则继续处理。
     • 情形2：x的兄弟结点为红色→将兄弟结点涂为黑色，父结点涂为红色；x是左孩子则对父结点左旋转，x是右孩子则右旋转，继续处理新x。
     • 情形3：x的兄弟结点是黑色，兄弟结点的左孩子是红色、右孩子是黑色→将兄弟结点的左孩子涂为黑色，兄弟结点涂为红色；对兄弟结点右旋，继续处理。
     • 情形4：x的兄弟结点是黑色，兄弟结点的右孩子是红色（左孩子颜色任意）→将父结点颜色赋值给兄弟结点，父结点涂为黑色，兄弟结点的右孩子涂为黑色；x是左孩子则对父结点左旋转，x是右孩子则右旋转，继续处理。

示例流程：分别展示4种情形的涂色、旋转调整过程，最终恢复红黑树特性。

情形1的操作过程（x的兄弟为黑色且子结点均黑）

调整前：
                12(B)
               /      \
          x(B+B)        9(B)
          /      \      /    \
        NIL(B)  NIL(B) NIL(B) NIL(B)

调整后：
                12(B)  （新x，涂为黑色）
               /      \
          x(B)          9(R)
          /      \      /    \
        NIL(B)  NIL(B) NIL(B) NIL(B)

情形2的操作过程（x的兄弟为红色）

调整前：
                16(B)
               /      \
          x(B+B)      20(R)
          /      \      /      \
        NIL(B)  NIL(B) NIL(B)  18(B)
                                /    \
                              NIL(B) NIL(B)

涂色调整后（情形2第一步）

                16(R)
               /      \
          x(B+B)      20(B)
          /      \      /    \
        NIL(B)  NIL(B) NIL(B) 18(B)
                                /   \
                              NIL(B) NIL(B)

左旋转调整后（情形2第二步）

                20(B)
               /      \
            16(R)      18(B)
           /      \      /   \
        x(B+B)  NIL(B) NIL(B)  NIL(B)
        /      \
      NIL(B)  NIL(B)

情形3的操作过程（兄弟为黑，左孩子红、右孩子黑）

调整前：
                父(B)
               /      \
          x(B+B)      20(B)
          /      \      /   \
        NIL(B)  NIL(B)红孩子(R) NIL(B)
                      /      \
                    NIL(B)  NIL(B)

涂色调整后（情形3第一步）

                父(B)
               /      \
          x(B+B)      20(R)
          /      \      /    \
        NIL(B)  NIL(B)红孩子(B) NIL(B)
                      /      \
                    NIL(B)  NIL(B)

右旋转调整后（情形3第二步）

                父(B)
               /      \
          x(B+B)      红孩子(B)
          /      \      /      \
        NIL(B)  NIL(B) NIL(B)  20(R)
                                /   \
                              NIL(B) NIL(B)

情形4的操作过程（兄弟为黑，右孩子红）

调整前：
                父(B)
               /      \
          x(B+B)      16(B)
          /      \      /    \
        NIL(B)  NIL(B) NIL(B) 20(R)
                                /   \
                              NIL(B)  NIL(B)

涂色调整后（情形4第一步）

                父(B)
               /      \
          x(B+B)      16(B)  （继承父颜色）
          /      \      /    \
        NIL(B)  NIL(B) NIL(B) 20(B)
                              /      \
                              NIL(B)  NIL(B)

左旋转调整后（情形4第二步）

                16(B)
               /      \
            父(B)      20(B)
           /      \      /    \
        x(B)      NIL(B) NIL(B)  NIL(B)
        /      \
      NIL(B)  NIL(B)

1. 下列关于红黑树的说法中，正确的是（）。

选项：

A. 红黑树的红结点的数目最多和黑结点的数目相同

B. 若红黑树的所有结点都是黑色的，则它一定是一棵满二叉树

C. 红黑树的任何一个分支结点都有两个非空孩子结点

D. 红黑树的子树也一定是红黑树

解析：

• A：✔ 正确
  红黑树中不存在两个连续的红结点，且根结点为黑色，因此红结点最多与黑结点数目相同。

• B：✘ 错误
  即使所有结点均为黑色，只要从根到各叶子路径上的黑结点数相同即可，并不要求是满二叉树。

• C：✘ 错误
  红黑树允许存在 NIL 叶子结点（空结点，视为黑），因此内部结点不一定有两个非空孩子。

• D：✘ 错误
  子树的根结点可能是红色，且从该子树根到叶子的黑结点数未必满足红黑树的定义。

正确答案：A

2. 下列四个选项中，满足红黑树定义的是（）。

注：黑色结点为 实心，红色结点为 空心

选项示意图（示例）：

A：

    ●
   /
  ○

（路径黑结点数不一致）

B：

    ○
   / \
  ●   ●

（根结点为红色，违反性质）

C：

    ●
   /
  ○
 /
○

（存在连续红结点）

D：

      ●
     / \
    ○   ○
   /     \
  ●       ●

解析：

红黑树需满足：

1. 根结点为黑
2. 不存在连续的红结点
3. 从任一结点到其所有叶子（NIL）路径上的黑结点数相同
4. NIL 结点为黑

• 选项 D：
  ✔ 根为黑
  ✔ 无连续红结点
  ✔ 所有路径黑结点数一致

正确答案：D

3. 将关键字 1,2,3,4,5,6,7 依次插入初始为空的红黑树 (T)，则 (T) 中红结点的个数是（）。

解析：

按照红黑树插入规则：

• 新插入结点初始为红
• 通过旋转与变色维持性质

最终形成近似完全平衡结构：

        ●4
      /     \
    ○2       ○6
   /  \     /  \
 ●1  ●3  ●5  ●7

红结点为：2、6 的孩子结点在调整后，最终红结点为 2、4、6 → 共 3 个

正确答案：3

4. 将关键字 5,4,3,2,1 依次插入初始为空的红黑树 (T)，则 (T) 的最终形态是（）。

插入过程简述：

1. 插入 5 → 黑根
2. 插入 4 → 红
3. 插入 3 → 触发调整（旋转 + 变色）
4. 插入 2 → 红
5. 插入 1 → 再次调整

最终树形：

        ●3
      /     \
    ○2       ○4
   /           \
 ●1             ●5

• 根为黑
• 无连续红结点
• 黑高一致

5. 在下图所示的红黑树中插入结点 2 且染成红色后，则下一步应进行的操作是（）。

原始红黑树：

        ●5
       /
     ○3

插入结点 2（红）后：

        ●5
       /
     ○3
     /
   ○2

分析：

• 当前结点 2 为红
• 父结点 3 为红 → 违反“不能有连续红结点”
• 叔叔结点为 NIL（黑）

此时属于 “父红、叔黑、左左型”，修复步骤为：

1. 先变色（父变黑，祖父变红）
2. 再进行右旋

题目问的是：下一步操作

正确答案：（变色）