看了许多资料，一脸懵圈，没有找到我想要的的逻辑，还是算法导论的伪码写的好。
我用简单的语言阐述我所理解的删除逻辑，(点赞超过三，附上原理图)
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) {//插入节点是左，进行右旋，变色
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) {//插入节点是右，进行左旋,右旋,变色
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) {//插入节点是右，进行左旋，变色
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);
}
}
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);
}
}
，
京公网安备 11010502036488号