• 数据结构-----红黑树的插入

    目录

    前言

    红黑树的储存结构

     一、节点旋转操作

    左旋（Left Rotation）

    右旋（Right Rotation） 

    二、插入节点

    1.插入的是空树

    2.插入节点的key重新重复

    3.插入节点的父节点是黑色

    4.插入节点的父节点是红色

    4.1父节点是祖父节点的左子节点

    4.1.1叔叔节点是红色 

     4.1.2叔叔节点是黑色

    4.1.2-1 插入节点是作左子节点

    4.1.2-2插入节点是作右子节点

     4.2父节点是祖父节点的右子节点

    4.2.1叔叔节点是红色

    4.2.2 叔叔节点是黑色

    4.2.1-1 插入节点是作左子节点

    4.2.1-2 插入节点是作右子节点

    三、完整代码展示

    前言

            上一期我们初步学习了红黑树的基本概念和特性（上一期链接：数据结构-----红黑树简介_Gretel Tade的博客-CSDN博客 如果不了解红黑树相关性质的话建议看看这个），那么从这一期开始，我们就进入到了红黑树的深入学习，首先我通过这一期来详细介绍红黑树的插入操作实现，下面就看看怎么去把数据插入到红黑树吧！

    红黑树的储存结构

     根据红黑树的要求，我们可以去定义红黑树节点和树的结构体，如下所示：

    1. //宏定义颜色
    2. #define red 0
    3. #define black 1
    4.  
    5. //数据类型Datatype
    6. typedef char Datatype;
    7. //红黑树节点存储结构
    8. typedef struct node {
    9. 	Datatype data;
    10. 	int color;
    11. 	int key;//排序键值，根据key大小排序
    12. 	struct node* par;//父节点指针
    13. 	struct node* left, * right;//左右子节点指针
    14. }Node;
    15.  
    16. //红黑树的定义rbtree
    17. typedef struct tree {
    18. 	Node* root;//指向根节点指针
    19. 	Node* nil;//叶子节点（哨兵）
    20. }rbtree;

     一、节点旋转操作

    在数据结构当中，旋转操作是一种很常见的操作，可能去实现数据结构平衡或者其他相关特性的要求，同样的的AVL树和红黑树里边也是要进行旋转操作的，通过旋转来满足平衡的特性。旋转分两种：左旋（Left Rotation）和右旋（Right Rotation）

    左旋（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. }

    二、插入节点

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

     废话不多说了，上正文！

    红黑树的插入操作分两步走：

    • 找到插入位置
    • 进行自平衡调整

     注意：插入节点初始为红色

    原因分析：因为红黑树中任意一个节点到叶子节点路径所含黑色节点数量相同，也就是说如果我插入的节点为黑色的话，那么就会破坏红黑树的要求，所以插入的节点必须是红色节点，才能保证红黑树的性质。

    下面就开始讨论红黑树的几种插入情况：

    1.插入的是空树

    这是最简单的插入情况，当插入第一个节点的时候，红黑树为空我们只需要让根节点指向这个节点即可。操作如下：

    1. 根节点指向此节点
    2. 把根节点染黑

    2.插入节点的key重新重复

    这种情况的话我们可以根据自己喜好去处理，如果出现了重复的key，那么就把这个key里面的值进行更新；或者我们不进行插入操作，因为key不可以重复，直接退出插入操作。

    3.插入节点的父节点是黑色

    这很好处理，直接插入就行了，因为父节点为黑色，插入节点为红色，所以不会影响红黑树的平衡性。

    1. 直接插入即可

    4.插入节点的父节点是红色

    这种情况是最为复杂的，由于父节点颜色是红色，所以要进行平衡调整，所以要去进一步的讨论才行。那具体根据什么去调整呢？是看叔叔节点的颜色来调整（父节点的兄弟节点），具体分以下几种情况：

     大的有两种情况，要看父节点是祖父节点的左边还是右边，下面我就以父节点为左子节点为例子：

     下文图标说明：

    t 表示插入的节点

    P表示父节点

    B表示叔叔节点

    PP表示祖父节点

    4.1父节点是祖父节点的左子节点
    4.1.1叔叔节点是红色 

    如果叔叔节点的颜色是红色的话，这里不需要进行旋转操作，只需要让父节点和叔叔节点颜色变为黑色，祖父节点颜色变为红色即可。流程如下：

    • 把P 和B 节点染黑
    • 把PP节点染红

     4.1.2叔叔节点是黑色

    这里的话又要去分两种情况：

    1. 插入节点是父节点的左子节点
    2. 插入节点是父节点的右子节点
    4.1.2-1 插入节点是作左子节点

     如果插入的节点是父节点的左子节点的话，那么要进行以下操作：

    • 把P染黑
    • 把PP染红
    • 对PP进行右旋

    4.1.2-2插入节点是作右子节点

     如果插入节点是作为父节点的右子节点的话，要进行以下操作：

    • 对P进行左旋
    • 把t 染黑
    • 把PP染红
    • 对PP进行右旋

     4.2父节点是祖父节点的右子节点

    这里的操作跟4.1基本上是一模一样的，只是对称过去是了，但是我还是想详细列出来吧，下面接着看。

    4.2.1叔叔节点是红色

    操作步骤如下：

    • 把B（叔叔节点）和P（父节点）然黑
    • 把PP（祖父节点）染红

    4.2.2 叔叔节点是黑色

    同样的也是分以下两种情况讨论： 

    4.2.1-1 插入节点是作左子节点
    •  对P 进行右旋
    • 将t 染黑
    • 将PP 然红
    • 对PP 进行左旋

    4.2.1-2 插入节点是作右子节点
    •  将P 染黑
    • 将PP 然红
    • 对PP进行左旋

     以上这些就是红黑树的插入全部可能了，是不是很多啊，其实还好啦！只要我们把这些情况一个一个分类，然后思路捋一捋很容易弄明白的，后面讲到红黑树的删除还有更多种情况呢！还有就是，这些图片是我自己画的，呃画得不太好，不好意思哈。

    三、完整代码展示

    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. //插入后平衡调整
    96. void Insert_adjust(rbtree* T, Node* t) {
    97. 	//如果父节点的颜色是红色那就进行调整操作了
    98. 	if (t->par->color == red) {
    99. 		Node* p = t->par;
    100. 		Node* pp = p->par;
    101. 		//01 p节点是pp左子节点
    102. 		if (p == pp->left) {
    103. 			Node* uncle = pp->right;
    104. 			//01-1 叔叔节点颜色是红色
    105. 			if (uncle->color == red) {
    106. 				p->color = black;
    107. 				uncle->color = black;
    108. 				pp->color = red;
    109. 				t = pp;
    110. 			}
    111. 			//01-2 叔叔节点颜色是黑色
    112. 			else {
    113. 				//01-2-1 插入节点t是p的左子节点
    114. 				if (t == p->left) {
    115. 					p->color = black;
    116. 					pp->color = red;
    117. 					right_rotate(T, pp);
    118. 					t = p;
    119. 				}
    120. 				//01-2-2 插入节点t是p的右子节点
    121. 				else if(t==p->right){
    122. 					left_rotate(T, p);
    123. 					t->color = black;
    124. 					pp->color = red;
    125. 					right_rotate(T, pp);
    126. 				}
    127. 			}
    128. 		}
    129. 		//02 p节点是pp的右子节点
    130. 		else {		
    131. 			Node* uncle = pp->left;
    132. 			//02-1 叔叔节点颜色是红色
    133. 			if (uncle->color == red) {
    134. 				pp->color = red;
    135. 				p->color = black;
    136. 				uncle->color = black;
    137. 				t = pp;
    138. 			}
    139. 			//02-2 叔叔节点颜色是黑色
    140. 			else {
    141. 				//02-2-1 插入节点t是p的右子节点
    142. 				if (t == p->right) {
    143. 					p->color = black;
    144. 					pp->color = red;
    145. 					left_rotate(T,pp);
    146. 					t = p;
    147. 				}
    148. 				//02-2-2 插入节点t是p的左子节点
    149. 				else {
    150. 					right_rotate(T, p);
    151. 					t->color = black;
    152. 					pp->color = red;
    153. 					left_rotate(T, pp);
    154. 				}
    155. 			}
    156. 		}
    157. 	}
    158. 	//根节点标记黑色
    159. 	T->root->color = black;
    160. }
    161.  
    162. //插入节点
    163. void Insert_node(rbtree* T, Datatype data,int key) {
    164. 	assert(T);
    165. 	Node* t = Create_node(T ,data, key);
    166. 	Node* root = T->root;//快指针
    167. 	Node* cur=T->nil;//慢指针
    168. 	//1.如果根节点为空
    169. 	if (T->root==T->nil) {
    170. 		T->root = t;//根结点指向新创建的节点
    171. 	}
    172. 	else {
    173. 		while (root != T->nil) {
    174. 			cur = root;//cur标记为root的上一个节点（父节点）
    175. 			if (t->key > root->key)
    176. 				root = root->right;
    177. 			else if (t->key < root->key)
    178. 				root = root->left;
    179. 			//如果出现插入重复的key值，就退出，不进行插入操作
    180. 			else {
    181. 				printf("Don't insert the same key!\n");
    182. 				free(t);
    183. 				t = NULL;
    184. 				return;
    185. 			}
    186. 		}
    187. 	}
    188. 	//判断插入的位置
    189. 	if (key < cur->key)
    190. 		cur->left = t;//小的话就插入左边
    191. 	else
    192. 		cur->right = t;//大的话就插入右边
    193. 	t->par = cur;//新插入的父节点指针指向cur
    194. 	Insert_adjust(T, t);//平衡调整
    195. }

     单单值考虑插入操作就有两百多行代码，后面还有删除操作，查找操作，总共的话大概400行代码，这里就先发今天所讲的插入操作内容的代码，注释很详细，慢慢看哈，我相信你一点看得懂的！

    以上就是本期的全部内容了，我们下一期讲红黑树的删除操作，下次见！

    分享一张壁纸： 

  • 相关阅读:
    About-Flink
    2022年下半年信息系统项目管理师综合知识真题及答案1-20
    JDK21的虚拟线程是什么？和平台线程什么关系？
    Java File分隔符和 Path分隔符
    七、使用kubeadm搭建生产环境单master多node节点的k8s集群
    NLP领域可以投稿的期刊（2022整理）
    latex左侧大括号 latex中大括号多行公式
    图像去雾易语言代码
    双非本23秋招之路-从考研跑路到某安全大厂（无实习、项目）
    如何使用Python实现发送邮件功能
  • 原文地址：https://blog.csdn.net/m0_73633088/article/details/133863827