数据结构-----红黑树的删除操作

前言

一、左旋和右旋

左旋（Left Rotation）

右旋（Right Rotation）

二、红黑树的查找

三、红黑树的删除

1.删除的是叶子节点

1.1删除节点颜色为红色

1.2删除节点颜色为黑色

1.2-1 要删除节点D为黑色，兄弟节点没有左右孩子

1.2-2 要删除节点D为黑色，兄弟节点有左孩子，右孩子为空

1.2-3 要删除节点D为黑色，兄弟节点有右孩子，左孩子为空

1.2-4 要删除节点为黑色，兄弟节点左右孩子都存在，且为红色

1.2-5 要删除节点为黑色，兄弟节点为红色

2.删除节点只有左孩子，没有右孩子

3.删除节点只有右孩子，没有左孩子

4.删除节点有左右子节点，且都为红色

四、完整代码

前言

只有流过血的手指，才能弹出世间的绝唱。 —— 泰戈尔

今天我们接着学习红黑树，前面学习了红黑树的插入操作，那这次就学习红黑树的删除操作，相较于红黑树的插入操作，红黑树的删除操作更加复杂，但是别急，下面我会非常详细的去讨论这个过程，以及提供完整的代码，好了，开始上正文。

相关链接

红黑树介绍：数据结构-----红黑树简介_Gretel Tade的博客-CSDN博客

红黑树的插入：数据结构-----红黑树的插入_Gretel Tade的博客-CSDN博客

再讲之前，我分享一个网址给大家（链接：Red/Black Tree Visualization），这个是一个红黑树模拟器的网址，你们可以去进行红黑树插入删除遍历等操作，可以自己试试看。如下图所示：

一、左旋和右旋

左旋（Left Rotation）

左旋是一种将某个节点的右子节点旋转上来的操作。也就是说当前节点的右子节点顶替了自己，然后自己变为右子节点的左子节点，以保持树的平衡。

操作如下：

将当前节点的右子节点设为新的父节点。
将新的父节点的左子节点设为当前节点的右子节点。
如果当前节点有父节点，将新的父节点替代当前节点的位置。
将当前节点设为新的父节点的左子节点。

//左旋（以x为旋转点，向左旋转）
void left_rotate(rbtree* T, Node* x) {Node* y = x->right;//标记到右子节点x->right = y->left;//y的左子节点代替x的右子节点if (x->right != T->nil)x->right->par = x;//如果不为空（nil）其父节点指向xy->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了if (x->par == T->nil) {//判断x的父节点是否为根结点T->root = y;//如果是的话，y就变为根结点}else {//y顶替x的位置if (x == x->par->left)x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点elsex->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点}//y的左子节点指向x，x的父节点指向yy->left = x;x->par = y;
}

右旋（Right Rotation）

同样的右旋也是将左子节点顶替自己成为父节点，然后自己成为左子节点的右子节点。

操作如下：

将当前节点的左子节点设为新的父节点
将新的父节点的右子节点设为当前节点的左子节点
如果当前节点有父节点，将新的父节点替代当前节点的位置
将当前节点设为新的父节点的右子节点

//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {Node* y = x->left;//标记到左子节点yx->left = y->right;//y的右子节点代替x的左子节点if (x->left != T->nil)x->left->par = x;y->par = x->par;//y的父节点指向x的父节点if (x->par == T->nil)T->root = y;//如果x是根结点的话，那么y代替x成为根结点else {if (x == x->par->left)x->par->left = y;elsex->par->right = y;}//y的右子节点指向x，x的父节点为yy->right = x;x->par = y;
}

二、红黑树的查找

红黑树是二叉排序树，查找也跟AVL树是一样的，根据key的值的大小去向左向右查找，找到就返回即可。

//根据key查找
Node* Search_key(rbtree* T, int target) {assert(T);assert(T->root);Node* cur = T->root;while (cur) {if (cur->key == target)return cur;//找到就返回else if (cur->key > target)cur = cur->left;elsecur = cur->right;}printf("The target is not exist\n");return NULL;
}

三、红黑树的删除

红黑树的删除所有情况如下所示：

删除的是叶子节点（下面又分2种情况）
删除节点的颜色是红色
删除节点的颜色是黑色（下面再分5种情况）
兄弟节点没有左右孩子
兄弟节点左孩子为红色，右孩子为黑色
兄弟节点右孩子为红色，左孩子为黑色
兄弟节点有左右孩子，且都为红色
兄弟节点有左右孩子，且都为黑色（兄弟节点为红色）
删除的只有左子节点，没有右子节点
删除的只有右子节点，没有左子节点
删除的既有左子节点，又有右子节点

以上就是红黑树删除操作的全部情况，非常清晰，那这里就要去进行一个一个来讨论了。

以下图片标注说明

D：表示要删除的节点

P：表示删除节点的父节点

B：表示D的兄弟节点

LN：表示B的左子节点

RN：表示B的右子节点

1.删除的是叶子节点

如果删除的是叶子节点，那就要去看删除节点的颜色来操作，以下分两种情况：

删除节点颜色为红色
删除节点颜色为黑色

注意事项

删除的是叶子结点，右两种可能，也就是要删除的叶子结点是左叶子结点或者是右叶子结点，下面我会去通过删除左叶子结点来去讨论上面这些过程，如果要删除右叶子结点，这里只需要进行对称操作就行了

1.1删除节点颜色为红色

直接删除，因为删除掉红色节点不会影响到红黑树的基本特性

1.2删除节点颜色为黑色

如果要删除节点的颜色为黑色的话，那么这里就要考虑到被删除节点的兄弟节点的颜色了：

如果兄弟节点颜色为黑色，那么父节点颜色既可以是黑色也可以是红色（下图用白色表示）
如果兄弟节点颜色为红色，那么父节点颜色只能是黑色

1.2-1 要删除节点D为黑色，兄弟节点没有左右孩子

操作如下：

删除D节点
P的颜色变为黑色
B的颜色变为红色

1.2-2 要删除节点D为黑色，兄弟节点有左孩子，右孩子为空

操作如下：

删除D节点
对B进行右旋
LN的颜色变为P的颜色
P的颜色变为黑色
对P进行左旋

1.2-3 要删除节点D为黑色，兄弟节点有右孩子，左孩子为空

操作如下：

删除D节点
B的颜色变P的颜色
P的颜色变为黑色
对P进行左旋

1.2-4 要删除节点为黑色，兄弟节点左右孩子都存在，且为红色

操作如下：

删除D节点
对P进行左旋
B的颜色变为P的颜色
P的颜色染为黑色
RN的颜色染为黑色

1.2-5 要删除节点为黑色，兄弟节点为红色

对于这种情况的话，父节点P的颜色那就是必须为黑色了，操作如下：

删除节点D
对P进行左旋
B的颜色染黑
LN的颜色染红

这里只讨论了删除节点作为左叶子节点的情况，还有作为右叶子结点的情况还没有说，但是操作跟上面这5种是一模一样的，只是个对称而已，这里就不多说了，各位可以自己照着上面的方式进行画图理解

2.删除节点只有左孩子，没有右孩子

对于这种情况，也就只有下图这种样式：

将D的值替换为LC的值
删除LC节点

3.删除节点只有右孩子，没有左孩子

对于这种情况，也是只有下图的样式：

将D的值替换为RC的值
删除RC节点

4.删除节点有左右子节点，且都为红色

对于这种情况处理，我们在前面学习二叉排序树的时候就已经知道了，首先要找到这个节点的后驱来替代这个节点，也就是在这个节点右子树找到最小的那个节点temp，替代这个被删除的节点D，然后问题就转换为删除temp节点，对于t删除emp节点就转化为上面三大类的删除情况（递归即可）。

四、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>//宏定义颜色
#define red 0
#define black 1//数据类型Datatype
typedef char Datatype;
//红黑树节点存储结构
typedef struct node {Datatype data;int color;int key;struct node* par;//父节点指针struct node* left, * right;//左右子节点指针
}Node;//红黑树的定义rbtree
typedef struct tree {Node* root;//指向根节点指针Node* nil;//叶子节点（哨兵）
}rbtree;//创建初始化红黑树
rbtree* Create_inittree() {rbtree* T = (rbtree*)malloc(sizeof(rbtree));assert(T);T->nil = (Node*)malloc(sizeof(Node));assert(T->nil);//T->nil是不储存数据的节点，作为空节点代替NULL，也就是哨兵节点（表示空）T->nil->color = black;T->nil->par = NULL;T->nil->left = T->nil->right = NULL;T->root = T->nil;return T;
}//创建一个节点
Node* Create_node(rbtree*T ,Datatype data, int key) {Node* new_node = (Node*)malloc(sizeof(Node));assert(new_node);new_node->data = data;new_node->color = red;//初始化颜色红色//左右父节点为nil哨兵节点new_node->left=new_node->right = T->nil;new_node->par = T->nil;new_node->key = key;return new_node;
}//左旋（以x为旋转点，向左旋转）
void left_rotate(rbtree* T, Node* x) {Node* y = x->right;//标记到右子节点x->right = y->left;//y的左子节点代替x的右子节点if (x->right != T->nil)x->right->par = x;//如果不为空（nil）其父节点指向xy->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了if (x->par == T->nil) {//判断x的父节点是否为根结点T->root = y;//如果是的话，y就变为根结点}else {//y顶替x的位置if (x == x->par->left)x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点elsex->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点}//y的左子节点指向x，x的父节点指向yy->left = x;x->par = y;
}
//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {Node* y = x->left;//标记到左子节点yx->left = y->right;//y的右子节点代替x的左子节点if (x->left != T->nil)x->left->par = x;y->par = x->par;//y的父节点指向x的父节点if (x->par == T->nil)T->root = y;//如果x是根结点的话，那么y代替x成为根结点else {if (x == x->par->left)x->par->left = y;elsex->par->right = y;}//y的右子节点指向x，x的父节点为yy->right = x;x->par = y;
}//根据key查找
Node* Search_key(rbtree* T, int target) {assert(T);assert(T->root);Node* cur = T->root;while (cur) {if (cur->key == target)return cur;//找到就返回else if (cur->key > target)cur = cur->left;elsecur = cur->right;}printf("The target is not exist\n");return NULL;
}//删除黑色叶子节点调整
void Del_b_adjust(rbtree* T, Node* x) {//被删除节点x父节点的左边if (x == x->par->left) {Node* p = x->par;//父节点Node* b = p->right;//兄弟节点p->left = T->nil;//删除节点xfree(x);x = NULL;//1.兄弟节点为黑色if (b->color == black) {//1-1没有侄子节点if (b->left == T->nil && b->right == T->nil) {p->color = black;b->color = red;}//1-2左侄节点红色else if (b->left->color == red && b->right == T->nil) {right_rotate(T, b);b->par->color = p->color;p->color = black;left_rotate(T, p);}//1-3右侄子节点红色else if (b->left == T->nil && b->right->color == red) {b->color = p->color;p->color = black;left_rotate(T, p);}//1-4 两个侄子节都是红色else {left_rotate(T, p);b->color = p->color;b->right->color = black;p->color = black;}}//2.兄弟节点为红色else {left_rotate(T, p);b->color = black;p->right->color = red;}}//被删除节点在父节点的右边else {Node* p = x->par;Node* b = p->left;p->right = T->nil;free(x);x = NULL;//1.兄弟节点黑色if (b->color == black) {//1-1没有侄子节点if (b->left == T->nil && b->right == T->nil) {p->color = black;b->color = red;}//1-2兄弟有右子节点else if (b->right->color == red && b->left == T->nil) {left_rotate(T, b);b->par->color = p->color;p->color = black;right_rotate(T, p);}//1-3 兄弟有左子节点else if (b->left->color == red && b->right == T->nil) {b->color = p->color;p->color = black;b->left->color = black;right_rotate(T, p);}//1-4 兄弟有左右子节点else {right_rotate(T, p);b->color = p->color;p->color = black;b->left->color = black;}}//2.兄弟节点为红色else {right_rotate(T, p);b->color = black;p->left->color = red;}}
}
//查找删除替身节点（找后驱）
Node* node_successor(rbtree* T, Node* root) {while (root->left != T->nil)root = root->left;return root;
}
//删除节点操作
void Delete_node(rbtree* T, Node* target) {//1.删除的节点是叶子节点if (target->left == T->nil && target->right == T->nil) {//1-01如果这个节点是红色节点if (target->color == red) {if (target == target->par->left)target->par->left = T->nil;elsetarget->par->right = T->nil;free(target);target = NULL;}//1-02 如果是黑色叶子节点进入到调整elseDel_b_adjust(T, target);}//2.删除的只有一个左孩子的节点else if (target->left != T->nil && target->right == T->nil) {Node* lc = target->left;target->data = lc->data;target->key = lc->key;target->left = T->nil;free(lc);lc = NULL;}//3.删除的只有一个右孩子的节点else if (target->left == T->nil && target->right != T->nil) {Node* rc = target->right;target->data = rc->data;target->key = rc->key;target->right = T->nil;free(rc);rc = NULL;}//4.删除的节点有左右孩子else {Node* sub = node_successor(T, target->right);//找到替代者target->data = sub->data;target->key = sub->key;Delete_node(T, sub);//递归进入到前三种删除方式}T->root->color = black;//根结点为黑色
}

代码很长，相较于红黑树的插入而已红黑树的删除更为复杂，各位看官慢慢看，我把上面这些情况都写得很详细了，相信你们可以理解。学会红黑树的插入和删除就基本上学会了红黑树啦，恭喜你哦！

好了，以上就是本期的全部内容了，我们下一次见！拜拜！

分享一张壁纸：