• 数据结构 红黄树 学习笔记

    首先我们了解一下红黑树的性质:

     

    在我们编写红黑树添加函数ADDRBT()之前   我们先编写几个工具函数 

    RBT* GetFather(RBT* pRoot, int id)       获得当前节点的父亲

    1. RBT* GetFather(RBT* pRoot, int id)
    2. {
    3. 	if (pRoot == NULL)
    4. 	{
    5. 		return nullptr;
    6. 	}
    7. 	while (pRoot != NULL)
    8. 	{
    9. 		if (pRoot->id > id)
    10. 		{
    11. 			if (pRoot->pLeft == NULL)
    12. 			{
    13. 				return pRoot;
    14. 			}
    15. 			pRoot = pRoot->pLeft;
    16.  
    17. 		}
    18. 		else if (pRoot->id < id)
    19. 		{
    20. 			if (pRoot->pRight == NULL)
    21. 			{
    22. 				return pRoot;
    23. 			}
    24. 			pRoot = pRoot->pRight;
    25.  
    26. 		}
    27. 		else
    28. 		{
    29. 			
    30. 			break;
    31. 		}
    32. 	}
    33. 	return nullptr;
    34. }

    RBT* GetUncle(RBT* pRoot)                   获得当前节点的叔叔

    1. RBT* GetUncle(RBT* pRoot)
    2. {
    3. 	if (pRoot == NULL || pRoot->pFather == NULL || pRoot->pFather->pFather == NULL)
    4. 	{
    5. 		return nullptr;
    6. 	}
    7. 	else
    8. 	{
    9. 		if (pRoot->pFather->pFather->pLeft == pRoot->pFather)
    10. 		{
    11. 			return pRoot->pFather->pFather->pRight;
    12. 		}
    13. 		else
    14. 		{
    15. 			return pRoot->pFather->pFather->pLeft;
    16. 		}
    17. 	}
    18.  
    19.  
    20. }

    void RightRotate(RBT* pRBT,RBT*& pBoot)     右旋当前节点

    1. void RightRotate(RBT* pRBT, RBT*& pBoot)
    2. {
    3. 	if (pRBT == nullptr || pRBT->pLeft == nullptr)
    4. 	{
    5. 		return;
    6. 	}
    7. 	//标记不平衡节点  A
    8. 	RBT* pMark = pRBT;
    9. 	//标记不平衡节点的左  B
    10. 	RBT* pTemp = pRBT->pLeft;
    11. 	//x  pMark->pFather   E   pTemp->pRight
    12.  
    13. 	//三个孩子
    14. 	//不平衡节点的左->不平衡节点的 左的右   A->左=E 
    15. 	pMark->pLeft = pTemp->pRight;
    16. 	//不平衡节点左的右->不平衡节点       B->右=A
    17. 	pTemp->pRight = pMark;
    18. 	//不平衡节点是不是根
    19.  
    20. 	  //是  不平衡的节点变为根
    21. 	if (pMark->pFather == nullptr)
    22. 	{
    23. 		pBoot = pTemp;
    24. 	}
    25. 	//不是 判断不平衡节点是父亲的左还是右   (A是父亲的左还是右)
    26. 	else
    27. 	{
    28. 		//左:
    29. 		  //不平衡节点的父亲的左孩子->不平衡节点   X->左=B
    30. 		if (pMark->pFather->pLeft == pMark)
    31. 		{
    32. 			pMark->pFather->pLeft = pTemp;
    33. 		}
    34. 		//右:
    35. 		  //不平衡节点的父亲的右孩子->不平衡节点   X->右=B
    36. 		else
    37. 		{
    38. 			pMark->pFather->pRight = pTemp;
    39. 		}
    40. 	}
    41.  
    42. 	if (pMark->pLeft != nullptr)
    43. 	{
    44. 		pMark->pLeft->pFather = pMark;
    45. 	}
    46.  
    47. 	pTemp->pFather = pMark->pFather;
    48.  
    49. 	pMark->pFather = pTemp;
    50. }

    void LeftRotate(RBT* pRBT, RBT*& pBoot)       左旋当前节点

    1. void LeftRotate(RBT* pRBT, RBT*& pBoot)
    2.  
    3. {
    4. 	if (pRBT == nullptr || pRBT->pRight == nullptr)
    5. 	{
    6. 		return;
    7. 	}
    8.  
    9. 	RBT* pMark = pRBT;
    10.  
    11. 	RBT* pTemp = pRBT->pRight;
    12.  
    13.  
    14. 	pMark->pRight = pTemp->pLeft;
    15.  
    16. 	pTemp->pLeft = pMark;
    17.  
    18.  
    19.  
    20. 	if (pMark->pFather == nullptr)
    21. 	{
    22. 		pBoot = pTemp;
    23. 	}
    24. 	else
    25. 	{
    26.  
    27. 		if (pMark->pFather->pLeft == pMark)
    28. 		{
    29. 			pMark->pFather->pLeft = pTemp;
    30. 		}
    31.  
    32. 		else
    33. 		{
    34. 			pMark->pFather->pRight = pTemp;
    35.  
    36. 		}
    37.  
    38. 	}
    39.  
    40.  
    41.  
    42. 	if (pMark->pRight != nullptr)
    43. 	{
    44. 		pMark->pRight->pFather = pMark;
    45. 	}
    46.  
    47. 	pTemp->pFather = pMark->pFather;
    48.  
    49. 	pMark->pFather = pTemp;
    50.  
    51.  
    52.  
    53.  
    54.  
    55. }
    56.  
    57.

    然后我们开始定义  void AddRBT(RBT*& rpBoot, int id)函数

    思想:

     

    首先  我们把思路列出来 如下列代码注释

    1. void AddRBT(RBT*& rpBoot, int id)
    2. {
    3. 	RBT* pFather = GetFather(rpBoot, id);
    4. 	RBT* pMark = new RBT;
    5. 	pMark->color = RED;
    6. 	pMark->id = id;
    7. 	pMark->pFather = pFather;
    8.  
    9. 	pMark->pLeft = NULL;
    10. 	pMark->pRight = NULL;
    11.  
    12.  
    13. 	//判断根是否为空
    14.   //空  pMark赋给根
    15. 	if (rpBoot == NULL)
    16. 	{
    17. 		pMark->color = BLACK;
    18. 		rpBoot = pMark;
    19. 		return;
    20. 	}
    21. 	//非空  添加
    22. 	if (pFather->id > pMark->id)
    23. 	{
    24. 		pFather->pLeft = pMark;
    25. 	}
    26. 	else
    27. 	{
    28. 		pFather->pRight = pMark;
    29. 	}
    30. 	//分析
    31. 	while (1)
    32. 	{
    33. 		//先给pFather和pUncle重新赋值
    34. 		pFather = pMark->pFather;
    35.  
    36. 		//判断父亲的颜色
    37. 		  //黑 直接加
    38.  
    39. 		if (pFather->color == BLACK)
    40. 		{
    41. 			return;
    42. 		}
    43. 		RBT* pUncle = GetUncle(pMark);
    44. 		//父亲为红 判断叔叔的颜色
    45.  
    46.  
    47. 			//叔叔为红
    48. 			  //父亲和叔叔都变黑
    49. 				//爷爷变红
    50. 				   //判断爷爷是否为根 
    51. 					 //为根 爷爷变黑
    52. 					 //不为根  爷爷赋给标记  结束当前循环  重新对爷爷进行分析
    53.  
    54.  
    55. 		if (pUncle != nullptr && pUncle->color == RED)
    56. 		{
    57. 			pFather->color = BLACK;
    58. 			pUncle->color = BLACK;
    59.  
    60. 			pFather->pFather->color = RED;
    61. 			pMark = pFather->pFather;
    62.  
    63. 			if (pMark->pFather == NULL)
    64. 			{
    65. 				pMark->color = BLACK;
    66. 				return;
    67. 			}
    68. 			continue;
    69.  
    70. 		}
    71. 		//叔叔为黑 (包含空)
    72. 		if (pUncle == NULL||pUncle->color==BLACK)
    73.  
    74. 		{
    75. 			
    76. 			  //判断父亲是爷爷的左还是右孩子
    77. 				//左 判断标记是父亲的左还是由节点
    78. 				  //左 爷爷变红 父亲变黑   对爷爷节点右旋  结束
    79.  
    80. 				  //右 爷爷变红 父亲赋值给标记 对标记左旋
    81.  
    82. 				//右 判断标记是父亲的左还是由节点
    83. 				  //右 爷爷变红 父亲变黑   对爷爷节点左旋  结束
    84.  
    85. 				  //左 爷爷变红 父亲赋值给标记 对标记右旋
    86.  
    87. 			if (pFather == pFather->pFather->pLeft)
    88. 			{
    89. 				if (pFather->pRight == pMark)
    90. 				{
    91.  
    92. 					pMark = pFather;
    93.  
    94. 					LeftRotate(pMark, rpBoot);
    95.  
    96. 				}
    97.  
    98. 				else
    99.  
    100. 				{
    101.  
    102. 					pMark->pFather->pFather->color = RED;
    103.  
    104. 					pMark->pFather->color = BLACK;
    105.  
    106. 					RightRotate(pMark->pFather->pFather, rpBoot);
    107.  
    108. 					return;
    109.  
    110. 				}
    111.  
    112. 			}
    113. 			//右
    114. 			if (pFather == pFather->pFather->pRight)
    115.  
    116. 			{
    117.  
    118.  
    119. 				if (pFather->pLeft == pMark)
    120.  
    121. 				{
    122.  
    123. 					pMark = pFather;
    124.  
    125. 					RightRotate(pMark, rpBoot);
    126.  
    127. 				}
    128.  
    129. 				else
    130.  
    131. 				{
    132.  
    133. 					pMark->pFather->pFather->color = RED;
    134. 					pMark->pFather->color = BLACK;
    135. 					LeftRotate(pMark->pFather->pFather, rpBoot);
    136.  
    137. 					return;
    138.  
    139.  
    140. 				}
    141.  
    142.  
    143.  
    144.  
    145. 			}
    146.  
    147.  
    148.  
    149. 		}
    150.  
    151. 	}
    152.  
    153. }

    delete函数思想:

     

    代码

    1.  
    2. RBT* GetDeleteNode(RBT* rpBoot, int id)
    3. {
    4. 	while (rpBoot)
    5. 	{
    6. 		if (id > rpBoot->id)
    7. 		{
    8.  
    9. 			rpBoot = rpBoot->pRight;
    10. 		}
    11. 		else if (id < rpBoot->id)
    12. 		{
    13.  
    14. 			rpBoot = rpBoot->pLeft;
    15. 		}
    16. 		else if(id == rpBoot->id)
    17. 		{
    18. 			return rpBoot;
    19. 		}
    20. 	}
    21. 	return NULL;
    22. }
    23.  
    24. void DeteleRBT(RBT*& rpBoot, int nId)
    25. {
    26.  
    27.  
    28. 	RBT* pDel = GetDeleteNode(rpBoot, nId);
    29.  
    30. 	if (pDel == NULL)
    31. 	{
    32. 		return;
    33. 	}
    34.  
    35. 	if (pDel->pLeft != NULL && pDel->pRight != NULL)
    36. 	{
    37. 		RBT* pMark = pDel;
    38. 		
    39. 			pDel = pDel->pRight;
    40. 			while (pDel->pLeft!=NULL)
    41. 			{
    42. 				pDel = pDel->pLeft;
    43. 			}
    44. 			
    45. 		
    46. 		
    47. 		pMark->id = pDel->id;
    48. 	}
    49. 	
    50. 	
    51.  
    52. 	if (pDel->pFather == NULL)
    53. 		//根
    54. 	{
    55. 		if (pDel->pLeft == NULL && pDel->pRight == NULL)
    56. 			//判断有没有一个孩子
    57. 		{
    58. 			rpBoot = NULL;
    59. 			//没有孩子
    60. 			
    61. 		}
    62. 		else
    63. 			
    64. 		{
    65. 			//有孩子
    66. 			rpBoot = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
    67. 			rpBoot->color = BLACK;
    68. 			rpBoot->pFather = NULL;
    69. 			
    70. 		}
    71. 		delete pDel;
    72. 		pDel = NULL;
    73. 		return;
    74. 	}
    75. 	
    76. 	RBT* pFather =pDel->pFather;
    77. 		//非根
    78. 		//分析节点颜色
    79. 	
    80.  
    81. 		if (pDel->color == RED)
    82. 			//红  直接删
    83. 		{
    84.  
    85. 			if (pDel == pFather->pLeft)
    86. 			{
    87. 				pFather->pLeft = NULL;
    88. 			}
    89. 			else
    90. 			{
    91. 				pFather->pRight = NULL;
    92. 			}
    93. 			delete pDel;
    94. 			pDel = NULL;
    95. 			return;
    96. 		}
    97. 		
    98. 			//黑  判断节点是否有孩子
    99. 		
    100. 			if (pDel->pLeft != NULL || pDel->pRight != NULL)
    101. 				//有孩子  一定是红孩子
    102. 			{ 
    103.  
    104. 				
    105. 					//红孩子变黑  与爷爷相连
    106. 					RBT* pChild = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
    107. 					pChild->color = BLACK;
    108. 					pChild->pFather = pFather;
    109. 					if (pFather->pLeft==pDel)  
    110. 					{
    111. 						pFather->pLeft = pChild;
    112. 					}
    113. 					else
    114. 					{
    115. 						pFather->pRight = pChild;
    116. 					}
    117. 					delete pDel;
    118. 					pDel = NULL;
    119. 					return;
    120. 				
    121. 				
    122. 					
    123. 				
    124. 			}
    125. 			
    126. 		
    127. 			
    128. 				//没孩子
    129. 				//先获得兄弟  删除节点
    130. 					RBT* pBrother = GetBrother(pDel);
    131. 					if (pFather->pLeft == pDel)
    132. 					{
    133. 						pFather->pLeft = NULL;
    134. 					}
    135. 					else 
    136. 					{
    137. 						pFather->pRight = NULL;
    138. 					}
    139. 					
    140.  
    141.  
    142. 					//分析兄弟颜色 loop
    143. 					while (1)
    144.  
    145. 					{
    146.  
    147.  
    148. 						if (pBrother->color == RED)
    149. 							//兄弟为红
    150. 						{
    151. 							//父亲变红  兄弟变黑  分析兄弟方向
    152. 							pFather->color = RED;
    153. 							pBrother->color = BLACK;
    154. 							if (pFather->pLeft == pBrother)//兄弟为父亲的左  
    155. 							{
    156. 								//以父亲为支点  右旋
    157. 								RightRotate(pFather, rpBoot);
    158. 								pBrother = pFather->pLeft;
    159.  
    160. 							}
    161. 							else //兄弟为父亲的右
    162. 							{
    163. 								//以父亲为支点  左旋
    164. 								LeftRotate(pFather, rpBoot);
    165. 								pBrother = pFather->pRight;
    166.  
    167. 							}
    168. 							continue;
    169. 						}
    170.  
    171. 						if (pBrother->color == BLACK)
    172. 							//兄弟为黑 
    173. 							 // 分析两个侄子的颜色
    174.  
    175. 						{
    176. 							if ((pBrother->pLeft == NULL && pBrother->pRight == NULL) ||
    177. 								((pBrother->pLeft != NULL && pBrother->pLeft->color == BLACK) &&
    178. 									(pBrother->pRight != NULL && pBrother->pRight->color == BLACK)))
    179. 							{
    180. 								//两个侄子全黑(包括全为空)  分析父亲颜色
    181. 								if (pFather->color == RED)
    182. 								{
    183. 									//父亲为红  :父亲变黑  兄弟变红 结束
    184. 									pFather->color = BLACK;
    185. 									pBrother->color = RED;
    186. 									return;
    187. 								}
    188. 								else
    189. 								{
    190. 									//父亲为黑  : 兄弟变红  父亲为新的标记 更换兄弟 标记为根的时候结束 不为根继续分析
    191.  
    192. 									pBrother->color = RED;
    193. 									pDel = pFather;
    194.  
    195. 									if (pDel->pFather == NULL)
    196. 									{
    197. 										return;
    198. 									}
    199.  
    200. 									continue;
    201.  
    202. 								}
    203. 							}
    204. 							//左侄子红右侄子黑(空)  分析兄弟方向
    205. 							if ((pBrother->pLeft != NULL && pBrother->pLeft->color == RED) &&
    206. 								(pBrother->pRight == NULL || pBrother->pRight->color == BLACK))
    207. 							{
    208. 								//兄弟是父亲的右  兄弟变红  左侄子变黑  一兄弟为支点右旋 继续分析
    209. 								if (pBrother == pFather->pRight)
    210. 								{
    211. 									pBrother->color = RED;
    212. 									pBrother->pLeft->color = BLACK;
    213. 									RightRotate(pBrother, rpBoot);
    214. 									pBrother = pFather->pRight;
    215. 									continue;
    216. 								}
    217. 								//兄弟是父亲的左 父亲的颜色给兄弟 父亲变黑 左侄子变黑 以父亲为支点右旋 结束
    218. 								if (pFather->pLeft == pBrother)
    219. 								{
    220. 									pBrother->color = pFather->color;
    221. 									pFather->color = BLACK;
    222. 									pBrother->pLeft->color = BLACK;
    223. 									RightRotate(pFather, rpBoot);
    224. 									return;
    225. 								}
    226. 							}
    227.  
    228. 							//右侄子红  分析兄弟方向
    229. 							if (pBrother->pRight != NULL && pBrother->pRight->color == RED)
    230. 								//兄弟是父亲的左  兄弟变红  右侄子变黑 以兄弟为支点左旋  继续分析
    231. 								if (pBrother == pFather->pLeft)
    232. 								{
    233. 									pBrother->color = RED;
    234. 									pBrother->pRight->color = BLACK;
    235. 									LeftRotate(pBrother, rpBoot);
    236. 									pBrother = pFather->pLeft;
    237. 									continue;
    238. 								}
    239. 							//兄弟是父亲的右 父亲的颜色给兄弟 父亲变黑 右侄子变黑 以父亲为支点左旋 结束
    240. 							if (pFather->pRight == pBrother)
    241. 							{
    242. 								pBrother->color = pFather->color;
    243. 								pFather->color = BLACK;
    244. 								pBrother->pRight->color = BLACK;
    245. 								LeftRotate(pFather, rpBoot);
    246. 								return;
    247. 							}
    248. 						}
    249.  
    250. 					}
    251. 			
    252. 		
    253. }
    254.  
    255.  
    256. 	
    257.

    主函数中我们进行测试:

    1. RBT* Boot = NULL;
    2.  
    3. 	int arr[] = { 11,2,14,1,7,15,5 ,8};
    4. 	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    5. 	{
    6. 		AddRBT(Boot, arr[i]);
    7. 	}
    8. 	inorder(Boot);
    9. 	cout << "----------" << endl;
    10. 	AddRBT(Boot, 4);
    11. 	/*RBT* pBrother = GetBrother(Boot->pRight);
    12. 	cout << pBrother->id << endl;*/
    13. 	inorder(Boot);
    14. 	cout << "----------" << endl;
    15. 	
    16. 	//DeteleRBT(Boot, 1);
    17. 	DeteleRBT(Boot,8);
    18. 	inorder(Boot);
    19. 	return 0;

    这里我们添加了节点4   删除了节点8

    执行结果如下:

     

     

    完整代码如下

    1. #include
    2. #include
    3. using namespace std;
    4. //1.红黑树中所有的节点但不是红的就是黑的
    5. //2.
    6.  
    7. enum COLOR { RED, BLACK };
    8. struct RBT
    9. {
    10. 	int id;
    11. 	RBT* pLeft;
    12. 	RBT* pRight;
    13. 	RBT* pFather;
    14. 	COLOR color;
    15.  
    16. };
    17.  
    18. RBT* GetFather(RBT* pRoot, int id)
    19. {
    20. 	if (pRoot == NULL)
    21. 		{
    22. 			return nullptr;
    23. 		}
    24. 	while (pRoot != NULL)
    25. 	{
    26. 		
    27. 		if (pRoot->id > id)
    28. 		{
    29. 			
    30. 			if (pRoot->pLeft == NULL)
    31. 			{
    32. 				return pRoot;
    33. 			}
    34. 			pRoot = pRoot->pLeft;
    35.  
    36. 		}
    37. 		else if (pRoot->id < id)
    38. 		{
    39. 			if (pRoot->pRight == NULL)
    40. 			{
    41. 				return pRoot;
    42. 			}
    43. 			pRoot = pRoot->pRight;
    44.  
    45. 		}
    46. 		else
    47. 		{
    48. 			cout << "不允许添加值相同的节点,数据有误" << endl;
    49. 			break;
    50. 		}
    51. 	}
    52. 	return nullptr;
    53. }
    54.  
    55. RBT* GetUncle(RBT* pRoot)
    56. {
    57. 	if (pRoot == NULL || pRoot->pFather == NULL || pRoot->pFather->pFather == NULL)
    58. 	{
    59. 		return nullptr;
    60. 	}
    61. 	
    62. 		if (pRoot->pFather->pFather->pLeft == pRoot->pFather)
    63. 		{
    64. 			return pRoot->pFather->pFather->pRight;
    65. 		}
    66. 		else
    67. 		{
    68. 			return pRoot->pFather->pFather->pLeft;
    69. 		}
    70. 	
    71.  
    72. }
    73.  
    74. void RightRotate(RBT* pRBT, RBT*& pBoot)
    75. {
    76. 	if (pRBT == nullptr || pRBT->pLeft == nullptr)
    77. 	{
    78. 		return;
    79. 	}
    80. 	//标记不平衡节点  A
    81. 	RBT* pMark = pRBT;
    82. 	//标记不平衡节点的左  B
    83. 	RBT* pTemp = pRBT->pLeft;
    84. 	//x  pMark->pFather   E   pTemp->pRight
    85.  
    86. 	//三个孩子
    87. 	//不平衡节点的左->不平衡节点的 左的右   A->左=E 
    88. 	pMark->pLeft = pTemp->pRight;
    89. 	//不平衡节点左的右->不平衡节点       B->右=A
    90. 	pTemp->pRight = pMark;
    91. 	//不平衡节点是不是根
    92.  
    93. 	  //是  不平衡的节点变为根
    94. 	if (pMark->pFather == nullptr)
    95. 	{
    96. 		pBoot = pTemp;
    97. 	}
    98. 	//不是 判断不平衡节点是父亲的左还是右   (A是父亲的左还是右)
    99. 	else
    100. 	{
    101. 		//左:
    102. 		  //不平衡节点的父亲的左孩子->不平衡节点   X->左=B
    103. 		if (pMark->pFather->pLeft == pMark)
    104. 		{
    105. 			pMark->pFather->pLeft = pTemp;
    106. 		}
    107. 		//右:
    108. 		  //不平衡节点的父亲的右孩子->不平衡节点   X->右=B
    109. 		else
    110. 		{
    111. 			pMark->pFather->pRight = pTemp;
    112. 		}
    113. 	}
    114.  
    115. 	if (pMark->pLeft != nullptr)
    116. 	{
    117. 		pMark->pLeft->pFather = pMark;
    118. 	}
    119.  
    120. 	pTemp->pFather = pMark->pFather;
    121.  
    122. 	pMark->pFather = pTemp;
    123. }
    124.  
    125.  
    126. void LeftRotate(RBT* pRBT, RBT*& pBoot)
    127.  
    128. {
    129. 	if (pRBT == nullptr || pRBT->pRight == nullptr)
    130. 	{
    131. 		return;
    132. 	}
    133.  
    134. 	RBT* pMark = pRBT;
    135.  
    136. 	RBT* pTemp = pRBT->pRight;
    137.  
    138.  
    139. 	pMark->pRight = pTemp->pLeft;
    140.  
    141. 	pTemp->pLeft = pMark;
    142.  
    143.  
    144.  
    145. 	if (pMark->pFather == nullptr)
    146. 	{
    147. 		pBoot = pTemp;
    148. 	}
    149. 	else
    150. 	{
    151.  
    152. 		if (pMark->pFather->pLeft == pMark)
    153. 		{
    154. 			pMark->pFather->pLeft = pTemp;
    155. 		}
    156.  
    157. 		else
    158. 		{
    159. 			pMark->pFather->pRight = pTemp;
    160.  
    161. 		}
    162.  
    163. 	}
    164.  
    165.  
    166.  
    167. 	if (pMark->pRight != nullptr)
    168. 	{
    169. 		pMark->pRight->pFather = pMark;
    170. 	}
    171.  
    172. 	pTemp->pFather = pMark->pFather;
    173.  
    174. 	pMark->pFather = pTemp;
    175.  
    176.  
    177.  
    178.  
    179.  
    180. }
    181.  
    182.  
    183. void AddRBT(RBT*& rpBoot, int id)
    184. {
    185. 	RBT* pFather = GetFather(rpBoot, id);
    186. 	RBT* pMark = new RBT;
    187. 	pMark->color = RED;
    188. 	pMark->id = id;
    189. 	pMark->pFather = pFather;
    190.  
    191. 	pMark->pLeft = NULL;
    192. 	pMark->pRight = NULL;
    193.  
    194.  
    195. 	//判断根是否为空
    196.   //空  pMark赋给根
    197. 	if (rpBoot == NULL)
    198. 	{
    199. 		pMark->color = BLACK;
    200. 		rpBoot = pMark;
    201. 		return;
    202. 	}
    203. 	//非空  添加
    204. 	if (pFather->id > pMark->id)
    205. 	{
    206. 		pFather->pLeft = pMark;
    207. 	}
    208. 	else
    209. 	{
    210. 		pFather->pRight = pMark;
    211. 	}
    212. 	//分析
    213. 	while (1)
    214. 	{
    215. 		//先给pFather和pUncle重新赋值
    216. 		pFather = pMark->pFather;
    217.  
    218. 		//判断父亲的颜色
    219. 		  //黑 直接加
    220.  
    221. 		if (pFather->color == BLACK)
    222. 		{
    223. 			return;
    224. 		}
    225. 		RBT* pUncle = GetUncle(pMark);
    226. 		//父亲为红 判断叔叔的颜色
    227.  
    228.  
    229. 			//叔叔为红
    230. 			  //父亲和叔叔都变黑
    231. 				//爷爷变红
    232. 				   //判断爷爷是否为根 
    233. 					 //为根 爷爷变黑
    234. 					 //不为根  爷爷赋给标记  结束当前循环  重新对爷爷进行分析
    235.  
    236.  
    237. 		if (pUncle != nullptr && pUncle->color == RED)
    238. 		{
    239. 			pFather->color = BLACK;
    240. 			pUncle->color = BLACK;
    241.  
    242. 			pFather->pFather->color = RED;
    243. 			pMark = pFather->pFather;
    244.  
    245. 			if (pMark->pFather == NULL)
    246. 			{
    247. 				pMark->color = BLACK;
    248. 				return;
    249. 			}
    250. 			continue;
    251.  
    252. 		}
    253. 		//叔叔为黑 (包含空)
    254. 		if (pUncle == NULL||pUncle->color==BLACK)
    255.  
    256. 		{
    257. 			
    258. 			  //判断父亲是爷爷的左还是右孩子
    259. 				//左 判断标记是父亲的左还是由节点
    260. 				  //左 爷爷变红 父亲变黑   对爷爷节点右旋  结束
    261.  
    262. 				  //右 爷爷变红 父亲赋值给标记 对标记左旋
    263.  
    264. 				//右 判断标记是父亲的左还是由节点
    265. 				  //右 爷爷变红 父亲变黑   对爷爷节点左旋  结束
    266.  
    267. 				  //左 爷爷变红 父亲赋值给标记 对标记右旋
    268.  
    269. 			if (pFather == pFather->pFather->pLeft)
    270. 			{
    271. 				if (pFather->pRight == pMark)
    272. 				{
    273.  
    274. 					pMark = pFather;
    275.  
    276. 					LeftRotate(pMark, rpBoot);
    277.  
    278. 				}
    279.  
    280. 				else
    281.  
    282. 				{
    283.  
    284. 					pMark->pFather->pFather->color = RED;
    285.  
    286. 					pMark->pFather->color = BLACK;
    287.  
    288. 					RightRotate(pMark->pFather->pFather, rpBoot);
    289.  
    290. 					return;
    291.  
    292. 				}
    293.  
    294. 			}
    295. 			//右
    296. 			if (pFather == pFather->pFather->pRight)
    297.  
    298. 			{
    299.  
    300.  
    301. 				if (pFather->pLeft == pMark)
    302.  
    303. 				{
    304.  
    305. 					pMark = pFather;
    306.  
    307. 					RightRotate(pMark, rpBoot);
    308.  
    309. 				}
    310.  
    311. 				else
    312.  
    313. 				{
    314.  
    315. 					pMark->pFather->pFather->color = RED;
    316. 					pMark->pFather->color = BLACK;
    317. 					LeftRotate(pMark->pFather->pFather, rpBoot);
    318.  
    319. 					return;
    320.  
    321.  
    322. 				}
    323.  
    324.  
    325.  
    326.  
    327. 			}
    328.  
    329.  
    330.  
    331. 		}
    332.  
    333. 	}
    334.  
    335. }
    336.  
    337. RBT* GetBrother(RBT* rpBoot)
    338. {
    339. 	if (rpBoot == NULL || rpBoot->pFather == NULL)
    340. 		
    341. 	{
    342.  
    343. 		return NULL;
    344. 	}
    345. 	return rpBoot == rpBoot->pFather->pLeft ? rpBoot->pFather->pRight : rpBoot->pFather->pLeft;
    346.  
    347. }
    348. RBT* GetDeleteNode(RBT* rpBoot, int id)
    349. {
    350. 	while (rpBoot)
    351. 	{
    352. 		if (id > rpBoot->id)
    353. 		{
    354.  
    355. 			rpBoot = rpBoot->pRight;
    356. 		}
    357. 		else if (id < rpBoot->id)
    358. 		{
    359.  
    360. 			rpBoot = rpBoot->pLeft;
    361. 		}
    362. 		else if(id == rpBoot->id)
    363. 		{
    364. 			return rpBoot;
    365. 		}
    366. 	}
    367. 	return NULL;
    368. }
    369.  
    370. void DeteleRBT(RBT*& rpBoot, int nId)
    371. {
    372.  
    373.  
    374. 	RBT* pDel = GetDeleteNode(rpBoot, nId);
    375.  
    376. 	if (pDel == NULL)
    377. 	{
    378. 		return;
    379. 	}
    380.  
    381. 	if (pDel->pLeft != NULL && pDel->pRight != NULL)
    382. 	{
    383. 		RBT* pMark = pDel;
    384. 		
    385. 			pDel = pDel->pRight;
    386. 			while (pDel->pLeft!=NULL)
    387. 			{
    388. 				pDel = pDel->pLeft;
    389. 			}
    390. 			
    391. 		
    392. 		
    393. 		pMark->id = pDel->id;
    394. 	}
    395. 	
    396. 	
    397.  
    398. 	if (pDel->pFather == NULL)
    399. 		//根
    400. 	{
    401. 		if (pDel->pLeft == NULL && pDel->pRight == NULL)
    402. 			//判断有没有一个孩子
    403. 		{
    404. 			rpBoot = NULL;
    405. 			//没有孩子
    406. 			
    407. 		}
    408. 		else
    409. 			
    410. 		{
    411. 			//有孩子
    412. 			rpBoot = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
    413. 			rpBoot->color = BLACK;
    414. 			rpBoot->pFather = NULL;
    415. 			
    416. 		}
    417. 		delete pDel;
    418. 		pDel = NULL;
    419. 		return;
    420. 	}
    421. 	
    422. 	RBT* pFather =pDel->pFather;
    423. 		//非根
    424. 		//分析节点颜色
    425. 	
    426.  
    427. 		if (pDel->color == RED)
    428. 			//红  直接删
    429. 		{
    430.  
    431. 			if (pDel == pFather->pLeft)
    432. 			{
    433. 				pFather->pLeft = NULL;
    434. 			}
    435. 			else
    436. 			{
    437. 				pFather->pRight = NULL;
    438. 			}
    439. 			delete pDel;
    440. 			pDel = NULL;
    441. 			return;
    442. 		}
    443. 		
    444. 			//黑  判断节点是否有孩子
    445. 		
    446. 			if (pDel->pLeft != NULL || pDel->pRight != NULL)
    447. 				//有孩子  一定是红孩子
    448. 			{ 
    449.  
    450. 				
    451. 					//红孩子变黑  与爷爷相连
    452. 					RBT* pChild = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
    453. 					pChild->color = BLACK;
    454. 					pChild->pFather = pFather;
    455. 					if (pFather->pLeft==pDel)  
    456. 					{
    457. 						pFather->pLeft = pChild;
    458. 					}
    459. 					else
    460. 					{
    461. 						pFather->pRight = pChild;
    462. 					}
    463. 					delete pDel;
    464. 					pDel = NULL;
    465. 					return;
    466. 				
    467. 				
    468. 					
    469. 				
    470. 			}
    471. 			
    472. 		
    473. 			
    474. 				//没孩子
    475. 				//先获得兄弟  删除节点
    476. 					RBT* pBrother = GetBrother(pDel);
    477. 					if (pFather->pLeft == pDel)
    478. 					{
    479. 						pFather->pLeft = NULL;
    480. 					}
    481. 					else 
    482. 					{
    483. 						pFather->pRight = NULL;
    484. 					}
    485. 					
    486.  
    487.  
    488. 					//分析兄弟颜色 loop
    489. 					while (1)
    490.  
    491. 					{
    492.  
    493.  
    494. 						if (pBrother->color == RED)
    495. 							//兄弟为红
    496. 						{
    497. 							//父亲变红  兄弟变黑  分析兄弟方向
    498. 							pFather->color = RED;
    499. 							pBrother->color = BLACK;
    500. 							if (pFather->pLeft == pBrother)//兄弟为父亲的左  
    501. 							{
    502. 								//以父亲为支点  右旋
    503. 								RightRotate(pFather, rpBoot);
    504. 								pBrother = pFather->pLeft;
    505.  
    506. 							}
    507. 							else //兄弟为父亲的右
    508. 							{
    509. 								//以父亲为支点  左旋
    510. 								LeftRotate(pFather, rpBoot);
    511. 								pBrother = pFather->pRight;
    512.  
    513. 							}
    514. 							continue;
    515. 						}
    516.  
    517. 						if (pBrother->color == BLACK)
    518. 							//兄弟为黑 
    519. 							 // 分析两个侄子的颜色
    520.  
    521. 						{
    522. 							if ((pBrother->pLeft == NULL && pBrother->pRight == NULL) ||
    523. 								((pBrother->pLeft != NULL && pBrother->pLeft->color == BLACK) &&
    524. 									(pBrother->pRight != NULL && pBrother->pRight->color == BLACK)))
    525. 							{
    526. 								//两个侄子全黑(包括全为空)  分析父亲颜色
    527. 								if (pFather->color == RED)
    528. 								{
    529. 									//父亲为红  :父亲变黑  兄弟变红 结束
    530. 									pFather->color = BLACK;
    531. 									pBrother->color = RED;
    532. 									return;
    533. 								}
    534. 								else
    535. 								{
    536. 									//父亲为黑  : 兄弟变红  父亲为新的标记 更换兄弟 标记为根的时候结束 不为根继续分析
    537.  
    538. 									pBrother->color = RED;
    539. 									pDel = pFather;
    540.  
    541. 									if (pDel->pFather == NULL)
    542. 									{
    543. 										return;
    544. 									}
    545.  
    546. 									continue;
    547.  
    548. 								}
    549. 							}
    550. 							//左侄子红右侄子黑(空)  分析兄弟方向
    551. 							if ((pBrother->pLeft != NULL && pBrother->pLeft->color == RED) &&
    552. 								(pBrother->pRight == NULL || pBrother->pRight->color == BLACK))
    553. 							{
    554. 								//兄弟是父亲的右  兄弟变红  左侄子变黑  一兄弟为支点右旋 继续分析
    555. 								if (pBrother == pFather->pRight)
    556. 								{
    557. 									pBrother->color = RED;
    558. 									pBrother->pLeft->color = BLACK;
    559. 									RightRotate(pBrother, rpBoot);
    560. 									pBrother = pFather->pRight;
    561. 									continue;
    562. 								}
    563. 								//兄弟是父亲的左 父亲的颜色给兄弟 父亲变黑 左侄子变黑 以父亲为支点右旋 结束
    564. 								if (pFather->pLeft == pBrother)
    565. 								{
    566. 									pBrother->color = pFather->color;
    567. 									pFather->color = BLACK;
    568. 									pBrother->pLeft->color = BLACK;
    569. 									RightRotate(pFather, rpBoot);
    570. 									return;
    571. 								}
    572. 							}
    573.  
    574. 							//右侄子红  分析兄弟方向
    575. 							if (pBrother->pRight != NULL && pBrother->pRight->color == RED)
    576. 								//兄弟是父亲的左  兄弟变红  右侄子变黑 以兄弟为支点左旋  继续分析
    577. 								if (pBrother == pFather->pLeft)
    578. 								{
    579. 									pBrother->color = RED;
    580. 									pBrother->pRight->color = BLACK;
    581. 									LeftRotate(pBrother, rpBoot);
    582. 									pBrother = pFather->pLeft;
    583. 									continue;
    584. 								}
    585. 							//兄弟是父亲的右 父亲的颜色给兄弟 父亲变黑 右侄子变黑 以父亲为支点左旋 结束
    586. 							if (pFather->pRight == pBrother)
    587. 							{
    588. 								pBrother->color = pFather->color;
    589. 								pFather->color = BLACK;
    590. 								pBrother->pRight->color = BLACK;
    591. 								LeftRotate(pFather, rpBoot);
    592. 								return;
    593. 							}
    594. 						}
    595.  
    596. 					}
    597. 			
    598. 		
    599. }
    600.  
    601.  
    602. 	
    603.  
    604.  
    605.  
    606. ostream& operator <<(ostream& os, COLOR color)
    607. {
    608. 	if (color == RED)
    609. 	{
    610. 		os << "红";
    611. 	}
    612. 	if (color == BLACK)
    613. 	{
    614. 		os << "黑";
    615. 	}
    616. 	return os;
    617. }
    618.  
    619.  
    620. void inorder(RBT*& Boot)
    621. {
    622. 	if (Boot == NULL)
    623. 	{
    624.  
    625. 		return;
    626. 	}
    627. 	inorder(Boot->pLeft);
    628. 	cout << Boot->id << " " << Boot->color << endl;
    629. 	inorder(Boot->pRight);
    630. }
    631.  
    632.  
    633. int main()
    634. {
    635. 	RBT* Boot = NULL;
    636.  
    637. 	int arr[] = { 11,2,14,1,7,15,5 ,8};
    638. 	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
    639. 	{
    640. 		AddRBT(Boot, arr[i]);
    641. 	}
    642. 	inorder(Boot);
    643. 	cout << "----------" << endl;
    644. 	AddRBT(Boot, 4);
    645. 	/*RBT* pBrother = GetBrother(Boot->pRight);
    646. 	cout << pBrother->id << endl;*/
    647. 	inorder(Boot);
    648. 	cout << "----------" << endl;
    649. 	//存疑 :
    650. 	// Add节点4 之后  8的节点的父亲应该是11  代码中的8 的父亲是7  未能找到原因  ??
    651. 	//  解决这个问题  代码就差不多没问题了
    652. 	//DeteleRBT(Boot, 1);
    653. 	DeteleRBT(Boot,7);
    654. 	inorder(Boot);
    655. 	return 0;
    656. }

  • 相关阅读:
    【leetcode】206. 反转链表 （简单）
    Element的MessageBox自定义图标
    win安装vue并运行 vue-admin-template
    Fiddler入门：下载、安装、配置、抓包、customize rules
    sap业务伙伴分组后台配置的问题
    Chrome iframe 跨域失败
    [c/c++进阶必刷题(一)]
    Java毕业设计-快递物流管理系统
    云原生：使用HPA和VPA实现集群扩缩容
    LeetCode 901. 股票价格跨度【单调栈】1708
  • 原文地址：https://blog.csdn.net/van9527/article/details/125819553