数据结构与算法——第9章-查找表-红黑树中删除结点(9.8.4)

发表于 分类于 ， ， 阅读时长 ≈ 4 分钟

一 概述

1
2
3
4
1.红黑树中删除结点的步骤
2.三种情况分析
3.判断依据
4.示例代码

二 红黑树中删除结点的步骤

1
2
3
在红黑树中删除结点，思路更简单，只需要完成 2 步操作：
1. 将红黑树按照二叉查找树删除结点的方法删除指定结点；
2. 重新调整删除结点后的树，使之重新成为红黑树；（还是通过旋转和重新着色的方式进行调整）

三 三种情况分析

1
2
3
4
在二叉查找树删除结点时，分为 3 种情况：
1.若该删除结点本身是叶子结点，则可以直接删除；
2.若只有一个孩子结点（左孩子或者右孩子），则直接让其孩子结点顶替该删除结点；
3.若有两个孩子结点，则找到该结点的右子树中值最小的叶子结点来顶替该结点，然后删除这个值最小的叶子结点。

四 判断依据

以上三种情况最终都需要删除某个结点，此时需要判断删除该结点是否会破坏红黑树的性质。判断的依据是：

一、

1
如果删除结点的颜色为红色，则不会破坏；

二、

1
如果删除结点的颜色为黑色，则肯定会破坏红黑树的第 5 条性质，此时就需要对树进行调整，调整方案分 4 种情况讨论：

2-1

1
删除结点的兄弟结点颜色是红色，调整措施为：将兄弟结点颜色改为黑色，父亲结点改为红色，以父亲结点来进行左旋操作，同时更新删除结点的兄弟结点（左旋后兄弟结点发生了变化），如下图所示：

2-2

1
2
删除结点的兄弟结点及其孩子全部都是黑色的，调整措施为：将删除结点的兄弟结点设为红色，
同时设置删除结点的父结点标记为新的结点，继续判断；

2-3

1
2
删除结点的兄弟结点是黑色，其左孩子是红色，右孩子是黑色。调整措施为：将兄弟结点设为红色，
兄弟结点的左孩子结点设为黑色，以兄弟结点为准进行右旋操作，最终更新删除结点的兄弟结点；

2-4

1
2
删除结点的兄弟结点是黑色，其右孩子是红色（左孩子不管是什么颜色），
调整措施为：将删除结点的父结点的颜色赋值给其兄弟结点，然后再设置父结点颜色为黑色，兄弟结点的右孩子结点为黑色，根据其父结点做左旋操作，最后设置替换删除结点的结点为根结点；

五 示例代码

红黑树删除结点具体实现代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
void rbTree_transplant(RBT_Root* T, RB_TREE* u, RB_TREE* v) {
	if(u->p == T->nil) {
		T->root = v;
	} else if(u == u->p->left) {
		u->p->left=v;
	} else {
		u->p->right=v;
	}
	v->p = u->p;
}
void RB_Delete_Fixup(RBT_Root**T,RB_TREE*x) {
	while(x != (*T)->root && x->color == BLACK) {
		if(x == x->p->left) {
			RB_TREE* w = x->p->right;
//第 1 种情况：兄弟结点是红色的
			if(RED == w->color) {
				w->color = BLACK;
				w->p->color = RED;
				rbTree_left_rotate((*T),x->p);
				w = x->p->right;
			}
//第 2 种情况：兄弟是黑色的，并且兄弟的两个儿子都是黑色的。
			if(w->left->color == BLACK && w->right->color == BLACK) {
				w->color = RED;
				x = x->p;
			}
//第 3 种情况
			if(w->left->color == RED && w->right->color == BLACK) {
				w->left->color = BLACK;
				w->color = RED;
				rbTree_right_rotate((*T),w);
				w = x->p->right;
			}
//第 4 种情况
			if (w->right->color == RED) {
				w->color = x->p->color;
				x->p->color = BLACK;
				w->right->color = BLACK;
				rbTree_left_rotate((*T),x->p);
				x = (*T)->root;
			}
		} else {
			RB_TREE* w = x->p->left;
//第 1 种情况
			if(w->color == RED) {
				w->color = BLACK;
				x->p->color = RED;
				rbTree_right_rotate((*T),x->p);
				w = x->p->left;
			}
//第 2 种情况
			if(w->left->color == BLACK && w->right->color == BLACK) {
				w->color = RED;
				x = x->p;
			}
//第 3 种情况
			if(w->left->color == BLACK && w->right->color == RED) {
				w->color = RED;
				w->right->color = BLACK;
				w = x->p->left;
			}
//第 4 种情况
			if (w->right->color == BLACK) {
				w->color=w->p->color;
				x->p->color = BLACK;
				w->left->color = BLACK;
				rbTree_right_rotate((*T),x->p);
				x = (*T)->root;
			}
		}
	}
	x->color = BLACK;//最终将根结点的颜色设为黑色
}
void rbTree_delete(RBT_Root* *T, int k) {
	if(NULL == (*T)->root) {
		return ;
	}
//找到要被删除的结点
	RB_TREE * toDelete = (*T)->root;
	RB_TREE * x = NULL;
//找到值为 k 的结点
	while(toDelete != (*T)->nil && toDelete->key != k) {
		if(k<toDelete->key) {
			toDelete = toDelete->left;
		} else if(k>toDelete->key) {
			toDelete = toDelete->right;
		}
	}
	if(toDelete == (*T)->nil) {
		printf("\n%d 不存在\n",k);
		return;
	}
//如果两个孩子，就找到右子树中最小的结点，将之代替，然后直接删除该结点即可
	if(toDelete->left != (*T)->nil && toDelete->right != (*T)->nil) {
		RB_TREE* alternative = rbt_findMin((*T), toDelete->right);
		k = toDelete->key = alternative->key;//这里只对值进行复制，并不复制颜色，以免破坏红黑树的性质
		toDelete = alternative;
	}
//如果只有一个孩子结点（只有左孩子或只有右孩子），直接用孩子结点顶替该结点位置即可（没有孩子结点的也走此判断语句）。
	if(toDelete->left == (*T)->nil) {
		x = toDelete->right;
		rbTree_transplant((*T),toDelete,toDelete->right);
	} else if(toDelete->right == (*T)->nil) {
		x = toDelete->left;
		rbTree_transplant((*T),toDelete,toDelete->left);
	}
//在删除该结点之前，需判断此结点的颜色：如果是红色，直接删除，不会破坏红黑树；若是黑色，删除后会破坏红黑树的第 5 条性质，需要对
	树做调整。
	if(toDelete->color == BLACK) {
		RB_Delete_Fixup(T,x);
	}
//最终可以彻底删除要删除的结点，释放其占用的空间
	free(toDelete);
}

六 参考

  • C语言中文网—红黑树（更高级的二叉查找树）算法详解