• C++简单实现红黑树

    目录

    一、概念

    二、红黑树的性质

    三、红黑树的定义

    四、红黑树的插入操作

    情况一（叔叔节点存在且为红色）——变色+向上调整：

    情况二（叔叔节点不存在或为黑色）——旋转+变色：

    2.1叔叔节点不存在

    2.2叔叔节点为黑色

    插入的代码实现：

    五、红黑树的验证

    六、红黑树完整代码

    一、概念

    红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
    Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
    径会比其他路径长出俩倍，因而是接近平衡的。

    二、红黑树的性质

    1. 每个结点不是红色就是黑色
    2. 根节点是黑色的
    3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的
    4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
    5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点）

    三、红黑树的定义

    1. enum Colour
    2. {
    3. 	RED,BLACK
    4. };
    5.  
    6. template<class K, class V>
    7. struct RBTreeNode
    8. {
    9. 	RBTreeNode(const pair& kv)
    10. 		:_kv(kv)
    11. 		,_right(nullptr)
    12. 		,_left(nullptr)
    13. 		,_parent(nullptr)
    14. 		,_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响
    15. 	{}
    16.  
    17. 	pair _kv;
    18. 	RBTreeNode* _right;
    19. 	RBTreeNode* _left;
    20. 	RBTreeNode* _parent;
    21. 	
    22. 	Colour _col;
    23. };

    C++STL中的set和map底层就是使用红黑树实现的，而map是存放键值对的，所以我们给红黑树的节点中的值存放一个键值对，以及左右孩子的指针和指向父节点的指针，还有一个存放颜色的标记。

    四、红黑树的插入操作

    红黑树的插入首先和普通二叉搜索树的插入操作一样，新建一个节点，左节点的值小于根，右节点的值大于根，找到位置进行插入。插入后应如果破坏了红黑树的性质，就需要进行调整。

    因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
    性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
    在一起的红色节点，此时需要对红黑树分情况来讨论：

    我们给出一个约定：cur为当前节点，p为父亲节点，g为祖父节点，u为叔叔节点

    情况一（叔叔节点存在且为红色）——变色+向上调整：

    将p和u改成黑色，将g改为红色

    此时有三种情况：

    1、g没有父亲节点，直接变成黑色就可以，插入结束；

    2、g有父亲节点，且父亲为黑色，插入结束；

    3、g有父亲节点，且父亲为红色（违反了红色节点不能连续的性质），需要向上调整。

    情况二（叔叔节点不存在或为黑色）——旋转+变色：

    2.1叔叔节点不存在

    如果cur在parent的左边——右旋：

    cur在parent的右边——先左旋再右旋：

    2.2叔叔节点为黑色

    如果cur在parent的左边——右旋：

    cur在parent的右边——先左旋再右旋：

    以上插入操作是p在g节点左边的情况，p在g节点右边的情况与以上插入过程类似，仅仅是镜像翻转一下。

    插入的代码实现：

    左旋代码：

    1. void RotateL(Node* parent)
    2. 	{
    3. 		Node* cur = parent->_right;
    4. 		Node* curleft = cur->_left;
    5.  
    6. 		parent->_right = curleft;
    7. 		cur->_left = parent;
    8. 		if (curleft)
    9. 			curleft->_parent = parent;
    10.  
    11. 		Node* ppnode = parent->_parent;
    12. 		parent->_parent = cur;
    13.  
    14. 		if (parent == _root)
    15. 		{
    16. 			cur->_parent = nullptr;
    17. 			_root = cur;
    18. 		}
    19. 		else
    20. 		{
    21. 			if (ppnode->_left == parent)
    22. 			{
    23. 				ppnode->_left = cur;
    24. 			}
    25. 			else
    26. 			{
    27. 				ppnode->_right = cur;
    28. 			}
    29. 			cur->_parent = ppnode;
    30. 		}
    31. 	}

    右旋代码：

    1. void RotateR(Node* parent)
    2. 	{
    3. 		Node* cur = parent->_left;
    4. 		Node* curright = cur->_right;
    5.  
    6. 		parent->_left = curright;
    7. 		cur->_right = parent;
    8.  
    9. 		if (curright)
    10. 			curright->_parent = parent;
    11.  
    12. 		Node* ppnode = parent->_parent;
    13. 		parent->_parent = cur;
    14.  
    15. 		if (parent == _root)
    16. 		{
    17. 			cur->_parent = nullptr;
    18. 			_root = cur;
    19. 		}
    20. 		else
    21. 		{
    22. 			if (ppnode->_left == parent)
    23. 			{
    24. 				ppnode->_left = cur;
    25. 			}
    26. 			else
    27. 			{
    28. 				ppnode->_right = cur;
    29. 			}
    30. 			cur->_parent = ppnode;
    31. 		}
    32. 	}

    插入代码：

    1.     bool insert(const pair& kv)
    2. 	{
    3. 		//如果root为空
    4. 		if (_root == nullptr)
    5. 		{
    6. 			_root = new Node(kv);
    7. 			_root->_col = BLACK;
    8. 			return true;
    9. 		}
    10. 		//插入
    11. 		Node* cur = _root;
    12. 		Node* parent = cur;
    13.  
    14. 		while (cur)
    15. 		{
    16. 			if (cur->_kv.first < kv.first)
    17. 			{
    18. 				parent = cur;
    19. 				cur = cur->_right;
    20. 			}
    21. 			else if (cur->_kv.first > kv.first)
    22. 			{
    23. 				parent = cur;
    24. 				cur = cur->_left;
    25. 			}
    26. 			else
    27. 			{
    28. 				return false;
    29. 			}
    30. 		}
    31. 		cur = new Node(kv);//插入节点
    32.  
    33. 		if (parent->_kv.first < kv.first)
    34. 		{
    35. 			parent->_right = cur;
    36. 		}
    37. 		else
    38. 		{
    39. 			parent->_left = cur;
    40. 		}
    41. 		cur->_parent = parent;
    42.  
    43. 		//插入完毕，开始调整颜色
    44. 		while (parent && parent->_col == RED)
    45. 		{
    46. 			Node* grandfather = parent->_parent;
    47. 			//叔叔在右
    48. 			if (grandfather->_left == parent)
    49. 			{
    50. 				Node* uncle = grandfather->_right;
    51.  
    52. 				//叔叔存在且为红色——变色
    53. 				if (uncle && uncle->_col == RED)
    54. 				{
    55. 					parent->_col = BLACK;
    56. 					uncle->_col = BLACK;
    57. 					grandfather->_col = RED;
    58.  
    59. 					//向上更新
    60. 					cur = grandfather;
    61. 					parent = cur->_parent;
    62. 				}
    63. 				//叔叔不存在或者为黑色——旋转+变色
    64. 				else
    65. 				{
    66. 					//右单旋即可
    67. 					if (parent->_left == cur)
    68. 					{
    69. 						RotateR(grandfather);
    70. 						//变色
    71. 						parent->_col = BLACK;
    72. 						grandfather->_col = RED;
    73. 					}
    74. 					//先左单旋，后右单旋
    75. 					else
    76. 					{
    77. 						RotateL(parent);
    78. 						RotateR(grandfather);
    79. 						//变色
    80. 						cur->_col = BLACK;
    81. 						grandfather->_col = RED;
    82. 					}
    83. 					break;
    84. 				}
    85. 			}
    86. 			//叔叔在左
    87. 			else
    88. 			{
    89. 				Node* uncle = grandfather->_left;
    90. 				//uncle存在且为红色——变色
    91. 				if (uncle && uncle->_col == RED)
    92. 				{
    93. 					parent->_col = BLACK;
    94. 					uncle->_col = BLACK;
    95. 					grandfather->_col = RED;
    96.  
    97. 					//向上更新
    98. 					cur = grandfather;
    99. 					parent = cur->_parent;
    100. 				}
    101. 				//uncle不存在或为黑色——旋转+变色
    102. 				else
    103. 				{
    104. 					//左单旋即可
    105. 					if (parent->_right == cur)
    106. 					{
    107. 						RotateL(grandfather);
    108. 						//变色
    109. 						grandfather->_col = RED;
    110. 						parent->_col = BLACK;
    111. 					}
    112. 					//先右单旋，再左单旋
    113. 					else
    114. 					{
    115. 						RotateR(parent);
    116. 						RotateL(grandfather);
    117. 						//变色
    118. 						cur->_col = BLACK;
    119. 						grandfather->_col = RED;
    120. 					}
    121. 					break;
    122. 				}
    123. 			}
    124. 		}
    125.  
    126. 		_root->_col = BLACK;
    127.  
    128. 		return true;
    129. 	}

    五、红黑树的验证

    1.     bool isBalance()
    2. 	{
    3. 		return _isBalance(_root);
    4. 	}
    5.  
    6.     bool checkcolour(Node* root, int benckmark, int blackcount)
    7. 	{
    8. 		if (root == nullptr)
    9. 		{
    10. 			if (blackcount != benckmark)
    11. 				return false;
    12. 			return true;
    13. 		}
    14. 		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    15. 			return false;
    16. 		if (root->_col == BLACK)
    17. 			++benckmark;
    18. 		return checkcolour(root->_left, benckmark, blackcount)
    19. 			&& checkcolour(root->_right, benckmark, blackcount);
    20. 	}
    21.  
    22. 	bool _isBalance(Node* root)
    23. 	{
    24. 		if (root == nullptr)
    25. 			return true;
    26.  
    27. 		if (root->_col != BLACK)
    28. 			return false;
    29. 		Node* cur = root;
    30.  
    31.         //求树中最左路径黑色节点的个数
    32. 		while (cur)
    33. 		{
    34. 			if (cur->_col == BLACK)
    35. 				++blackcount;
    36. 			cur = cur->_left;
    37. 		}
    38. 		return checkcolour(_root, 0, blackcount);
    39. 	}

    六、红黑树完整代码

    1. #pragma once
    2.  
    3. #include 
    4. #include 
    5. using namespace std;
    6.  
    7. enum Colour
    8. {
    9. 	RED,BLACK
    10. };
    11.  
    12. template<class K, class V>
    13. struct RBTreeNode
    14. {
    15. 	RBTreeNode(const pair& kv)
    16. 		:_kv(kv)
    17. 		,_right(nullptr)
    18. 		,_left(nullptr)
    19. 		,_parent(nullptr)
    20. 		,_col(RED)//默认插入节点为红色，如果为黑色，就会对其他路径也造成影响
    21. 	{}
    22.  
    23. 	pair _kv;
    24. 	RBTreeNode* _right;
    25. 	RBTreeNode* _left;
    26. 	RBTreeNode* _parent;
    27. 	
    28. 	Colour _col;
    29. };
    30. /*
    31. * 红黑树插入思路——关键在于uncle节点：
    32. * 分为两大类：
    33. * 一、如果uncle存在且为红色——仅仅变色即可
    34. * 
    35. *	       g(黑)                            g(红)     
    36. *     p(红)     u(红)    ------->       p(黑)      u(黑) ------->继续向上更新
    37. *  c(红)                            c(红)
    38. * 
    39. * 
    40. * 二、如果uncle不存在或为黑色——旋转加变色
    41. * 
    42. * 情况一：       g(黑)                              p(红)
    43. *            p(红)    NULL/黑  ------->       c(红)       g(黑)
    44. *         c(红)
    45. * 
    46. *        仅仅右旋即可，g变成红色; p变成黑色;  break;
    47. * 
    48. * 情况二：       g(黑)                                  g(黑)                c(红)
    49. *			 p(红)    NULL/黑  ------->   先左旋     c(红)    ------->   p(红)    g(黑) 
    50. *               c(红)                             p(红)
    51. * 
    52. *        c变成黑色，g变成红色，break;
    53. * 
    54. * 情况三：情况一的对称图形
    55. * 情况四：情况二的对称图形
    56. * 
    57. */
    58. template<class K, class V>
    59. class RBTree
    60. {
    61. 	typedef RBTreeNode Node;
    62. public:
    63. 	RBTree()
    64. 		:_root(nullptr)
    65. 	{}
    66.  
    67. 	void InOrder()
    68. 	{
    69. 		cout << "InOrder: ";
    70. 		_InOrder(_root);
    71. 		cout << endl;
    72. 	}
    73.  
    74. 	bool insert(const pair& kv)
    75. 	{
    76. 		//如果root为空
    77. 		if (_root == nullptr)
    78. 		{
    79. 			_root = new Node(kv);
    80. 			_root->_col = BLACK;
    81. 			return true;
    82. 		}
    83. 		//插入
    84. 		Node* cur = _root;
    85. 		Node* parent = cur;
    86.  
    87. 		while (cur)
    88. 		{
    89. 			if (cur->_kv.first < kv.first)
    90. 			{
    91. 				parent = cur;
    92. 				cur = cur->_right;
    93. 			}
    94. 			else if (cur->_kv.first > kv.first)
    95. 			{
    96. 				parent = cur;
    97. 				cur = cur->_left;
    98. 			}
    99. 			else
    100. 			{
    101. 				return false;
    102. 			}
    103. 		}
    104. 		cur = new Node(kv);//插入节点
    105.  
    106. 		if (parent->_kv.first < kv.first)
    107. 		{
    108. 			parent->_right = cur;
    109. 		}
    110. 		else
    111. 		{
    112. 			parent->_left = cur;
    113. 		}
    114. 		cur->_parent = parent;
    115.  
    116. 		//插入完毕，开始调整颜色
    117. 		while (parent && parent->_col == RED)
    118. 		{
    119. 			Node* grandfather = parent->_parent;
    120. 			//叔叔在右
    121. 			if (grandfather->_left == parent)
    122. 			{
    123. 				Node* uncle = grandfather->_right;
    124.  
    125. 				//叔叔存在且为红色——变色
    126. 				if (uncle && uncle->_col == RED)
    127. 				{
    128. 					parent->_col = BLACK;
    129. 					uncle->_col = BLACK;
    130. 					grandfather->_col = RED;
    131.  
    132. 					//向上更新
    133. 					cur = grandfather;
    134. 					parent = cur->_parent;
    135. 				}
    136. 				//叔叔不存在或者为黑色——旋转+变色
    137. 				else
    138. 				{
    139. 					//右单旋即可
    140. 					if (parent->_left == cur)
    141. 					{
    142. 						RotateR(grandfather);
    143. 						//变色
    144. 						parent->_col = BLACK;
    145. 						grandfather->_col = RED;
    146. 					}
    147. 					//先左单旋，后右单旋
    148. 					else
    149. 					{
    150. 						RotateL(parent);
    151. 						RotateR(grandfather);
    152. 						//变色
    153. 						cur->_col = BLACK;
    154. 						grandfather->_col = RED;
    155. 					}
    156. 					break;
    157. 				}
    158. 			}
    159. 			//叔叔在左
    160. 			else
    161. 			{
    162. 				Node* uncle = grandfather->_left;
    163. 				//uncle存在且为红色——变色
    164. 				if (uncle && uncle->_col == RED)
    165. 				{
    166. 					parent->_col = BLACK;
    167. 					uncle->_col = BLACK;
    168. 					grandfather->_col = RED;
    169.  
    170. 					//向上更新
    171. 					cur = grandfather;
    172. 					parent = cur->_parent;
    173. 				}
    174. 				//uncle不存在或为黑色——旋转+变色
    175. 				else
    176. 				{
    177. 					//左单旋即可
    178. 					if (parent->_right == cur)
    179. 					{
    180. 						RotateL(grandfather);
    181. 						//变色
    182. 						grandfather->_col = RED;
    183. 						parent->_col = BLACK;
    184. 					}
    185. 					//先右单旋，再左单旋
    186. 					else
    187. 					{
    188. 						RotateR(parent);
    189. 						RotateL(grandfather);
    190. 						//变色
    191. 						cur->_col = BLACK;
    192. 						grandfather->_col = RED;
    193. 					}
    194. 					break;
    195. 				}
    196. 			}
    197. 		}
    198.  
    199. 		_root->_col = BLACK;
    200.  
    201. 		return true;
    202. 	}
    203.  
    204. 	bool isBalance()
    205. 	{
    206. 		return _isBalance(_root);
    207. 	}
    208.  
    209. private:
    210.  
    211. 	bool checkcolour(Node* root, int benckmark, int blackcount)
    212. 	{
    213. 		if (root == nullptr)
    214. 		{
    215. 			if (blackcount != benckmark)
    216. 				return false;
    217. 			return true;
    218. 		}
    219. 		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    220. 			return false;
    221. 		if (root->_col == BLACK)
    222. 			++benckmark;
    223. 		return checkcolour(root->_left, benckmark, blackcount)
    224. 			&& checkcolour(root->_right, benckmark, blackcount);
    225. 	}
    226.  
    227. 	bool _isBalance(Node* root)
    228. 	{
    229. 		if (root == nullptr)
    230. 			return true;
    231.  
    232. 		if (root->_col != BLACK)
    233. 			return false;
    234. 		Node* cur = root;
    235. 		while (cur)
    236. 		{
    237. 			if (cur->_col == BLACK)
    238. 				++blackcount;
    239. 			cur = cur->_left;
    240. 		}
    241. 		return checkcolour(_root, 0, blackcount);
    242. 	}
    243.  
    244. 	void RotateL(Node* parent)
    245. 	{
    246. 		Node* cur = parent->_right;
    247. 		Node* curleft = cur->_left;
    248.  
    249. 		parent->_right = curleft;
    250. 		cur->_left = parent;
    251. 		if (curleft)
    252. 			curleft->_parent = parent;
    253.  
    254. 		Node* ppnode = parent->_parent;
    255. 		parent->_parent = cur;
    256.  
    257. 		if (parent == _root)
    258. 		{
    259. 			cur->_parent = nullptr;
    260. 			_root = cur;
    261. 		}
    262. 		else
    263. 		{
    264. 			if (ppnode->_left == parent)
    265. 			{
    266. 				ppnode->_left = cur;
    267. 			}
    268. 			else
    269. 			{
    270. 				ppnode->_right = cur;
    271. 			}
    272. 			cur->_parent = ppnode;
    273. 		}
    274. 	}
    275.  
    276. 	void RotateR(Node* parent)
    277. 	{
    278. 		Node* cur = parent->_left;
    279. 		Node* curright = cur->_right;
    280.  
    281. 		parent->_left = curright;
    282. 		cur->_right = parent;
    283.  
    284. 		if (curright)
    285. 			curright->_parent = parent;
    286.  
    287. 		Node* ppnode = parent->_parent;
    288. 		parent->_parent = cur;
    289.  
    290. 		if (parent == _root)
    291. 		{
    292. 			cur->_parent = nullptr;
    293. 			_root = cur;
    294. 		}
    295. 		else
    296. 		{
    297. 			if (ppnode->_left == parent)
    298. 			{
    299. 				ppnode->_left = cur;
    300. 			}
    301. 			else
    302. 			{
    303. 				ppnode->_right = cur;
    304. 			}
    305. 			cur->_parent = ppnode;
    306. 		}
    307. 	}
    308.  
    309. 	void _InOrder(Node* root)
    310. 	{
    311. 		if (root == nullptr)
    312. 			return;
    313. 		_InOrder(root->_left);
    314. 		cout << root->_kv.first << " ";
    315. 		_InOrder(root->_right);
    316. 	}
    317. private:
    318. 	Node* _root;
    319. 	int blackcount = 0;
    320. };

    测试：

    运行结果：

    之后更新红黑树的应用，用红黑树封装map和set。

  • 相关阅读:
    UE5场景逐渐变亮问题
    【FLASH存储器系列二】非易失性存储器基本原理之EEPROM和FLASH
    网络安全（黑客）自学
    Java 数据结构 ---》 泛型
    Springboot:如何搭建起自己第一个Springboot项目
    TYUT太原理工大学2022需求工程考试简答题
    【无标题】小程序条件判断wx:if=“{{indexof.checkFunDic(item.settingId,‘2‘)}}“
    Python爬虫 -- Selenium库的使用
    循序渐进介绍基于CommunityToolkit.Mvvm 和HandyControl的WPF应用端开发(2)
    【每日训练】连续最大和
  • 原文地址：https://blog.csdn.net/weixin_50601177/article/details/133386765