关于红黑树:数据结构中红黑树的详细介绍

5次阅读

共计 12924 个字符，预计需要花费 33 分钟才能阅读完成。

树

  • 树:

    • 数据结构中是以二叉堆的模式呈现的
    • 如果从链表的观点登程, 相当于是放宽了有序的的要求
    • 容许两个不同地位的元素有相等的序

  • 对于序为 n 的节点来说, 能够指向多个序为 n + 1 的节点:

    • 相应的后者称为前者的孩子
    • 前者称为后者的父节点
    • 最大的序即为树的高度
  • 0 节点的左右两个节点别离为 0 节点的左子节点和右子节点
  • 0 节点也是这两个子节点的父节点
  • 在一个树中, 只有 0 节点没有父节点. 这个节点叫做根节点

二叉搜寻树

  • 二叉搜寻树:

    • 父节点大于或者等于左子节点及所有子节点
    • 父节点小于或者等于右子节点及所有子节点

初始化

  • 要在二叉搜寻树中查问任意一个值:

    • 最坏的状况就是查问到最上面的节点

    • 进行比拟的次数为树的高度

      • 因为这是二叉树, 若树的元素个数为 n, 则现实状况下树的高度不大于 log~2~n
  • 二叉搜寻树中, 每个父节点最多子节点有两个子节点

  • 树中任意节点有三个指针: 别离指向父节点, 左子节点和右子节点. 其中根节点没有父节点

    typedef struct TREENODE
{
  struct TREENODE *father;
  struct TREENODE *left;
  struct TREENODE *right;
  int value;
}tNode;

  • 在一个二叉搜寻树中, 插入新节点:

    • 比拟新节点与以后节点的值
    • 如果大于以后节点, 则比拟新节点与以后节点右子节点的值
    • 如果小于以后节点, 则比拟新节点与以后左子节点的值

    • 如果下一个将要比拟的节点不存在, 就将新节点插入进来

      void insertNode(tNode* root, int val) {tNode* new = (tNode*)malloc(sizeof(tNode));
new -> value = val;
new -> left = NULL;
new -> right = NULL;
while (true) {if (root -> value < val)
        if (root -> right != NULL)
            root = root -> right;
        else {
            // 右子节点不存在, 则新节点成为右子节点
            new -> father = root;
            root -> right = new;
            return;        // 实现赋值之后函数完结
        }
    else 
        if (root -> !=NULL)
            root = root -> left
        else {
            new -> father = root;
            root -> left = new;
            return;
        }
}
}

  • 生成二叉搜寻树之后, 能够将二叉搜寻树打印进去, 查看生成的二叉搜寻树是否正确

    // 打印二叉搜寻树, 输出的值为节点和节点序
void printBST(tNode* root, int start) {printf("the %dth node is %d\n",start, root -> value);
  // 如果以后节点有子节点, 则持续打印这个子节点和节点序
  if (root -> left != NULL) 
      printBST(root -> left, start + 1);
  if (root -> right) 
      printBST(root -> right, start + 1)
}

  • main 主函数:

    int main() {
  tNode* root;
  root -> left = NULL;
  root -> right = NULL;
  root -> value = 10;

  int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
  for (int i = 0; i < 10; i ++)
      inserNode(root, init[i]);

  printBST(root, 0);
  return 0; 
}

  • 生成的二叉搜寻树合乎二叉搜寻树的规定, 接下来为二叉搜寻树增加搜寻节点和删除节点的性能

查找节点

  • 搜寻节点:

    • 搜寻节点和插入性能相似, 然而不须要反复插入, 只须要将这个值的指针返回

      // 通过节点的值搜寻节点的地位, 其中 root 为根节点
tNode* searchBST(tNode* root, int val) {while (root -> value != val) {if (root -> value < val && root -> right != NULL)
        root = root -> right;
    else if (root -> value > val && root -> left != NULL)
        root = root -> left;
    else
        return FALSE;
}
return root;
}

删除节点

  • 删除节点会波及到父节点, 左子节点, 右子节点以及兄弟节点之间的大小关系

  • 如果被删除的节点没有子节点:

    • 只须要将节点的父节点指向被删除节点的指针设置为 NULL 即可

  • 如果被删除的节点只有一个子节点:

    • 只须要指向被删除节点的指针指向这个子节点即可

  • 如果被删除的节点有两个子节点:

    • 因为父节点必须大于左子节点而小于右子节点
    • 所以取代被删除节点的能够是左子节点, 也能够是右子节点
    • 如果是右子节点取代该节点, 则左子节点为新父节点的左子节点
    • 如果是左子节点取代父节点, 则右子节点为新父节点的右子节点
  • 二者选其一, 替换以后节点与这个节点的右子节点, 而后删除替换后的右子节点即可

  • 如果替换后的右子节点依然有两个子节点, 则持续替换, 直到删除为止

    // 删除节点的值,root 为根节点,delNode 为待删除节点
void deleteNode(tNode* delNode) {if (delNode -> left == NULL && delNode -> right == NULL) {if (delNode -> value > pNode -> value)
          pNode -> right = NULL;
      else
          pNode -> left = NULL;
  }
  else if (delNode -> left == NULL && delNode -> right == NULL) {
      int val = delNode -> value;
      // 替换以后节点与右子节点的值
      delNode -> value = delNode -> right -> value;
      delNode -> right -> value = val;
      deleteNode(delNode -> right);    // 删除右节点
  }
  else {tNode* pNode = (delNode -> left == NULL) ? delNode -> right : delNode ->left;
      delNode -> value = pNode -> value;
      delNode -> right = pNode -> right;
      delNode -> left = pNode -> left;
  }
}

  • main 主函数

    int main() {
  tNode* root;
  root -> left = NULL;
  root -> right = NULL;
  root -> value = 10;
  int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
  for (int i = 0; i < 10; i++)
      insertNode(root, init[i]);
  tNode* sNode = searchBST(root, 5);
  deleteNode(sNode);
  printBST(root, 0);
  return 0;
}

旋转节点

  • 二叉搜寻树问题:

    • 如果初始化时, 输出的为顺次递增的值
    • 二叉搜寻树可能并不会产生分叉
    • 径直变成一个只有右子节点的列表
  • 二叉搜寻树的复杂度是和树的高度成正比的, 所以须要管制二叉搜寻树的高度, 使得横向散布平均, 就可能无效进步二叉搜寻树的性能

  • 最直观的做法就是旋转节点:

    • 左旋: 将某个节点旋转为该节点的右孩子的左孩子

    • 右旋: 将某个节点旋转为该节点的左孩子的右孩子

      假如 y 是 x 的右子节点, 而 x 的左子结点很少,y 的右子节点很多, 如果把 y 的子节点过继给 x, 或者取代 x, 逆转父子关系, 就能够使得整个树变得平均

  • 对于 x, xL, y, yL, yR 五个节点:

    • xL, y是 x 的左右节点
    • yL, yR是 y 的左右节点
    • 这些节点之间存在关系: xL <= x <= yL <= y <= yR
    • 如果心愿 y 变成 x 的父节点, 那么 x 必为 y 的左子节点
    • 此时 y 多出一个节点, 必须过继给x

    • 因为 x <= y, 只能过继左子节点yL


      这个过程没有扭转二叉搜寻树的性质, 然而在 yR 长于 yL 的状况下, 可能无效升高树的高度

      • x, y 的转置过程和旋转相似, 这个操作称之为旋转
      • 父节点变成子节点的左子节点叫做左旋, 这样的逆过程叫做右旋

  • 旋转节点算法的实现:

    • 不须要思考xL, yR
    • 须要思考 x 父节点指针的变动

  • 传统旋转节点的实现形式:

    #define RIGHT 1
#define LEFT 0

// 二叉树的传统旋转节点操作
// flag 为 LEFT 时为左旋,flag 为 RIGHT 时为右旋
void rotNode(tNode* xNode, int flag) {
  tNode* yNode;
  if (flag == LEFT) {
      yNode == xNode -> right;
      xNode -> father -> right = yNode;    // y 成为 x 父节点的右子节点
  } else {
      yNode == xNode -> left;
      xNode -> father -> left = yNode;     
  }    

  yNode -> father = xNode -> father;        // x 的父节点成为 y 的父节点
  xNode -> father = yNode;                // y 成为 x 的父节点

  if (flag == LEFT) {
      yNode -> left -> father = xNode;    // y 的左子节点成为 x 的子节点
      xNode -> right = yNode -> left;
      yNode -> left = xNode;
  } else {
      yNode -> right -> father = xNode;
      xNode -> left = yNode -> right;
      yNode -> right = xNode;
  }
  
}

  • main 主函数

    int main() {
  tNode* root;
  root -> left = NULL;
  root -> right = NULL;
  root -> value = 10;
  int init[10] = {1, 11, 5, 12, 2, 4, 19, 11, 8, 7}
  for (int i = 0; i < 10; i++)
      insertNode(root, init[i]);
  tNode* sNode = searchBST(root, 5);
  rotNode(sNode, LEFT);
  printBST(root, 0);
  return 0;
}

  • 从代码角度来说, 替换意义上的旋转操作能够更加简洁, 而且更易于了解

    // 替换意义上的旋转操作,sNode 为子节点,pNode 为父节点
void turnNode(tNode *sNode, tNode* pNode) {if (sNode == pNode -> right) {
      sNode -> left -> father = pNode;
      pNode -> right = sNode ->left;
      sNode -> left = pNode;
  } else {
      sNode -> right -> father = pNode;
      pNode -> left = sNode -> right;
      sNode -> right = pNode;
  }

  sNode -> father = pNode -> father;
  pNode -> father = sNode;
}

红黑树

  • 红黑树具备良好的效率, 能够在 $O(logN)$ 工夫内实现查找, 减少, 删除操作
  • Java中的 TreeMap, HashMap 都是基于红黑树的数据结构实现的

  • 红黑树的性质:

    • 根节点是彩色
    • 节点是红色或者彩色
    • 叶子节点是彩色
    • 每个红色节点必须有两个彩色子节点. 从每个叶子节点到根节点的所有门路上都不可能存在两个间断的红色节点
    • 从任意一个节点到对应的每个叶子节点所有简略门路都蕴含雷同数目的彩色节点

  • 下面的性质保障二叉查找树不会进化成单链表. 其中后两个性质保障任意节点到该节点的每个叶子节点的最长门路不会超过最短门路的 2 倍

    • 红黑树最短门路: 都是由彩色节点形成

    • 红黑树最长门路: 由红色节点和彩色节点相间形成

      • 依据从任意一个节点到对应的每个叶子节点所有简略门路中都蕴含雷同数目的彩色节点的性质可知最长门路时 : 红色节点数量 = 彩色节点数量. 该门路的长度为两倍的彩色节点数, 也就是最短门路长度的两倍

        调整节点

  • 有了旋转操作后, 须要探讨何时旋转的问题:

    • 让每个节点都蕴含辈分信息, 设计让每一个家族的辈分相差不要太过迥异

      • 这种计划存在的问题:
      • 如果扭转一个父节点的辈分, 那么这个父节点的所有子孙, 都会受到影响
      • 须要找到某中共掂量树高的某个参数, 并且使得这个参数易于放弃
      • 因为树的节点数目并不固定, 所以不同子孙所形成链表的长度必然不等
      • 不可能要求每个家族的最小辈分齐全相等
      • 让每个家族在抽离一些非凡的子女后, 达到的辈分相等

  • 红黑树:

    • 任意一个父节点到其最初一代节点的所有简略门路中 , 蕴含雷同数目的彩色节点
    • 因为父节点之后的所有简略门路不可能蕴含雷同的节点
    • 要在彩色节点之间插入红色节点, 以保障彩色节点数目相等

  • 红色节点插入时留神点:

    • 红色节点必须要少于彩色节点
    • 红色父节点两个子节点都为彩色

  • 定义红黑树节点:

    #define RED 0
#define BLACK 0
typedef struct rbNODE
{
  struct rbNODE* father;
  struct rbNODE* left;
  struct rbNODE* right;
  int value;
  int color;
}rbNODE;

  • 这样就能够生成一个红黑树:

    • 首先要有一个根节点
    • 因为根节点对于所有子孙节点都是惟一的

    • 所以根节点抉择彩色

      • 红黑树的两点要求:

        • 任意父节点到这个父节点最初一代子孙节点的所有简略门路中, 彩色节点数目雷同
        • 红色节点的左右子节点都是彩色节点

      • 第一点要求等价于:

        • 任何一个末代孙节点到根节点的简略门路中, 彩色节点数目雷同
        • 任何两个末代孙节点到达任意一个雷同父节点的简略门路中, 彩色节点数目雷同

  • 父节点和叔叔节点都为红色:

    • 如果向已有的红黑树中插入新节点 N 时, 依据第一条规定, 优先思考插入红色节点
    • 如果 N 的父节点 P 也是红色, 就违反了第二条规定, 须要将 P 节点变为彩色
    • 然而变为彩色节点之后, 这条门路就比其它门路多了一个彩色节点
    • 如果 P 的兄弟节点, 即 N 的叔叔节点 Q 是红色节点
    • 能够将 Q 节点变成彩色, 而后将 P,Q 的父节点 G 变成红色
    • 这样,G 的所有子系节点就失去了对立, 从而整棵树失去了对立
    • 可能 G 和这个 G 节点的父节点会违反第二条规定, 只须要反复调用即可

  • 叔叔节点为彩色:

    • 如果向已有的红黑树中插入新节点 N 时, 依据第一条规定, 优先思考插入红色节点
    • 如果 N 的父节点 P 也是红色, 就违反了第二条规定, 须要将 P 节点变为彩色
    • 然而变为彩色节点之后, 这条门路就比其它门路多了一个彩色节点
    • 如果 N 的叔叔节点为彩色, 能够考虑一下旋转操作:
    • 假如 xL, yL, yR 的子系均合乎红黑树的要求, 比拟旋转前后各条子系:
    旋转前 旋转后
    x, y, yL y, x, yL
    x, xL y, x, xL
    x, y, yR y, yR

    如果x, y 均为红色, 则旋转前后彩色节点的数目不会发生变化; 如果 x 为彩色, 则 y, yR 这条子系会缩小一个彩色节点; 如果 y 为彩色, 则 y, x, xL 这条子系减少一个节点

    • 两个红色节点的旋转操作不会扭转子系的彩色节点数目
    • 红父和右黑子的旋转, 会使红父的左子节点的子系减少一个彩色节点
    • 黑父和右红子的旋转, 会使红子的右节点缩小一个彩色节点

  • 当父节点 P 和子节点 N 都为红色, 且 N 的叔节点 Q 为彩色时:

    • 旋转节点 P, N. 但 P, N 旋转后不会扭转二者的二色彩, 此时不满足第二条规定
    • 因为 P 为红色, 则 P 的父亲节点 G 肯定为彩色, 而 P 的兄弟节点 Q 也为彩色, 只须要将 P 变为彩色, 让 G 变成红色, 这样就满足了第二条规定
    • 新的问题: 满足第二条规定之后,G 的 Q 子系因为 G 的变色少了一个彩色节点

    • 思考到 P, G 二者的色彩, 将这两个节点再旋转一次, 正好使得 Q 子系减少一个节点, 这样的红黑树就满足要求

      • 如果叔节点 Q 存在且为红色, 则将父节点 P 和叔节点 Q 同时设为彩色, 将祖父节点 G 设为红色, 而后将指针指向祖父节点

      • 如果叔节点 Q 不存在或者为彩色:

        • 如果插入节点与父节点在同侧(插入节点为左节点, 父节点也为左节点):

          • 将父节点 P 设为彩色, 将祖父节点 G 设为红色, 旋转 P, G

        • 如果插入节点与父节点在异侧:

          • 旋转 P 和插入节点, 而后将指针移向 P, 此时 P 与这个节点的父节点成为同侧节点
      // 调整红黑树节点
void adjust(rbNode* node) {
rbNode* pNode = node -> father; // 父节点
rbNode* qNode;

while (pNode -> color = RED) {
    int flag = pNode == pNode -> father -> left ? LEFT : RIGHT;
    qNode = flag == LEFT ? pNode -> father -> right : pNode -> father -> left;    // 叔节点
    // 如果叔节点存在且为红色
    if (qNode != NULL || qNode -> color == RED) {
        pNode -> color = BLACK;
        qNode -> color = BLACK;
        pNode -> father -> color = RED;
        node = pNode -> father;
        pNode = node -> father;
    } else {if (flag != (node == pNode -> left ? LEFT : RIGHT)) {turnRbNode(node, pNode);    // 此时插入节点与父节点在异侧
            node = pNode;
            pNode = node -> father;
        }
        // 执行下面的操作, 插入节点和父节点变为同侧
        pNode -> color = BLACK;
        pNode -> father = RED;
        turnRbNode(pNode,pNode -> father);
    } 
} 
}

插入节点

  • 红黑树插入新节点后, 须要进行调整来满足红黑树的性质:

    • 节点是红色或者彩色: 插入一个红色的新节点

      • 插入一个彩色的新节点, 就会导致这个节点所在的门路比其余门路多出一个彩色的节点, 很难调整.
      • 插入一个红色的新节点, 此时所有门路上彩色节点的数量不变, 只会呈现两个间断的红色节点的状况. 此时通过变色和旋转即可调整

  • 红黑树根节点色彩:

    • 红黑树的根节点色彩不会影响红黑树的第一条性质
    • 如果红黑树的根是红色, 那么根节点的左右子节点必须同时为彩色
    • 因而, 当根节点为彩色时对后辈色彩的影响更小, 所以选取根节点的色彩为彩色

  • 定义的二叉树的插入操作对红黑树齐全无效, 然而须要额定增加节点色彩:

    • 从二叉树的插入函数中提取新节点的指针
    • 为指针赋予色彩

    • 对指针的色彩进行调整

      • 红黑树的外围算法 adjustRBT 援用的旋转操作存在很大问题:

        • 默认在树两头进行操作, 所波及到的所有节点元素都不为 null
        • 一旦波及到根节点或者末代节点, 会引起零碎解体
        • 所以必须在变动之前进行节点判断
      // 打印红黑树, 显示节点的红黑个性
void printRBT(rbNode* root, int start) {printf("the %dth node : %d with %d\n", start, root -> value, root -> color);
if (root -> left != NULL)
    printRBT(root -> left, start + 1);
if (root -> right != NULL)
    printRBT(root -> right, start + 1);
}

// 旋转红黑树的节点, sNode 是被旋转的子节点
// root 为根节点, 输入为旋转后的根节点
rbNode* turnNode(rbNode* root, rbNode* sNode) {
    rbNode* pNode = sNode -> father;    // 被旋转的父节点
    if (sNode == pNode -> right) {        // sNode 为右子节点
        if (sNode -> left != NULL) {
            sNode -> left -> father = pNode;    // sNode 的左子节点过继给 pNode
        pNode -> right = sNode -> left;        // pNode 接管 sNode 的左子节点
        sNode -> left = pNode;        // pNode 成为 sNode 的左子节点
        } else {if (sNode -> right != NULL)
                sNode -> right -> father = pNode;
                pNode -> left = sNode -> right;
                sNode -> right = pNode;
        }
        sNode -> father = pNode -> father;
        pNode -> father = sNode;

        if (sNode -> father == NULL) 
            return sNode;
        if (pNode == pNode -> father -> right) 
            sNode -> father -> right = sNode;
        else
            sNode -> father -> left = sNode;
        return root;    
    }

    // 红黑树的插入算法
    rbNode* insertRbNode(rbNode* root, int val) {rbNode* new = (rbNode*)malloc(sizeof(rbNode));
        new -> val = value;
        new -> left = NULL, new -> right = NULL;
        new -> color = RED;

        rbNode* tmpRoot = root;        // 爱护 root 节点数据
        rbNode* temp;
        while (temp = root -> value < val ? root -> right : root -> left, temp != NULL)
            root = temp;
        new -> father = root;
        if (root -> value < val)
            root -> right = new;
        else
            root -> left = new;
        return adjustRBT(tmpRoot, new);
    }

  • main 主函数:

    // 红黑树插入算法
int main() {rbNode* Root = {NULL, NULL, NULL, 11, 1};
  rbNode* root = &Root;
  int init[7] = {2, 14, 1, 7, 15, 5, 8}
  for (int i = 0; i < 7; i ++) {root = insertRbNode(root, init[i]);
  }
  root = insertRbNode(root, 4);
  printRBT(root, 0);
  return 0;
}

    这里能够看出节点以及节点色彩的变动过程:

  • 插入新节点为红黑树的根节点:

    • 将节点的色彩由红色变为彩色

  • 插入新节点的父节点是彩色:

    • 不须要调整

  • 插入新节点的父节点是红色, 新节点的叔叔节点是红色:

    • 将父节点和叔叔节点变为彩色
    • 将祖父节点变为红色
    • 向上递归调整

  • 插入新节点的父节点是红色, 新节点的叔叔节点是彩色, 新节点是父节点的左孩子, 父节点是祖父节点的左孩子:

    • 将祖父节点进行右旋
    • 调换父节点与祖父节点的地位与色彩

  • 插入新节点的父节点是红色, 新节点的叔叔节点是彩色诶, 新节点是父节点的右孩子, 父节点是祖父节点的左孩子:

    • 将父节点进行左旋
    • 调换新节点与父节点的地位
    • 将祖父节点进行右旋
    • 调换新节点与祖父节点的地位与色彩

  • 总结:

    • 后三种状况的区别在于叔叔节点的色彩:
    • 如果叔叔节点的色彩为红色, 间接变色
    • 如果叔叔节点的色彩为彩色, 须要先抉择, 再替换色彩

删除节点

  • 删除节点首先要确定待删除节点有几个孩子:

    • 如果有两个孩子, 不能间接删除节点. 先找到该节点的前驱, 即左子树中最大的节点. 或者是该节点的后继, 即右子树中最小的节点. 而后将前驱或后继的值复制到要删除的节点中, 最初将前驱或后继节点删除
    • 因为前驱节点和后继节点至少只有一个孩子节点, 这样就能够将要删除的节点有两个孩子的问题转化为只有一个孩子节点的问题
    • 不须要关注最终删除的节点是否为想要删除的节点, 只有节点外面的值被删除即可, 树的构造如何变动不须要关注

  • 红黑树删除操作的复杂度在于删除节点的色彩:

    • 删除节点为红色:

      • 间接应用删除节点的孩子节点补上空位即可

      • 删除节点为彩色:

        • 删除节点的孩子节点为红色:

          • 间接应用删除节点的孩子节点替换删除节点并变为彩色

        • 删除节点的孩子节点为彩色:

          • 删除节点的孩子节点为新的根节点:

            • 因为删除节点是彩色节点, 孩子节点也为彩色节点, 整个红黑树的性质不变
            • 即删除节点为根节点且删除节点的左右孩子节点均为空节点, 此时将删除节点用空姐点替换实现删除操作

          • 删除节点的孩子节点的新的父节点, 新的兄弟节点, 新的兄弟节点的孩子节点都为彩色:

            • 将新的兄弟节点变为彩色
            • 依照从删除节点的孩子节点为新的根节点开始对删除节点的孩子节点的新的父节点进行再次调整

          • 删除节点的孩子节点的新的兄弟节点为彩色, 新的兄弟节点的左孩子为红色, 右孩子为彩色, 新的父节点色彩能够是红色也能够是彩色并且删除节点的孩子节点是新的父节点的左孩子:

            • 将新的兄弟节点进行右旋
            • 调换右旋后新的兄弟和新的兄弟节点的父节点的色彩
            • 此时, 所有门路上的彩色节点的数量仍然相等, 删除节点的孩子节点的兄弟节点变为了新的兄弟节点的左孩子, 新的兄弟节点的右孩子变为红色

          • 删除节点的孩子节点的新的父节点为红色, 叔叔节点为彩色. 删除节点的孩子节点是新的父节点的右孩子, 删除节点的孩子节点的新的父节点是删除节点的孩子节点的新的祖父节点的左孩子:

            • 将删除节点的孩子节点的新的父节点进行左旋
            • 调换删除节点的孩子节点与新的父节点的地位

            • 而后依照下面一种状况持续进行调整

              • 当新的父节点为红色, 有两个孩子节点并且均为彩色, 这样从删除节点的孩子节点的祖父节点登程到各个叶子节点门路上彩色节点数量才能够保持一致
              • 新的父节点曾经有两个孩子时, 删除节点的孩子节点不是新插入的节点
              • 这里的状况是由删除节点的孩子节点为根节点的子树中插入新节点, 通过调整后, 导致删除节点的孩子节点变为红色, 进而导致该状况呈现
              • 插入删除节点的孩子节点并且依照删除节点的兄弟节点为红色, 其余节点为彩色的状况解决, 此时新的父节点的右子节点变为红色, 与新的父节点造成间断的红色节点, 就能够又依照当前情况进行调整

          • 删除节点的孩子节点的新的兄弟节点为彩色, 新的兄弟节点的右孩子为红色, 新的父节点的色彩能够是红色也能够是彩色并且删除节点的孩子节点是新的父节点的左孩子:

            • 将新的父节点进行左旋

            • 调换新的父节点与新的兄弟节点的色彩, 并将兄弟节点的右孩子变为彩色

              • 因为新的父节点变为彩色, 所以通过删除节点的孩子节点的门路多了一个彩色节点, 此时, 通过删除节点的孩子节点的门路上的彩色节点与删除前的数量统一, 对于不通过删除节点的孩子节点的门路, 存在以下两种状况:

                • 门路通过左旋后删除节点的孩子节点的新的叔叔节点的左孩子, 那么门路之前必然是通过删除节点的孩子节点的新的父节点和左旋后新的叔叔节点, 而新的父节点和左旋后新的叔叔节点只是替换色彩, 所以对通过左旋后删除节点的孩子节点的新的叔叔节点的左孩子没有影响
                • 门路通过左旋后删除节点的孩子节点的叔叔节点的右孩子, 那么门路之前必然通过删除节点的孩子节点的新的父节点后左旋后的叔叔节点以及叔叔节点的右孩子, 而当初只通过了左旋后删除节点的孩子节点的叔叔节点和叔叔节点的右孩子. 在对删除节点的孩子节点的新的父节点进行左旋并且与左旋前新的兄弟节点换色后, 通过左旋后删除节点的孩子节点的新的叔叔节点的右孩子的门路少了一个彩色节点. 因为左旋后删除节点的孩子节点的新的叔叔节点的色彩能够是红色也能够是彩色. 如果左旋后删除节点的孩子节点的新的叔叔节点的色彩是红色, 那么就会和左旋后删除节点的孩子节点的新的叔叔节点的右孩子造成间断的红色节点. 此时只有将左旋后删除节点的孩子节点的新的叔叔节点的右孩子变为彩色即可

          • 删除节点的兄弟节点为红色, 其余节点为彩色:

            • 将删除节点的孩子节点的新的父节点进行左旋操作
            • 调换新的父节点与兄弟节点的色彩

  • 二叉树中的删除节点操作:

    • 如果被删除的节点有两个子节点
    • 这个节点 将与子节点的值进行替换
    • 这个替换在替换后的子节点不多于一个子节点时进行

  • 能够对二叉树的删除节点操作进行批改:

    • 只有被删除节点有子节点
    • 该节点的值就要和子节点的值进行替换
    • 而后将指针指向子节点
    • 直到指针指向末代节点
    • 最初删除节点

  • 红黑树的删除节点操作: 不须要思考色彩, 更加简略

    • 只有被删除节点有子节点, 该节点的值就要和子节点的值进行替换
    • 在值替换的过程中, 不须要替换节点的色彩
    • 而后将指针指向子节点, 直到指针指向末代节点
    • 最初要思考到节点的色彩, 对节点进行删除

    • 然而, 末代节点被删除将导致末代节点这条世系彻底隐没, 所以无论末代节点色彩如何, 都不会扭转另外世系的黑高

      // 红黑树查问, root 为根节点,val 为待查问值
// 返回值为节点的指针
rbNode* searchRBT(rbNode* root, int val) {if (root -> value == val) 
    return root;
if (root -> value < val && root -> right != NULL)
    return searchRBT(root -> right, val);
else if (root -> value > val && root -> left != NULL)
    return searchRBT(root -> left, val);
else
    return false;
}

// 红黑树删除节点, 输出为待删除的节点指针
void deleteRbNode(rbNode* dNode) {
rbNode* pNode = dNode -> father;
if (dNode -> left == NULL && dNode -> right == NULL) {if (dNode == pNode -> right)
        pNode -> right = NULL;
    else
        pNode -> left = NULL;
} else {
    // 如果左子节点存在, 则 pNode 为 dNode 的左子节点, 否则为右子节点
    pNode = (dNode -> left == NULL) ? dNode -> right : dNode -> left;
    int val = dNode -> value;
    dNode -> value = pNode -> value;
    pNode -> value = val;
    deleteRbNode(pNode)
}
}

// 主函数
int main() {rbNode Root = {NULL, NULL, NULL, 11, 1};
rbNode* root = &Root;
int init[10] = {2, 14, 1, 7, 15, 5, 8, 4, 13, 6}
for (int i = 0; i < 10; i++) {root = insertRbNode(root, init[i]);
}
rbNode* delNode = searchRBT(root, 11);
print(root, 0)
deleteRbNode(delNode);
printf("After delete node 11\n");
printRBT(root, 0);
return 0;
}

程序统计树

  • 程序统计树定义:

    • 程序统计树是红黑树的一种数据扩张
    • 程序统计树除了红黑的属性外, 节点还蕴含子系个数的信息size
    • size为以后节点为根的子树的所有节点个数

  • 程序统计树的插入节点实现:

    • 在实现红黑树的根底上
    • 首先在节点构造体中增加一个成员size
    • 而后批改插入操作, 当插入新节点时, 新节点的 size 值为 1

    • 途中经验的的所有指针指向的节点 ,size值都减少 1 

      while (temp = root -> value < val ? root -> right : root -> left, temp != NULL) {
root -> size += 1;
root = temp;
}

  • 程序统计树的删除节点实现:

    • 删除操作时, 记录最终被删除的节点指针, 所有的父辈 size 均减1

      if (dNode -> left == NULL && dNode -> right == NULL) {if (dNode == pNode -> right)
    pNode -> right = NULL;
else
    pNode -> left = NULL;
while (pNode.size -= 1, pNode -> father != NULL) {pNode = pNode -> father;}
}
  • size 值一方面给出了以后节点子系的体量
  • size 值另一方面也是对以后节点所在节点中的大小排名的一个标记

  • 当指针从根节点一次下沉, 顺带也继承了以后节点的区间信息

    rbNode* searchRBTN(rbNode* root, int n) {
  int low = 0;    // 左开右闭
  int high = root -> size;
  if (n > high)
      return NULL;
  
  while (1) {
      // 左子节点存在并且 size < n - low
      if (root -> left != NULL && root -> left -> size < n-low) {
          root = root -> left;
          high = low + root -> size;
      } else {
          root = root -> right;
          low = high - root -> size;
      }
      if (root -> right != NULL && root -> right -> size == high - root -> size)
          return root;
      if (root -> left != NULL && root -> left -> size == low + root -> size - 1)
          return root;
  }
}
正文完
红黑树
发表至： 红黑树
2021-06-28
 0
关于红黑树:数据结构与算法-红黑树-C语言实现
关于红黑树:数据结构中红黑树的详细介绍
关于红黑树:C-STL-mapunorderedmap-红黑树与hash表
关于红黑树:数据结构与算法学习红黑树

站内搜索

-「」