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

    目录

    前言

     一、左旋和右旋

    左旋（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. 将当前节点设为新的父节点的左子节点。

    1. //左旋（以x为旋转点，向左旋转）
    2. void left_rotate(rbtree* T, Node* x) {
    3. 	Node* y = x->right;//标记到右子节点
    4. 	x->right = y->left;//y的左子节点代替x的右子节点
    5. 	if (x->right != T->nil)
    6. 		x->right->par = x;//如果不为空（nil）其父节点指向x
    7. 	y->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了
    8. 	if (x->par == T->nil) {//判断x的父节点是否为根结点
    9. 		T->root = y;//如果是的话，y就变为根结点
    10. 	}
    11. 	else {
    12. 		//y顶替x的位置
    13. 		if (x == x->par->left)
    14. 			x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点
    15. 		else
    16. 			x->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点
    17. 	}
    18. 	//y的左子节点指向x，x的父节点指向y
    19. 	y->left = x;
    20. 	x->par = y;
    21. }

    右旋（Right Rotation） 

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

    操作如下：

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

    1. //右旋（以x为旋转点，向右旋转）
    2. void right_rotate(rbtree* T, Node* x) {
    3. 	Node* y = x->left;//标记到左子节点y
    4. 	x->left = y->right;//y的右子节点代替x的左子节点
    5. 	if (x->left != T->nil)
    6. 		x->left->par = x;
    7. 	y->par = x->par;//y的父节点指向x的父节点
    8. 	if (x->par == T->nil)
    9. 		T->root = y;//如果x是根结点的话，那么y代替x成为根结点
    10. 	else {
    11. 		if (x == x->par->left)
    12. 			x->par->left = y;
    13. 		else
    14. 			x->par->right = y;
    15. 	}
    16. 	//y的右子节点指向x，x的父节点为y
    17. 	y->right = x;
    18. 	x->par = y;
    19. }

     二、红黑树的查找

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

    1. //根据key查找
    2. Node* Search_key(rbtree* T, int target) {
    3. 	assert(T);
    4. 	assert(T->root);
    5. 	Node* cur = T->root;
    6. 	while (cur) {
    7. 		if (cur->key == target)
    8. 			return cur;//找到就返回
    9. 		else if (cur->key > target)
    10. 			cur = cur->left;
    11. 		else
    12. 			cur = cur->right;
    13. 	}
    14. 	printf("The target is not exist\n");
    15. 	return NULL;
    16. }

    三、红黑树的删除

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

    • 删除的是叶子节点（下面又分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节点就转化为上面三大类的删除情况（递归即可）。

    四、完整代码

    1. #include
    2. #include
    3. #include
    4. #include
    5.  
    6. //宏定义颜色
    7. #define red 0
    8. #define black 1
    9.  
    10. //数据类型Datatype
    11. typedef char Datatype;
    12. //红黑树节点存储结构
    13. typedef struct node {
    14. 	Datatype data;
    15. 	int color;
    16. 	int key;
    17. 	struct node* par;//父节点指针
    18. 	struct node* left, * right;//左右子节点指针
    19. }Node;
    20.  
    21. //红黑树的定义rbtree
    22. typedef struct tree {
    23. 	Node* root;//指向根节点指针
    24. 	Node* nil;//叶子节点（哨兵）
    25. }rbtree;
    26.  
    27. //创建初始化红黑树
    28. rbtree* Create_inittree() {
    29. 	rbtree* T = (rbtree*)malloc(sizeof(rbtree));
    30. 	assert(T);
    31. 	T->nil = (Node*)malloc(sizeof(Node));
    32. 	assert(T->nil);
    33. 	//T->nil是不储存数据的节点，作为空节点代替NULL，也就是哨兵节点（表示空）
    34. 	T->nil->color = black;
    35. 	T->nil->par = NULL;
    36. 	T->nil->left = T->nil->right = NULL;
    37. 	T->root = T->nil;
    38. 	return T;
    39. }
    40.  
    41. //创建一个节点
    42. Node* Create_node(rbtree*T ,Datatype data, int key) {
    43. 	Node* new_node = (Node*)malloc(sizeof(Node));
    44. 	assert(new_node);
    45. 	new_node->data = data;
    46. 	new_node->color = red;//初始化颜色红色
    47. 	//左右父节点为nil哨兵节点
    48. 	new_node->left=new_node->right = T->nil;
    49. 	new_node->par = T->nil;
    50. 	new_node->key = key;
    51. 	return new_node;
    52. }
    53.  
    54. //左旋（以x为旋转点，向左旋转）
    55. void left_rotate(rbtree* T, Node* x) {
    56. 	Node* y = x->right;//标记到右子节点
    57. 	x->right = y->left;//y的左子节点代替x的右子节点
    58. 	if (x->right != T->nil)
    59. 		x->right->par = x;//如果不为空（nil）其父节点指向x
    60. 	y->par = x->par;//把y的父节点指向x的父节点，此时x与y没有直接联系了
    61. 	if (x->par == T->nil) {//判断x的父节点是否为根结点
    62. 		T->root = y;//如果是的话，y就变为根结点
    63. 	}
    64. 	else {
    65. 		//y顶替x的位置
    66. 		if (x == x->par->left)
    67. 			x->par->left = y;//如果x是父节点的左边，那y就代替x成为左子节点
    68. 		else
    69. 			x->par->right = y;//如果x是父节点的右边，那y就代替x成为右子节点
    70. 	}
    71. 	//y的左子节点指向x，x的父节点指向y
    72. 	y->left = x;
    73. 	x->par = y;
    74. }
    75. //右旋（以x为旋转点，向右旋转）
    76. void right_rotate(rbtree* T, Node* x) {
    77. 	Node* y = x->left;//标记到左子节点y
    78. 	x->left = y->right;//y的右子节点代替x的左子节点
    79. 	if (x->left != T->nil)
    80. 		x->left->par = x;
    81. 	y->par = x->par;//y的父节点指向x的父节点
    82. 	if (x->par == T->nil)
    83. 		T->root = y;//如果x是根结点的话，那么y代替x成为根结点
    84. 	else {
    85. 		if (x == x->par->left)
    86. 			x->par->left = y;
    87. 		else
    88. 			x->par->right = y;
    89. 	}
    90. 	//y的右子节点指向x，x的父节点为y
    91. 	y->right = x;
    92. 	x->par = y;
    93. }
    94.  
    95. //根据key查找
    96. Node* Search_key(rbtree* T, int target) {
    97. 	assert(T);
    98. 	assert(T->root);
    99. 	Node* cur = T->root;
    100. 	while (cur) {
    101. 		if (cur->key == target)
    102. 			return cur;//找到就返回
    103. 		else if (cur->key > target)
    104. 			cur = cur->left;
    105. 		else
    106. 			cur = cur->right;
    107. 	}
    108. 	printf("The target is not exist\n");
    109. 	return NULL;
    110. }
    111.  
    112. //删除黑色叶子节点调整
    113. void Del_b_adjust(rbtree* T, Node* x) {
    114. 	//被删除节点x父节点的左边
    115. 	if (x == x->par->left) {
    116. 		Node* p = x->par;//父节点
    117. 		Node* b = p->right;//兄弟节点
    118. 		p->left = T->nil;
    119. 		//删除节点x
    120. 		free(x);
    121. 		x = NULL;
    122. 		//1.兄弟节点为黑色
    123. 		if (b->color == black) {
    124. 			//1-1没有侄子节点
    125. 			if (b->left == T->nil && b->right == T->nil) {
    126. 				p->color = black;
    127. 				b->color = red;
    128. 			}
    129. 			//1-2左侄节点红色
    130. 			else if (b->left->color == red && b->right == T->nil) {
    131. 				right_rotate(T, b);
    132. 				b->par->color = p->color;
    133. 				p->color = black;
    134. 				left_rotate(T, p);
    135. 			}
    136. 			//1-3右侄子节点红色
    137. 			else if (b->left == T->nil && b->right->color == red) {
    138. 				b->color = p->color;
    139. 				p->color = black;
    140. 				left_rotate(T, p);
    141. 			}
    142. 			//1-4 两个侄子节都是红色
    143. 			else {
    144. 				left_rotate(T, p);
    145. 				b->color = p->color;
    146. 				b->right->color = black;
    147. 				p->color = black;
    148. 			}
    149. 		}
    150. 		//2.兄弟节点为红色
    151. 		else {
    152. 			left_rotate(T, p);
    153. 			b->color = black;
    154. 			p->right->color = red;
    155. 		}
    156. 	}
    157.  
    158. 	//被删除节点在父节点的右边
    159. 	else {
    160. 		Node* p = x->par;
    161. 		Node* b = p->left;
    162. 		p->right = T->nil;
    163. 		free(x);
    164. 		x = NULL;
    165. 		//1.兄弟节点黑色
    166. 		if (b->color == black) {
    167. 			//1-1没有侄子节点
    168. 			if (b->left == T->nil && b->right == T->nil) {
    169. 				p->color = black;
    170. 				b->color = red;
    171. 			}
    172. 			//1-2兄弟有右子节点
    173. 			else if (b->right->color == red && b->left == T->nil) {
    174. 				left_rotate(T, b);
    175. 				b->par->color = p->color;
    176. 				p->color = black;
    177. 				right_rotate(T, p);
    178. 			}
    179. 			//1-3 兄弟有左子节点
    180. 			else if (b->left->color == red && b->right == T->nil) {
    181. 				b->color = p->color;
    182. 				p->color = black;
    183. 				b->left->color = black;
    184. 				right_rotate(T, p);
    185. 			}
    186. 			//1-4 兄弟有左右子节点
    187. 			else {
    188. 				right_rotate(T, p);
    189. 				b->color = p->color;
    190. 				p->color = black;
    191. 				b->left->color = black;
    192. 			}
    193. 		}
    194. 		//2.兄弟节点为红色
    195. 		else {
    196. 			right_rotate(T, p);
    197. 			b->color = black;
    198. 			p->left->color = red;
    199. 		}
    200. 	}
    201. }
    202. //查找删除替身节点（找后驱）
    203. Node* node_successor(rbtree* T, Node* root) {
    204. 	while (root->left != T->nil)
    205. 		root = root->left;
    206. 	return root;
    207. }
    208. //删除节点操作
    209. void Delete_node(rbtree* T, Node* target) {
    210. 	//1.删除的节点是叶子节点
    211. 	if (target->left == T->nil && target->right == T->nil) {
    212. 		//1-01如果这个节点是红色节点
    213. 		if (target->color == red) {
    214. 			if (target == target->par->left)
    215. 				target->par->left = T->nil;
    216. 			else
    217. 				target->par->right = T->nil;
    218. 			free(target);
    219. 			target = NULL;
    220. 		}
    221. 		//1-02 如果是黑色叶子节点进入到调整
    222. 		else
    223. 			Del_b_adjust(T, target);
    224. 	}
    225. 	//2.删除的只有一个左孩子的节点
    226. 	else if (target->left != T->nil && target->right == T->nil) {
    227. 		Node* lc = target->left;
    228. 		target->data = lc->data;
    229. 		target->key = lc->key;
    230. 		target->left = T->nil;
    231. 		free(lc);
    232. 		lc = NULL;
    233. 	}
    234. 	//3.删除的只有一个右孩子的节点
    235. 	else if (target->left == T->nil && target->right != T->nil) {
    236. 		Node* rc = target->right;
    237. 		target->data = rc->data;
    238. 		target->key = rc->key;
    239. 		target->right = T->nil;
    240. 		free(rc);
    241. 		rc = NULL;
    242. 	}
    243. 	//4.删除的节点有左右孩子
    244. 	else {
    245. 		Node* sub = node_successor(T, target->right);//找到替代者
    246. 		target->data = sub->data;
    247. 		target->key = sub->key;
    248. 		Delete_node(T, sub);//递归进入到前三种删除方式
    249. 	}
    250.  
    251. 	T->root->color = black;//根结点为黑色
    252. }

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

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

    分享一张壁纸：

  • 相关阅读:
    企业知识库构建：关于企业知识库及知识平台搭建的重要性！
    在CentOS编译Git源码
    J9数字论：最近爆火的Web3.0到底是什么？
    java计算机毕业设计基于springboo+vue的人事管理系统
    【Git】 git push 提示Not possible to fast-forward，无法提交也无法提交程序
    数字IC后端实现 |TSMC 12nm 与TSMC 28nm Metal Stack的区别
    js图片url反转file文件 vue
    个人信息保护视域下知情同意框架的应用困境与对策探析
    一种计算整数位1个数的新方法
    拔河攻略要点
  • 原文地址：https://blog.csdn.net/m0_73633088/article/details/133881888