Red-black_tree_example.svg.png

树

• 树:
  • 数据结构中是以二叉堆的形式出现的
  • 如果从链表的观点出发,相当于是放宽了有序的的要求
  • 允许两个不同位置的元素有相等的序
• 对于序为n的节点来说,可以指向多个序为n+1的节点:
  • 相应的后者称为前者的孩子
  • 前者称为后者的父节点

  • 最大的序即为树的高度

    

    -
• 0节点的左右两个节点分别为0节点的左子节点和右子节点
• 0节点也是这两个子节点的父节点
• 在一个树中,只有0节点没有父节点.这个节点叫做根节点

二叉搜索树

• 二叉搜索树:
  • 父节点大于或者等于左子节点及所有子节点

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

    

    -

初始化

• 要在二叉搜索树中查询任意一个值:
  • 最坏的情况就是查询到最下面的节点
  • 进行比较的次数为树的高度
    • 由于这是二叉树,若树的元素个数为n,则理想情况下树的高度不大于log₂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;
}

红黑树

• 红黑树具有良好的效率,可以在时间内完成查找,增加,删除操作
• 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;
    }
}