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

目录

前言

 一、左旋和右旋

左旋（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）

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

操作如下：

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

//左旋（以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）其父节点指向x
	y->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成为左子节点
		else
			x->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点
	}
	//y的左子节点指向x，x的父节点指向y
	y->left = x;
	x->par = y;
}

右旋（Right Rotation） 

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

操作如下：

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

//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {
	Node* y = x->left;//标记到左子节点y
	x->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;
		else
			x->par->right = y;
	}
	//y的右子节点指向x，x的父节点为y
	y->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;
		else
			cur = cur->right;
	}
	printf("The target is not exist\n");
	return NULL;
}

三、红黑树的删除

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

• 删除的是叶子节点（下面又分2种情况）
  • 删除节点的颜色是红色
  • 删除节点的颜色是黑色（下面再分5种情况）
    1. 兄弟节点没有左右孩子
    2. 兄弟节点左孩子为红色，右孩子为黑色
    3. 兄弟节点右孩子为红色，左孩子为黑色
    4. 兄弟节点有左右孩子，且都为红色
    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）其父节点指向x
	y->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成为左子节点
		else
			x->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点
	}
	//y的左子节点指向x，x的父节点指向y
	y->left = x;
	x->par = y;
}
//右旋（以x为旋转点，向右旋转）
void right_rotate(rbtree* T, Node* x) {
	Node* y = x->left;//标记到左子节点y
	x->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;
		else
			x->par->right = y;
	}
	//y的右子节点指向x，x的父节点为y
	y->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;
		else
			cur = 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;
		//删除节点x
		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->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;
			else
				target->par->right = T->nil;
			free(target);
			target = NULL;
		}
		//1-02 如果是黑色叶子节点进入到调整
		else
			Del_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;//根结点为黑色
}

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

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

分享一张壁纸：