红黑树定义

通过变色和旋转方式来实现存储过程中自平衡的二叉搜索树。保证最坏搜索情况下时间复杂度为 O(07_红黑树 - 图1 n)。

红黑树的性质

  1. 每个结点为红色或黑色；
  2. 根结点为黑色；
  3. 叶子结点（NIL / NULL）是黑色的；
  4. 不可能有互为父子关系的两个红色结点。
  5. 对每个结点，从该结点到其所有后代叶子结点的简单路径上，均包含相同数目的黑色结点。

红黑树相关特性

  • 一棵有n个内部结点的红黑树，高度**至多为 2 07_红黑树 - 图2 (n - 1)

结构定义

  • 结点结构定义

    • 父指针方便自下而上的查找。实现时候注意父子关系一致性。
    • 红黑状态标记。注意插入情况下构建结点的颜色。
      1. // 红黑树结点结构定义
      2. typedef struct BrTreeNode
      3. {
      4. // 数据域
      5. BrTreeNodeElementType data;
      6. // 左孩子的指针
      7. BrTreeNode* left;
      8. // 右孩子的指针
      9. BrTreeNode* right;
      10. // 父指针
      11. BrTreeNode* parent;
      12. // 红黑状态标记，默认为红色
      13. bool black = false;
      14. }BrNode, * BrTree;

  • 常量定义 ```c /替代所有NULL的结点/ BrTreeNode nil = {NULL, NULL, NULL, NULL, true};

/根结点指针/ BrTree root = &nil;

  2.    - nil ==> 红黑树中**所有Null指向**的替换
  3.       - **未满状态**的结点（包括叶子）
  4.       - **根结点的parent**
  5.    - 根结点 => 所有**存取操作**的**初始**操作元素
  7. > 红黑树的基本操作
  9. ![红黑树_左旋&右旋.svg](https://cdn.nlark.com/yuque/0/2021/svg/21873585/1624244809220-aafe4ea1-681c-425b-bded-202164ceaf5c.svg#align=left&display=inline&height=328&margin=%5Bobject%20Object%5D&name=%E7%BA%A2%E9%BB%91%E6%A0%91_%E5%B7%A6%E6%97%8B%26%E5%8F%B3%E6%97%8B.svg&originHeight=328&originWidth=871&size=18048&status=done&style=none&width=871)
  11. - **变色**：红色和黑色之间的转变，在某些插入或删除条件的发生。
  12. - 左旋：实现自平衡的一种方法。对某个**结点x**，**x的父结点**，**x右子树根y**，y**的左子树根β**之间的操作（当前操作对象为x）。
  13. ```c
  14. /* 02_红黑树_左旋（对某个结点及其右孩子的操作）*/
  15. void leftRotate_BrT(BrTree& root, BrTree x)
  16. {
  17.     // 1. 保存其右孩子
  18.     BrTree y = x->right;
  20.     // 2. x -> y 连接更改，改为y的左孩子
  21.     x->right = y->left;
  22.     if (y->left != &nil)
  23.     {
  24.         y->left->parent = x;
  25.     }
  27.     // 3. x与其父结点关系
  28.     // 无父结点，x即为root
  29.     if (x->parent == &nil)
  30.     {
  31.         root = y;
  32.         y->parent = &nil;
  33.     }
  34.     // 为其左孩子
  35.     else if (x == x->parent->left)
  36.     {
  37.         x->parent->left = y;
  38.         y->parent = x->parent;
  39.     }
  40.     // 为其右孩子
  41.     else
  42.     {
  43.         x->parent->right = y;
  44.         y->parent = x->parent;
  45.     }
  47.     // 4. 调整为 y -> x 的关系，反向
  48.     y->left = x;
  49.     x->parent = y;
  50. }
  • 找到x的右孩子，用指针y保存；
  • x 断开与 y的连接，改为连接y的左孩子（存在互相指向，注意父指针别遗忘）；
  • 指向x的结点，改为指向y（互相指向，别遗忘父指针）；

  • 建立新的x与y之间指向（别遗忘父指针）。

    • 右旋：参考左旋，操作与之对称，与左旋互为逆过程。对某个结点y，y的父结点，y的左子树根x，x的右子树根β之间的操作。 ```c / 03红黑树右旋（对某个结点及其左孩子的操作）/ void rightRotate_BrT(BrTree& root, BrTree y) { // 1. 保存其左孩子 BrTree x = y->left;

    // 2. y -> x的连接更改，改为x的右孩子 y->left = x->right; if (x->right != &nil) { x->right->parent = y; }

    // 3. y与上级指针的关系 // 无父指针，则y为根结点 if (y->parent == &nil) { root = x; x->parent = &nil; } // y为父的左 else if (y == y->parent->left) { y->parent->left = x; x->parent = y->parent; } // y为父的右 else { y->parent->right = x; x->parent = y->parent; }

    // 4. 调整为 x -> y 的关系，反向 x->right = y; y->parent = x; } ```

红黑树的插入元素操作

  • 先按二叉查找树（BST）方式插入元素。

    1. /* 04_红黑树_插入元素（插入完成，根据情况执行保持平衡的基本操作）*/
    2. Status insertElem_BrT(BrTree& root, BrTreeNodeElementType data)
    3. {
    4.   // 1. 根结点为空，直接插入，并返回
    5.   if (root == &nil)
    6.   {
    7.       return buildBrNode_BrT(root, true, data) ? OK : ERROR;
    8.   }
    9.   // 2. 否则构建红色结点，并执行二叉搜索插入
    10.   BrTree toAdd = NULL;
    11.   if (!buildBrNode_BrT(toAdd, false, data))
    12.   {
    13.       return ERROR;
    14.   }
    15.   brSearchAddElem(root, toAdd);
    16.   // 3. 判断红黑特性，决定自平衡操作
    17.   insertFixUp_BrT(root, toAdd);
    18.   return OK;
    19. }

    • 先判断根结点是否为Null。

      1. /* 根据颜色和数据，构建结点*/
      2. Status buildBrNode_BrT(BrTree& brT, bool black, BrTreeNodeElementType data)
      3. {
      4. brT = (BrTree)malloc(sizeof(BrTreeNode));
      5. if (!brT)
      6. {
      7.    printf("构建结点失败！\n");
      8.    return ERROR;
      9. }
      10. // 颜色、数据
      11. brT->black = black;
      12. brT->data = data;
      13. // 处理Null
      14. brT->left = &nil;
      15. brT->right = &nil;
      16. brT->parent = &nil;
      18. return OK;
      19. }
      • 是。
        • 插入即是树根，构建黑色结点。
        • 处理Null位置，退出。
      • 否。构建红色结点。
    • 执行二叉搜索插入。
      1. /* 红黑树基础二叉搜索插入(注意parent指针)*/ 
      2. void brSearchAddElem(BrTree& brT, BrTree& toAdd)
      3. {
      4. // 关键字大小，小于 ==> 左子树
      5. if (toAdd->data < brT->data)
      6. {
      7.    // 为空，连接上，设置父子关系
      8.    if (brT->left == &nil)
      9.    {
      10.        brT->left = toAdd;
      11.        toAdd->parent = brT;
      12.        return;
      13.    }
      14.    // 递归其左子树
      15.    else
      16.    {
      17.        brSearchAddElem(brT->left, toAdd);
      18.    }
      19. }
      20. // 大于等于 ==> 右子树
      21. else
      22. {
      23.    if (brT->right == &nil)
      24.    {
      25.        brT->right = toAdd;
      26.        toAdd->parent = brT;
      27.        return;
      28.    }
      29.    // 递归其右子树
      30.    else
      31.    {
      32.        brSearchAddElem(brT->right, toAdd);
      33.    }
      34. }
      35. }

  • 检查红黑特性满足条件，决策执行自平衡操作。

    • 父亲为黑色，不影响平衡，不操作。
    • 父亲为红色 ==> 一定有黑色的祖父结点。
      • 叔叔为红色。
        红黑树_插入_父为红_叔叔为红.svg
        1. 父亲和叔叔变黑色；
        2. 爷爷变红色；
        3. 当前结点置为爷爷，继续检查。
      • 叔叔为黑色（包括Null）
        • 祖父、父亲、孩子同向（同左边或同右边）
          1. 祖父、父亲变色；
          2. 祖父旋转（同左 ==> 右转，同右 ==> 左转）
        • 祖父、父亲、孩子不同向
          1. 对父亲旋转，使得三代同向。
          2. 按同向逻辑变色和旋转。
            红黑树_插入_父为红_叔叔为黑.svg
  • 红黑树插入自平衡代码
    1. /* 10_红黑树_插入自平衡处理*/
    2. void insertFixUp_BrT(BrTree& root, BrTree cur)
    3. {
    4.   // 父亲红色时候，才需要进行平衡
    5.   while (!cur->parent->black)
    6.   {
    7.       // 叔叔结点
    8.       BrTree uncle;
    9.       // 父亲是祖父左孩子
    10.       if (cur->parent == cur->parent->parent->left)
    11.       {
    12.           // 叔叔（祖父右孩子）
    13.           uncle = cur->parent->parent->right;
    14.           // 1. 父代均为红色，仅变色
    15.           if (!uncle->black)
    16.           {
    17.               cur->parent->black = true;
    18.               uncle->black = true;
    19.               cur->parent->parent->black = false;
    20.               cur = cur->parent->parent;
    21.               // 为红色需重新进入判断
    22.               continue;
    23.           }
    24.           // 2. 叔叔黑，父亲红
    25.           // 2.1 当前为父亲的右孩子
    26.           else if (cur == cur->parent->right)
    27.           {
    28.               cur = cur->parent;
    29.               leftRotate_BrT(root, cur);
    30.           }
    31.           // 2.2 当前为父亲左孩子
    32.           cur->parent->black = true;
    33.           cur->parent->parent->black = false;
    34.           rightRotate_BrT(root, cur->parent->parent);
    35.       }
    36.       // 父亲是祖父右孩子
    37.       else
    38.       {
    39.           // 叔叔（祖父左孩子）
    40.           uncle = cur->parent->parent->left;
    41.           // 1. 父代均为红色，仅变色
    42.           if (!uncle->black)
    43.           {
    44.               cur->parent->black = true;
    45.               uncle->black = true;
    46.               cur->parent->parent->black = false;
    47.               cur = cur->parent->parent;
    48.               continue;
    49.           }
    50.           // 2. 叔叔黑，父亲红
    51.           // 2.1 当前为父亲的左孩子
    52.           else if (cur == cur->parent->left)
    53.           {
    54.               cur = cur->parent;
    55.               rightRotate_BrT(root, cur);
    56.           }
    57.           // 2.2 当前为父亲右孩子
    58.           cur->parent->black = true;
    59.           cur->parent->parent->black = false;
    60.           leftRotate_BrT(root, cur->parent->parent);
    61.       }
    62.   }
    63.   root->black = true;
    64. }

红黑树的删除元素操作

先按二叉查找树（BST）方式删除元素（参考BST删除元素）。 结点定义

  • Z ==> 待删除结点
  • X ==> 自平衡起始的结点（替代结点）
  • Y ==> 按z的孩子数
    • 为2时候：y作为z的后继
    • 小于2个，y用于保存z的颜色
  • 元素没有左孩子，用右其孩子替换（不论右孩子是否为空）。
  • 没有右孩子，用其左孩子替换（不论左孩子是否为空）。
    红黑树_删除_待删除结点孩子数小于2.svg
  • 有两个孩子。需要找其前驱或后继（这里找其后继）。
    • 右孩子无左子树，则后继==> 右孩子。
    • 右孩子有左子树，后继 ==> 左子树最左的元素。
      红黑树_删除_待删除结点有两个孩子.svg

检查红黑特性满足条件，决策执行自平衡操作。

  1. 自平衡情况是左右对称的，只需讨论一边的情况，另一边镜像即可。
  2. 总体思路：先讨论替代节点的红黑情况，再讨论
  • 自平衡的结点定义
    红黑树_删除自平衡_结点定义.svg
  • 删除自平衡操作。
    1. 替代结点X 为红色 ==> 变黑即可
      红黑树_删除自平衡_替代为红.svg
      • 根据红黑性质【不能有两个连续的红色结点】，推导出【真正删除的结点为黑色】，而父亲的颜色不确定
      • 当前①②所在分支少了一个黑结点，黑平衡被破坏，将当前红结点变黑即可解决。
    2. 替代结点X为黑色
      1. 兄弟S为红色 ==> 父亲P，左侄子SL，右侄子SR一定为黑色
        红黑树_删除自平衡_替代为黑兄弟为红.svg
        • 兄弟S，父亲P互换颜色；
        • 对P旋转，更新旋转后的兄弟指针指向（图中的SL）。
        • 此时所有路径黑结点数未受影响。经过路径①②的黑结点，仍然比其他路径少1个。但情况以转变为如下【兄弟S为黑色】
      2. 兄弟S为黑色
        1. 兄弟的左右孩子（SL和SR）均为黑色
          红黑树_删除自平衡_替代为黑，兄弟为黑.svg
          1. 父亲P为黑色
          2. 父亲P为红色
        2. 兄弟的孩子（SL与SR）中存在红色，父亲（P）均可。
          红黑树_删除自平衡_替代为黑_兄弟为黑_兄弟的孩子存在红色.svg
          1. 左孩子SL为红色，SR为黑色。
          2. SR为红色，SL可红可黑。