算法导论红黑树（删除）

看了许多资料，一脸懵圈，没有找到我想要的的逻辑，还是算法导论的伪码写的好。

我用简单的语言阐述我所理解的删除逻辑，(点赞超过三，附上原理图)

z；被删除的点

y；取代z的点，（也叫后继节点）

x；y的孩子节点（x只有一个右孩子，或者没有孩子）

当被删除的点是黑色的时候，一定会导致红黑树的性质被破坏。

被删除的点有两种颜色，红黑。我们追踪的就是这个被删除的点（或是他的后继节点y），当z点有两个孩子的时候，我们追踪的是y节点的颜色，此时z会被y取代，z的颜色不再影响平衡，而是x顶替y后的原y颜色会影响平衡。

如果是红，万事大吉，删除后无序调整，让我一一举例，

1；z没有孩子，删除后红黑树平衡，

2；z有且只有一个孩子，这样的状态不会出现，（没有孩子的那边少一个黑点，黑点数量不平衡，这样的状态不会存在）

3；z有两个孩子，y是z的孩子，这个时候，y会顶替z的位置，并且保持和z的颜色一直，z就会保持平衡，且无论z是什么颜色，都是平衡，此时我们不再追踪z的颜色，而是追踪y的颜色，此时若y是红色，依然直接删除（此时的y是红色，则一定没有孩子节点，因为它是后继节点，一定没有左孩子，转2理解）

4；z有两个孩子，y是z的的右子树下的一个节点，我们追踪y的颜色，如果y是红色，同理（此时的y是红色，则一定没有孩子节点，因为它是后继节点，一定没有左孩子，转2理解）直接删除

如果是黑，需要颜色调整，使用cut_out_color_fixup函数调整（请看源码）

---------------------------------------------------------------------------------------------------------------------

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<malloc.h>
//*********************************以下内容是插入源码****************************
#define N 200
#define K 100
typedef struct redblacknode RBN;
struct redblacknode {//红黑树的节点
    int key;
    char rb;
    RBN* father;
    RBN* left;
    RBN* right;
};
void redblacktree(RBN* p, int key);//红黑树，能插入关键字
void happen_rand(int* p, int n);//生成随机数
void color(RBN* p);
void right_handed(RBN* p);//右旋
void left_handed(RBN* p);//左旋
RBN sentry={-1,'b',&sentry,&sentry,&sentry };//哨兵，主要作用是节省空间，不然每一个叶节点都要开辟一个空结构体；详见算法导论10.2的介绍
RBN *uncle;//定义一个叔叔指针
RBN* NODE;//定义一个根节点指针
RBN* tmp,*tmptmp;

void happen_rand(int* p, int n) {
    int i;
    for (i = 0; i < N; i++) {
        p[i] = rand() % K;

    }
}

void redblacktree(RBN* p, int key) {//递归的方式把key插入到红黑树中
    if (key < p->key && p->left == &sentry) {//插入节点后需要用color函数调整颜色

   p->left = (RBN*)malloc(sizeof(RBN));
        p->left->key = key;
        p->left->father = p;
        p->left->left = &sentry;
        p->left->right = &sentry;
        p->left->rb = 'r';
        color(p->left);
    }
    else if (key >= p->key && p->right == &sentry) {
        p->right = (RBN*)malloc(sizeof(RBN));
        p->right->key = key;
        p->right->father = p;
        p->right->left = &sentry;
        p->right->right = &sentry;
        p->right->rb = 'r';
        color(p->right);
    }
    else if (key < p->key && p->left != &sentry)
        redblacktree(p->left, key);
    else if (key >= p->key && p->right != &sentry)
        redblacktree(p->right, key);

}

void color(RBN* p) {//颜色调整分为6种状态，前两种不旋转直接调色，后四种要旋转，旋转后再调色，旋转有4种状态，每一种状态旋转后需要调色（176页）（/右旋）（\左旋）（<左旋+/右旋）（>右旋+\左旋）
    if (p->rb == 'b') { return; }
    if (p->father->rb == 'r') {
        if (p->father == p->father->father->left) {//父节点是左节点
            uncle = p->father->father->right;//叔节点是右节点
            if (uncle->rb == 'r') {//叔节点是红
                if (p->father->father->father != &sentry)p->father->father->rb = 'r';
                p->father->rb = 'b';
                uncle->rb = 'b';
                color(p->father->father);
            }
            else if (uncle->rb == 'b' || uncle == &sentry) {//叔节点是黑或者是无
                if (p == p->father->left) {//插入节点是左，进行右旋，变色

  right_handed(p->father);
                    p->father->rb = 'b';
                    p->father->right->rb = 'r';
                    color(p->father);
                }
                else if (p == p->father->right) {//插入节点是右，进行左旋,右旋,变色

left_handed(p);

                    right_handed(p);
                    p->rb = 'b';
                    p->right->rb = 'r';
                    color(p);
                }

            }
        }
        else if (p->father == p->father->father->right) {//父节点是右节点
            uncle = p->father->father->left;//叔节点是左节点
            if (uncle->rb == 'r') {//叔节点是红
                if (p->father->father->father != &sentry)p->father->father->rb = 'r';
                p->father->rb = 'b';
                uncle->rb = 'b';
                color(p->father->father);
            }
            else if (uncle->rb == 'b' || uncle == &sentry) {//叔节点是黑或者是无
                if (p == p->father->right) {//插入节点是右，进行左旋，变色

                     left_handed(p->father);
                    p->father->rb = 'b';
                    p->father->left->rb = 'r';
                    color(p->father);
                }
                else if (p == p->father->left) {//插入节点是左，进行右旋，左旋，左旋
                    right_handed(p);
                    left_handed(p);
                    p->rb = 'b';
                    p->left->rb = 'r';
                    color(p);
                }
            }
        }
    }

}

void left_handed(RBN* p) {
    RBN* y = p;
    RBN* x = y->father;
    x->right = y->left;
    if (y->left != &sentry) y->left->father = x;
    y->father = x->father;
    if (x->father == &sentry) NODE = y;
    else if (x == x->father->left) x->father->left = y;
    else x->father->right = y;
    y->left = x;
    x->father = y;
}

void right_handed(RBN* p) {
    RBN* x = p;
    RBN* y = x->father;
    y->left = x->right;
    if (x->right != &sentry) x->right->father = y;
    x->father = y->father;
    if (y->father == &sentry) NODE = x;
    else if (y == y->father->left) y->father->left = x;
    else y->father->right = x;
    x->right = y;
    y->father = x;
}
//*********************************以上内容是插入源码****************************

//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

//*********************************以下内容是按层打印源码****************************
typedef struct queue SQ;//队列
struct queue {
    RBN array[N];
    RBN* head;
    RBN* tail;
};//申明队列结构体
int enqueue(SQ* p, RBN n);//入队
RBN* dequeue(SQ* p);//出队
int printf_tree_layer(RBN* p);//按层遍历打印二叉树
int enqueue(SQ* p, RBN n) {
    *p->tail = n;
    p->tail++;
    if (p->tail == &p->array[N]) {
        p->tail = &p->array[0];
    }//尾部循环
    if (p->head == p->tail)//判断溢出
        return -1;

}
RBN* dequeue(SQ* p) {
    if (p->head == &p->array[N]) {
        p->head = &p->array[0];
    }//尾部循环
    if (p->head == p->tail) //判断溢出
    {
        RBN* p = NULL;
        return p;
    }
    return (p->head++);
}
SQ Q = { {0},&Q.array[0],&Q.array[0] };//Q队列初始化
int k = 0;
int sumup = 1;//当前行的元素个数
int sumdown = 0;//下一行的元素个数
int printf_tree_layer(RBN* p) {
    if (p == &sentry) { printf("not number"); return; }
    if (0 == sumup) {//这里是关键，当前元素是0的时候换行，
        if (sumdown == 0) { printf("\n"); sumdown = 1; return; }//判断下一行是否为0
        printf("\n");
        sumup = sumdown;
        sumdown = 0;
    }
    printf("%d ", p->key);
    sumup--;//每次打印后当前元素个数减一
    if (&sentry != p->left) { enqueue(&Q, *p->left); sumdown++; }//每次生成子元素后下一行元素个数加一
    if (&sentry != p->right) { enqueue(&Q, *p->right); sumdown++; }//每次生成子元素后下一行元素个数加一
    RBN* T = dequeue(&Q);
    printf_tree_layer(T);

}
//*********************************以上内容是按层打印源码****************************

//;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

//*********************************以下内容是删除源码****************************
RBN* y,*x;//记录将要被删除(或者是后继节点)的和替补的结构体的地址
char y_color;///记录将要被删除的结构体的颜***r /> void rb_transplant(RBN* father, RBN* son);//儿子移动到父亲的位置
RBN* rb_delete(RBN *p);//删除p节点
RBN* address(RBN*p,int key);//通过关键字，找地址，
RBN* tree_minsum(RBN* p);//找到后继（该节点的右子树的最小元素）
RBN* cut_out_color_fixup(RBN* x);//删除后，保持平衡
RBN* cut_out_color_fixup(RBN* x) {
    RBN* w; //兄弟节点
    while (x != NODE && x->rb == 'b') {//y是黑色，x也是黑色，x就是双黑节点（被移动的节点是黑色，替补上去的也是黑色，叫做双黑非根节点）
        if (x == x->father->left) {
            w = x->father->right;//兄弟节点
            if (w->rb == 'r') {//四种状态，详见算法导论186页
                w->rb = 'b';
                x->father->rb = 'r';
                left_handed(w);
                w = x->father->right;
            }
            if (w->left->rb == 'b' && w->right->rb == 'b') {
                w->rb = 'r';
                x = x->father;
                continue;
            }
            else if (w->right->rb == 'b') {
                w->left->rb = 'b';
                w->rb = 'r';
                right_handed(w->left);
                w = x->father->right;
            }
            w->rb = x->father->rb;
            x->father->rb = 'b';
            w->right->rb = 'b';
            left_handed(w);
            x = NODE;

        }
        else {
            w = x->father->left;//兄弟节点
            if (w->rb == 'r') {
                w->rb = 'b';
                x->father->rb = 'r';
                right_handed(w);
                w = x->father->left;
            }
            if (w->left->rb == 'b' && w->right->rb == 'b') {
                w->rb = 'r';
                x = x->father;
                continue;
            }
            else if (w->left->rb == 'b') {
                w->right->rb = 'b';
                w->rb = 'r';
                left_handed(w->right);
                w = x->father->left;
            }
            w->rb = x->father->rb;
            x->father->rb = 'b';
            w->left->rb = 'b';
            right_handed(w);
            x = NODE;


        }
    }
    x->rb = 'b';
}
RBN* tree_minsum(RBN* p)

{
    while (p->left != &sentry) {
        p = p->left;
    }
    return p;
}
void rb_transplant(RBN* father, RBN* son) {
    if (father->father == &sentry) {
        NODE = son;
    }
    else if (father == father->father->left) {
        father->father->left = son;
    }
    else {
        father->father->right = son;

    }
    son->father = father->father;
}
RBN* address(RBN*p,int key) {
    if (key == p->key) return p;
    if (p == &sentry)return &sentry;
    if (key < p->key)
        address(p->left, key);
    else
        address(p->right, key);

}
RBN* rb_delete(RBN* z) {
    y = z;
    y_color = y->rb;
    if (z->left == &sentry) {
        x = z->right;
        rb_transplant(z, z->right);
    }
    else if(z->right == &sentry) {
        x = z->left;
        rb_transplant(z, z->left);
    }
    else {
        y = tree_minsum(z->right);
        y_color = y->rb;
        x = y->right;
        if (y->father == z){//后继节点是z的右孩子
            x->father = y;
        }
        else { //将后继节点y取出,放到z的右孩子的父节点
            rb_transplant(y, y->right);
            y->right = z->right;
            y->right->father = y;
        }
        rb_transplant(z, y);
        y->left = z->left;
        y->left->father = y;
        y->rb = z->rb;//保持原有的平衡
    }
    if (y_color == 'b') {//y是红色，必然没有孩子，直接删除后，无需调整颜色，y是黑色，删除后需要调整颜***r />         cut_out_color_fixup(x);
    }
}

//*********************************以上内容是删除源码****************************
int main() {
    int array[N] = { 0}, i;
    happen_rand(array, N);//数组随机化
    RBN node = { array[0],'b' ,&sentry,&sentry,&sentry };//根节点
    NODE = &node;
    for (i = 1; i < N; i++) {
        redblacktree(NODE, array[i]);//在红黑树中插入元素
    }
    printf_tree_layer(NODE);
    for (i = 0; i < N; i++) {
        RBN* tmp = address(NODE,array[i] );
        rb_delete(tmp);//在红黑树中删除元素
        printf_tree_layer(NODE);
    }

}