红黑树-结点的删除（C语言实现）

2024-01-12 15:26:46

红黑树结点的删除

首先来回顾一下二叉树结点的删除，总共分为了三种情况：

删除叶子结点，此时可以直接删除
删除结点有左子树或者右子树的单支结点，将左子树或者右子树结点直接推到删除的结点即可
删除结点同时存在左子树和右子树（双支节点），此时可以将它的直接前驱或者直接后继代替删除结点的位置，删除该结点就转化为删除它的直接后继或者直接前驱的结点，而删除结点的直接后继或者直接前驱结点只有两种情况，要么是叶子结点要么是单支结点，此时问题就间接转化为了1,2两种情况，这里涉及到两个转化，一定要理解透彻。

红黑树的删除，确实不容易理解，主要是情况有点多，并且这多种情况有的可以转化，也有的情况根本不存在。红黑树的删除终究是围绕二叉查找树的删除为基础，在其上增加了颜色和红黑树的性质，限制了红黑树删除结点后需要做出相应的调整，以满足删除结点后不改变红黑树。

红黑树的删除：

(1)删除叶子结点(无论哪种情况，我们最终处理的就是删除叶子结点的过程，2,3情况最后还是转化为删除叶子结点)

红色：直接删除，此时不影响红黑树。

黑色：情况多，后面会主要讨论。

(2)删除单支结点(结点只存在左孩子或者右孩子)

只能是黑红单支(B-R)

竖线代表分支可左可右。

上述三种形态(6种)的单支结点，根本不可能存在，所以说删除单支结点只能是删除黑红单支的黑结点。删除黑色结点后，黑高减1，将红色子结点直接推到删除结点，并且将红色结点涂黑，此时黑高又恢复到未删除结点之前的状态。（删除红色子节点--->情况1）

(3)删除双支节点

前面我们已经讲过了，删除的结点如果是双支节点存在左右子树的情况下，我们通常用删除结点的前驱节点的值或者后继结点的值代替，然后将问题转化为删除它的前驱或者后继结点。这里以后继为例（删除结点的右孩子的左子树最左的结点），删除的后继结点只有两种情况，D'是叶子结点或者单支结点，问题可以进一步转化为(1)、(2)两种情形。进一步细分的话情形1有红黑两种情况，情形2删除的结点D‘必定是黑结点直接转为(2)处理。

单支结点必定是黑红。

这里的图特意将黑色的NULL节点给加上，这是因为删除节点被摘掉后，我们可以用一个黑色的节点接上，从而进行统一处理。

为什么删除黑色叶子结点这么复杂？

删除红色叶子结点、删除单支结点，删除的如果是这些类型的结点，在经过一定的算法调整后，黑高bh一定不会发生变化，通过局部调整，子树黑高没变化，那么整棵树的黑高也就不会发生变化。

但是当删除的结点是黑色叶子结点的时候，在经过算法调整后，黑高就不一定不会变化了。某些情况调整后，它的黑高不会变化，但是某些情况调整后，黑高会变化，此时就需要递归向上处理，直至根节点，这种情况属于牵一发而动全身。

删除结点并不代表删除所在位置的结点结构？

红黑树中，删除某个结点采取的是值覆盖的方法，将整个删除结点的过程转化成删除“用来覆盖的值”所在结点的过程，这个被拿来做值覆盖所在的结点一定是叶子结点，删除过程最终转化为删除红黑树中重复值的叶子结点。

下面分析删除黑色叶子结点，也就是情况最复杂的一种：

删除黑色叶子结点后，红黑树的调整需要考虑到父结点、兄弟结点和兄弟结点的左右孩子结点，我们把这些结点的情况列出进行分析。

换种方式去理解

红黑树删除黑色叶子结点调整的核心

黑高：

从某一结点到叶子结点(其子孙结点)的黑色结点数目，用bh(x)来表示。

bh(A->B->叶子)表示从A走到B再走到某一个叶子路径的黑色节点数量（A与B，B与叶子之间可能间隔了多个节点）。

本文余下内容均指的是删除黑色的叶子节点后引发的一系列平衡操作。比如P->D->N，删除D（黑色）后，N接至父节点：P->N。

这里所指的叶子结点不是NULL结点，删除D后，N可以看做是填补的一个黑色nil结点。

因为删除了一个黑色节点（N的父节点D），经过N的路径的黑色数量减1，即bh(P->N->叶子) 比 bh(P->S->叶子) 少1。平衡的方式有：

bh(P->N->叶子)不变，bh(P->S->叶子)减1，此时已经子平衡；然而h(GP->P->叶子)还是会比bh(GP -> U ->叶子)少1。此时需要将P当作新的N，向上递归处理，这种情况就好像牵一发而动全身。[黑高变化]
bh(P->N->叶子)加1，bh(P->S->叶子)不变，也就是恢复了原来的状态，此时已经平衡，因为bh(GP->P->叶子)=bh(GP -> U ->叶子)。[黑高不变]

平衡的思路主要就是基于以上两种方式，另外要注意的是，红色和红色不能连一起的约束也不能违反。理解这个比较重要。

下面讨论删除黑色叶子结点的各种情况:

1、当前结点为黑根结点

删除黑根叶子结点，无需做平衡处理，因为树已经变成空树了。

2、兄弟结点为黑色（S=黑）

2.1、兄弟的子结点全黑(SL/SR=黑)

兄弟节点的子节点全为黑色，也就意味着兄弟节点（S）可以涂红而不会和子冲突。S涂红后，也就实现了子平衡，这时候我们看父节点是红是黑，再做处理。
- 2.1.1、父结点为黑色（P=黑）
  
  此时将S涂红，父节点作为新的平衡节点N，递归上去处理。这个也就是之前提到的bh(P->N->叶子)不变，bh(P->S->叶子)减1；而bh(GP->P->叶子)，依然会比bh(GP -> U ->叶子)少1，所以要递归上去处理。
  
  结点意义：N、SL、SR看做NIL结点去理解，N是D删除之后填补的一个结点。
  
  注：每种情况的红黑树都是不平衡的（不满足红黑树性质），N在每种情况里面都是充当了一个填补的NIL结点，填补被删除的D。
- 2.1.2、父结点为红色（P=红）
  
  此时将S涂红，P涂黑，平衡结束。 S涂红后，h(P->N->叶子)不变，h(P->S->叶子)-1，实现子平衡；因为P节点是红色的，如果将它涂黑，h(P->N->叶子)和h(P->S->叶子)均会+1，就可以恢复原来的状态了，而不用递归上去。
2.2、兄弟子结点非全黑

所谓的不全黑包括：[SL红, SR红]、[SL黑，SR红]、[SL红，SR黑]。~~如果其中一个为黑，另外一个肯定是红~~。
以全黑/非全黑作为分类，是因为全黑时无论N是在左子还是右子，其处理方式是一样的。而非全黑则要看N所处的位置（或者说S所处的位置）进行特定方向的旋转。
- 2.2.1、S在左分支，SL红；S在右分支，SR红
  
  以P为支点右旋；交换P和S颜色，SL涂黑；平衡结束。
  这里的平衡思路其实就是：h(P->S->叶子)不变（因为SL涂黑补回来了），h(P->N->叶子)+1（因为多了个黑色P）。
  
  结点意义：SL一定是真实结点，SR可以看做是真实红结点或者NIL结点，N是NIL结点。
  
  在代码中，S的颜色不一定是黑色，S的颜色是由P决定的，s->color = s->parent->color，这样做的目的是防止旋转后的结点S与GP冲突。
  
  比如P颜色为红色，旋转后如果S不改成P结点的颜色值，就会导致bh+1，破坏红黑树的性质。
  
  所以说为了不破坏红黑树的性质，通常直接将P的颜色给S。
  
  明白了上面，这个，与其对称的一种情形就好理解了。
  
  结点意义：SR一定是真实结点，SL可以看做是真实红结点或者NIL结点，N是NIL结点。
- 2.2.2、S在左分支，SR红，S在右分支，SL红
  
  以S为支点左旋，交换S和SR颜色（SR涂黑，S涂红），此时转至情形2.2.1-(1) S左-SL红进行处理。
  
  转化为单支只能是黑红！
结点意义：SR一定是真实结点，SL可以看做是真实红结点或者NIL结点，N是NIL结点。并且SL排除在了虚线框内，它对红黑树意义不大。

同理也存在与其对称的一种情况

结点意义：SL一定是真实结点，SR可以看做是真实红结点或者NIL结点，N是NIL结点。

3、兄弟结点为红色（S=红）

兄弟结点为红色，则父子结点颜色必为黑色，否则不满足性质4

S在左分支，以P进行右旋；S在右分支，以P进行左旋；旋转后交换P和S的颜色（S涂黑，P涂红），N兄弟结点变为黑色，转化为情况2处理。

结点意义：SL、SR一定是真实结点，N是NIL结点。

至此，我们介绍完了删除结点是黑色叶子结点的所有情况，在实际编程中，如何进行考虑？

删除结点是红色，简单处理
删除结点是黑色，看兄弟结点颜色
1. 兄红，以父结点旋转涂色，转为兄黑处理。
2. 兄黑，看兄弟结点的子结点是否全黑
  1. 全黑，根据父结点的颜色进行相应处理
  2. 不全黑，看兄弟所在位置及兄弟孩子的颜色和位置。

代码实现

/**
* 删除指定元素的结点
* @param T 红黑树的头结点
* @param key 删除的元素值
* @description 找到结点元素等于key的结点,删除结点，调整红黑树
*/
void RBTree_Delete(RBTRoot** T, ElemType key) {
    RBTree target, realDel, child;
    // 1.在红黑树中查找指定元素等于key的结点,可以以下逻辑封装到方法里面
    // target = RBTreeSearch(root, key);
    target = (*T)->root;
    while (key != target->key && target != (*T)->nil) {
        if (key < target->key)
            target = target->lchild;
        else if (key > target->key)
            target = target->rchild;
    }
    if (target == (*T)->nil)
        return; //树中没有key结点

    // 2. 判断删除结点是叶子、单支、双支，找到删除结点的真正位置
    // 2.1 如果为叶子结点或者单支结点，删除结点的真正位置就是其本身
    // 2.2 如果为双支结点，删除结点的真正位置为后继结点(Successor)右孩子左子树最左边的结点
    if (target->lchild == (*T)->nil || target->rchild == (*T)->nil)
        realDel = target;
    else {
        realDel = target->rchild;
        while (realDel->lchild != (*T)->nil) {
            realDel = realDel->lchild;
        }
        // 处理完毕之后，readDel不会存在左分支
    }

    // 处理完毕之后，readDel最多有一个孩子
    //找到删除结点的孩子结点，之后移植结点需要用到child
    if (realDel->lchild != (*T)->nil)
        child = realDel->lchild;    // 只有左单支走这一步
    else
        child = realDel->rchild;    // 叶子结点或者右单支走这一步

    // 3. 移植结点:结点变化父结点，左右子树

    // 建立结点关联

    // 如果是nil结点，则将空的叶子结点推到删除空缺的位置,
    // 这一步其实就是让nil结点代替删除的结点,虚设黑结点
    // 否则将子结点推到父结点
    child->parent = realDel->parent;

    if (realDel->parent == (*T)->nil)
        (*T)->root = child;
    else if (realDel->parent->lchild == realDel)
        realDel->parent->lchild = child;
    else if (realDel->parent->rchild == realDel)
        realDel->parent->rchild = child;

    // 4. 如果删除结点发生了转化，比如删除结点为双支结点,那么就转化为后继结点被删
    // 而为了不移动大量指针，这里只是将值复制到删除结点，然后在删除后继结点
    if (target != realDel)
        target->key = realDel->key;

    // 5.删除结点是黑色的需要调整,调整的是已经移植的树，传递child，而非realDel
    if (realDel->color == BLACK)
        RBTree_Delete_FixUp(*T, child);

    // 6. 释放结点
    free(realDel);
}

/**
* 红黑树删除修正函数
* @param T 头结点
* @param p 删除结点的父结点
* @param n 删除结点
* @description 找到结点元素等于key的结点,删除结点，调整红黑树
*/
void RBTree_Delete_FixUp(RBTRoot* T, RBTree n) {
    RBTree s;
    // 单支黑红结点不会进入while,因为替代结点n为红色，n结点变色即可
    // 进入循环体的一定 叶子结点 为黑色的这种情况
    while (n != T->root && n->color == BLACK) {

        // 兄在右子树
        if (n == n->parent->lchild) {
            s = n->parent->rchild;  // 找到其兄弟结点,其子必为双黑
            // 第一种情况：兄红
            if (s->color == RED) {
                s->color = BLACK;
                n->parent->color = RED;
                RBTree_L_Rotate(T, n->parent);
                // 此时,兄弟结点必为黑色，转为情况2,3,4处理
                s = n->parent->rchild;
            }
            // 第二种情况：兄黑，子全黑
            // 处理方式，兄涂红色，n指向父结点，下次while循环，如果父为红色，结束循环，
            // 循环跳出后会设置父结点为黑，也就是笔记提到的2.1.1情况。如果父为黑色，此时就需要
            // 递归向上处理，以parent为n，再找其兄弟结点，通过局部平衡达到全局平衡。
            // s->color == BLACK判断并没有多大意义，
            // 第一种情况被处理后兄结点为黑，其他情况兄结点一定为黑，所以说判断可加可不加

            if (s->color == BLACK &&
                s->lchild->color == BLACK &&
                s->rchild->color == BLACK) {
                s->color = RED;
                n = n->parent;
            }

            // 3，4两种情况包括了红红，红黑，黑红，但是必须有一个if存在限制，
            // 防止左右双红都会进入if处理
            // 第三种情况：兄黑，兄在右子树，左孩子红色
            if (s->rchild->color == BLACK &&
                s->lchild->color == RED ) {
                s->color = RED;
                s->lchild->color = BLACK;
                RBTree_R_Rotate(T, s);
                s = n->parent->rchild;
                // 一环接一环，处理后s变为情况4
                // 转为情况4处理
            }
            // 第四种情况：兄黑，兄在右子树，右孩子红色
            if (s->rchild->color == RED) {
                // 左红右红或者右红左黑都进入该条件处理
                // 使用父结点的颜色，目的是旋转S结点(新的父结点)不会和GP冲突
                s->color = n->parent->color;
                n->parent->color = BLACK;
                s->rchild->color = BLACK;
                RBTree_L_Rotate(T, n->parent);
                s = T->root;
            }
        } else {
        // 兄在左子树
            s = n->parent->lchild;
            if (s->color == RED) {
                s->color = BLACK;
                n->parent->color = RED;
                RBTree_R_Rotate(T, n->parent);
                s = n->parent->lchild;
            }
            if (s->lchild->color == BLACK && s->rchild->color == BLACK) {
                s->color = RED;
                n = n->parent;
            }
            if (s->lchild->color == BLACK && s->rchild->color == RED) {
                s->color = RED;
                s->rchild->color = BLACK;
                RBTree_L_Rotate(T, s);
                s = n->parent->lchild;
            }
            if (s->lchild->color == RED) {
                s->color = n->parent->color;
                n->parent->color = BLACK;
                s->lchild->color = BLACK;
                RBTree_R_Rotate(T, n->parent);
                n = T->root;
            }
        }
    }

    n->color = BLACK;
}

看图时刻：

(1) 删除结点是红色叶子结点(001)和单支结点(002)的动态演示。

(2) 删除结点是双支结点(009)，这里将其转化为删除前驱结点处理。而其前驱有位红色叶子结点，直接删除即可。

(3) 删除结点是双支结点(009)，转为前驱处理，换一种角度来想，也可以是直接删除(008)结点，只不过删除(009)多了一步查找转化的过程。这里前驱是黑色结点，要根据兄弟结点，父结点进行分析。

分析下面这张动图

不难发现(008)的兄弟结点都为红色，当然是按最简单的方式处理，即兄黑左分支，兄左孩子红，直接旋转涂色即可。

上面介绍的这两种情况都属于兄弟子结点为非全黑的情况。

回想一下代码中的处理是怎样的。

(4) 假若删除(0012)结点，情况属于兄黑子全黑，(0014)哪有子全黑？对于每个叶子结点都有一个nil结点，这里可以把(0014)的子结点理解为nil结点。第一次调整以11为根的子树达到局部平衡，但是他的黑高相比之前的以12结点为根的子树差一个单位，所以就必须以11为N，情况好像转为以11为待删除结点，兄结点(007)为黑，继续调整。另外也可以网上大多数贴子介绍的那样理解，这里11具有了双重黑色，需要把双重黑色继续上移至根节点，之后去除一层黑色。

兄黑子全黑

这种情况如果细分的话就属于：兄黑子全黑，父结点为黑的情况。

同样你也可以自己推导兄黑子全黑，父为红的情况。

(5) 最后列出兄红的情况，最终转为兄黑处理。

从上面几个双支结点的例子我们可以看出，双支结点的处理实质还是转化为单支结点或者叶子结点的处理，就是平衡查找树删除的那两种情况。在删除调整函数中，也主要是对删除叶子结点为黑色的进行逻辑处理判断。

完整代码：

#include <stdio.h>
#include <stdlib.h>

typedef enum {RED, BLACK} ColorType;
typedef int ElemType;
/*树结点类型定义*/
typedef struct RBNode {
    ElemType key;
    struct RBNode * lchild;
    struct RBNode * rchild;
    struct RBNode * parent;
    ColorType color;
} RBNode, *RBTree;

/*我把它理解为树的头结点*/
typedef struct RBTRoot {
    RBTree root;
    RBTree nil;
} RBTRoot;

/**
* 初始化一棵红黑树头结点
*/
RBTRoot* RBTree_Init() {
   RBTRoot* T = (RBTRoot*) malloc(sizeof(RBTRoot));
   T->nil = (RBTree) malloc(sizeof(RBNode));
   if (T == NULL || T->nil == NULL)
        exit(-1);
   T->nil->lchild = T->nil->rchild = NULL;
   T->nil->parent = NULL;
   T->nil->color = BLACK;

   T->root = T->nil;
   return T;
}


/**
* 相比于AVL,RBtree涉及的点多,但是
* 旋转只管旋转,不管颜色.
* 旋转：变化左右孩子，父结点
* 注：这里用到的是一级指针,因为改变的是结构体内部变量的地址引用，
* 并没有改变*T或者x所指的引用地址，都是在其地址上操作的，所以
* 用一级指针就可以生效。
*/
void RBTree_L_Rotate(RBTRoot* T, RBTree x) {
    RBTree rc;
    rc = x->rchild;
    x->rchild = rc->lchild;
    // 如果根节点左子树有右孩子,需更改父结点
    if (rc->lchild != T->nil)
        rc->lchild->parent = x;
    // 更改rc的父结点
    rc->parent = x->parent;
    // 判断之前的结点是否是根节点,根节点parent指向nil
    if (x->parent == T->nil) {
        T->root = rc;
    } else if (x->parent->lchild == x) {
        x->parent->lchild = rc;
    } else if (x->parent->rchild == x) {
        x->parent->rchild = rc;
    }
    x->parent = rc;
    rc->lchild = x;
}

void RBTree_R_Rotate(RBTRoot* T, RBTree x) {
    RBTree lc;
    lc = x->lchild;
    x->lchild = lc->rchild;
    if (lc->rchild != T->nil)
        lc->rchild->parent = x;

    lc->parent = x->parent;
    if (lc->parent == T->nil)
        T->root = lc;
    else if (x->parent->lchild == x)
        x->parent->lchild = lc;
    else if (x->parent->rchild == x)
        x->parent->rchild = lc;
    x->parent = lc;
    lc->rchild = x;
}

/**
* 红黑树插入修正函数
* @param T 红黑树的根
* @param x 插入的结点
* @description 用到变色和旋转
*/
void RBTree_Insert_FixUp(RBTRoot* T, RBTree x) {
   // 当前结点的父结点为红色需调整 注：根节点 parent是指向nil
   // (1) 叔叔结点是红色: (1.1,1.2)左右分支,一样处理,变色即可
   // (2) 叔叔结点是黑色：(2.1,2.2)左分支下左右孩子 (2.3,2.4)右分支下左右孩子

   while (x->parent->color == RED) {
        // 首先父结点是祖父结点的左分支还是右分支
        if (x->parent == x->parent->parent->lchild) {
            // 判断叔叔结点颜色
            if (x->parent->parent->rchild->color == RED) {
                // 将父结点和叔叔结点改为黑色,祖父结点改为红色
                x->parent->color = BLACK;
                x->parent->parent->rchild->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {
                // 叔叔结点的颜色为黑色:分父结点的(1)左孩子 (2)右孩子
                // (1)父结点左孩子：父结点颜色变为BLACK，祖父节点变RED，右旋处理
                if (x->parent->lchild == x) {
                    x->parent->color = BLACK;
                    x->parent->parent->color = RED;
                    // 注意这里是x->parent->parent 以祖父节点作为旋转的根节点
                    RBTree_R_Rotate(T, x->parent->parent);
                } else {
                // (2)右孩子,先左旋转，转为上面(1)父结点左孩子的情况
                // 借助循环下次就会运行到(1)然后右旋
                    x = x->parent;
                    RBTree_L_Rotate(T, x);
                }
            }
        } else {
            // 祖父结点的右分支
            if (x->parent->parent->lchild->color == RED) {
                // 叔叔结点为红色,左右分支都一样处理
                x->parent->color = BLACK;
                x->parent->parent->lchild->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {
                // 叔叔为黑色
                // 父结点的右分支
                if (x->parent->rchild == x) {
                    x->parent->color = BLACK;
                    x->parent->parent->color = RED;
                    RBTree_L_Rotate(T, x->parent->parent);  // 左旋
                } else {
                    // 父结点的左分支
                    x = x->parent;
                    RBTree_R_Rotate(T, x);  // 右旋
                }
            }
        }
        // 每次循环结束需要将根节点涂黑,因为可能在某次变色时,根节点变为红色
        // 不可放在循环外部
        // T->root->color = BLACK;
   }
    T->root->color = BLACK;
}

/**
* 插入结点
* @param T 红黑树的头结点
* @param key 插入结点值
* @description 找到位置,初始化结点，插入结点,调整红黑树
*/
void RBTree_Insert(RBTRoot** T, ElemType key) {
    RBTree pre; // pre保存了上一个x位置的指针(引用)
    RBTree x = (*T)->root;
    pre = x;
    while (x != (*T)->nil) {
        pre = x;
        if (x->key == key) {
            printf("\n%d已存在\n",key);
            return;
        } else if (key < x->key)
            x = x->lchild;
        else
            x = x->rchild;
    }

    // 初始化插入结点,将结点设为红色
    x = (RBTree) malloc(sizeof(RBNode));
    x->key = key;
    x->lchild = x->rchild = (*T)->nil;
    x->color = RED;
    x->parent = pre;

    // 根节点引用没有发生变化，
    // 插入根节点，直接插入,否则,向保存x父结点的pre左孩子或者右孩子插入x
    if ((*T)->root == (*T)->nil)
        (*T)->root = x;
    else if (key < pre->key)
        pre->lchild = x;
    else
        pre->rchild = x;
    // 插入之后，进行修正处理
    RBTree_Insert_FixUp(*T, x);
}

/**
* 红黑树删除修正函数
* @param T 头结点
* @param p 删除结点的父结点
* @param n 删除结点
* @description 找到结点元素等于key的结点,删除结点，调整红黑树
*/
void RBTree_Delete_FixUp(RBTRoot* T, RBTree n) {
    RBTree s;
    // 单支黑红结点不会进入while,因为替代结点n为红色，n结点变色即可
    // 进入循环体的一定 叶子结点 为黑色的这种情况
    while (n != T->root && n->color == BLACK) {

        // 兄在右子树
        if (n == n->parent->lchild) {
            s = n->parent->rchild;  // 找到其兄弟结点,其子必为双黑
            // 第一种情况：兄红
            if (s->color == RED) {
                s->color = BLACK;
                n->parent->color = RED;
                RBTree_L_Rotate(T, n->parent);
                // 此时,兄弟结点必为黑色，转为情况2,3,4处理
                s = n->parent->rchild;
            }
            // 第二种情况：兄黑，子全黑
            // 处理方式，兄涂红色，n指向父结点，下次while循环，如果父为红色，结束循环，
            // 循环跳出后会设置父结点为黑，也就是笔记提到的2.1.1情况。如果父为黑色，此时就需要
            // 递归向上处理，以parent为n，再找其兄弟结点，通过局部平衡达到全局平衡。
            // s->color == BLACK判断并没有多大意义，
            // 第一种情况被处理后兄结点为黑，其他情况兄结点一定为黑，所以说判断可加可不加

            if (s->color == BLACK &&
                s->lchild->color == BLACK &&
                s->rchild->color == BLACK) {
                s->color = RED;
                n = n->parent;
            }

            // 3，4两种情况包括了红红，红黑，黑红，但是必须有一个if存在限制，
            // 防止左右双红都会进入if处理
            // 第三种情况：兄黑，兄在右子树，左孩子红色
            if (s->rchild->color == BLACK &&
                s->lchild->color == RED ) {
                s->color = RED;
                s->lchild->color = BLACK;
                RBTree_R_Rotate(T, s);
                s = n->parent->rchild;
                // 一环接一环，处理后s变为情况4
                // 转为情况4处理
            }
            // 第四种情况：兄黑，兄在右子树，右孩子红色
            if (s->rchild->color == RED) {
                // 左红右红或者右红左黑都进入该条件处理
                // 使用父结点的颜色，目的是旋转S结点(新的父结点)不会和GP冲突
                s->color = n->parent->color;
                n->parent->color = BLACK;
                s->rchild->color = BLACK;
                RBTree_L_Rotate(T, n->parent);
                s = T->root;
            }
        } else {
        // 兄在左子树
            s = n->parent->lchild;
            if (s->color == RED) {
                s->color = BLACK;
                n->parent->color = RED;
                RBTree_R_Rotate(T, n->parent);
                s = n->parent->lchild;
            }
            if (s->lchild->color == BLACK && s->rchild->color == BLACK) {
                s->color = RED;
                n = n->parent;
            }
            if (s->lchild->color == BLACK && s->rchild->color == RED) {
                s->color = RED;
                s->rchild->color = BLACK;
                RBTree_L_Rotate(T, s);
                s = n->parent->lchild;
            }
            if (s->lchild->color == RED) {
                s->color = n->parent->color;
                n->parent->color = BLACK;
                s->lchild->color = BLACK;
                RBTree_R_Rotate(T, n->parent);
                n = T->root;
            }
        }
    }

    n->color = BLACK;
}

/**
* 删除指定元素的结点
* @param T 红黑树的头结点
* @param key 删除的元素值
* @description 找到结点元素等于key的结点,删除结点，调整红黑树
*/
void RBTree_Delete(RBTRoot** T, ElemType key) {
    RBTree target, realDel, child;
    // 1.在红黑树中查找指定元素等于key的结点,可以以下逻辑封装到方法里面
    // target = RBTreeSearch(root, key);
    target = (*T)->root;
    while (key != target->key && target != (*T)->nil) {
        if (key < target->key)
            target = target->lchild;
        else if (key > target->key)
            target = target->rchild;
    }
    if (target == (*T)->nil)
        return; //树中没有key结点

    // 2. 判断删除结点是叶子、单支、双支，找到删除结点的真正位置
    // 2.1 如果为叶子结点或者单支结点，删除结点的真正位置就是其本身
    // 2.2 如果为双支结点，删除结点的真正位置为后继结点(Successor)右孩子左子树最左边的结点
    if (target->lchild == (*T)->nil || target->rchild == (*T)->nil)
        realDel = target;
    else {
        realDel = target->rchild;
        while (realDel->lchild != (*T)->nil) {
            realDel = realDel->lchild;
        }
        // 处理完毕之后，readDel不会存在左分支
    }

    // 处理完毕之后，readDel最多有一个孩子
    //找到删除结点的孩子结点，之后移植结点需要用到child
    if (realDel->lchild != (*T)->nil)
        child = realDel->lchild;    // 只有左单支走这一步
    else
        child = realDel->rchild;    // 叶子结点或者右单支走这一步

    // 3. 移植结点:结点变化父结点，左右子树

    // 建立结点关联

    // 如果是nil结点，则将空的叶子结点推到删除空缺的位置,
    // 这一步其实就是让nil结点代替删除的结点,虚设黑结点
    // 否则将子结点推到父结点
    child->parent = realDel->parent;


    if (realDel->parent == (*T)->nil)
        (*T)->root = child;
    else if (realDel->parent->lchild == realDel)
        realDel->parent->lchild = child;
    else if (realDel->parent->rchild == realDel)
        realDel->parent->rchild = child;

    // 4. 如果删除结点发生了转化，比如删除结点为双支结点,那么就转化为后继结点被删
    // 而为了不移动大量指针，这里只是将值复制到删除结点，然后在删除后继结点
    if (target != realDel)
        target->key = realDel->key;

    // 5.删除结点是黑色的需要调整,调整的是已经移植的树，传递child，而非realDel
    if (realDel->color == BLACK)
        RBTree_Delete_FixUp(*T, child);

    // 6. 释放结点
    free(realDel);
}

/**
* 中序遍历二叉排序树
*/
void InOrderTraverse(RBTRoot* T, RBTree t) {
    if(T->nil == t){
        return ;
    }
    InOrderTraverse(T,t->lchild);
    if(t->color == RED){
        printf("%dR ",t->key);
    }else{
        printf("%dB ",t->key);
    }
    InOrderTraverse(T,t->rchild);
}

int main()
{
    int a[] = {10,9,8,7,6,5,4,3,2,1};
    //int a[] = {1,3,2};
    RBTRoot* head = RBTree_Init();
    for (int i = 0; i < 10; i++) {
        RBTree_Insert(&head, a[i]);
    }
    InOrderTraverse(head, head->root);
    for (int i = 0; i < 9; i++) {
        RBTree_Delete(&head, a[i]);
    }
    //RBTree_Delete(&head, a[6]);
    printf("\n");
    InOrderTraverse(head, head->root);
    return 0;
}

参考

码农公寓

红黑树结点的删除

红黑树删除黑色叶子结点调整的核心

相关文章