devbox
寸_铁
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++数据结构——红黑树_c++中的红黑树是什么?

作者：寸_铁 | 2024-08-08 07:45:55

赞

踩

c++中的红黑树是什么?

前言：本篇文章我们继续来分享C++中的另一个复杂数据结构——红黑树。

目录

一.红黑树概念

二.红黑树性质

三.红黑树实现

1.基本框架

2.插入

3.判断平衡

 四.完整代码

总结

一.红黑树概念

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

二.红黑树性质

  1. 每个结点不是红色就是黑色

  2. 根节点是黑色的

  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（不存在连续的红色节点） 

  4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路径都存在相同数量的黑色节点） 

  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点NULL)

如何理解红黑树最长路径不超过最短路径的二倍呢？？？

  1.  从性质能够看出，红黑树每一条路径上，都有相同数量的黑色节点。
  2. 红黑树每条路径上可以存在连续的黑色节点，但不能存在连续的红色节点。
  3. 所以最短路径即为全是黑色节点的路径。
  4. 最长路径则为一黑一红相间的路径。

三.红黑树实现

1.基本框架

红黑树与AVL树相比，多了节点颜色这一信息，为了实现这一信息，我们使用枚举：

  1. enum Colour
  2. {
  3. 	RED,
  4. 	BLACK
  5. };
  6.  
  7. template<class K,class V>
  8. struct RBTreeNode
  9. {
  10. 	RBTreeNode<K, V>* _left;
  11. 	RBTreeNode<K, V>* _right;
  12. 	RBTreeNode<K, V>* _parent;
  13.  
  14. 	pair<K, V> _kv;
  15. 	Colour _col;
  16.  
  17. 	RBTreeNode(const pair<K, V>& kv)
  18. 		:_left(nullptr)
  19. 		, _right(nullptr)
  20. 		, _parent(nullptr)
  21. 		, _kv(kv)
  22. 		,_col(RED)
  23. 	{}
  24. };
  25. template<class K, class V>
  26. class RBTree
  27. {
  28. 	typedef RBTreeNode<K, V> Node;
  29. public:
  30.  
  31. private:
  32. 	Node* _root = nullptr;
  33. 	size_t _size = 0;
  34. };

同时我们多创建一个_size成员变量，用于记录节点数量。 

2.插入

红黑树插入的基本步骤与二叉搜索树和AVL树一样，都是按照左子节点比根节点小，右子节点比根节点大的规则，唯一不同的是，红黑树的插入要考虑其性质。其中最值得注意的性质为：

  1. 不存在连续的红节点
  2. 每条路径上的黑节点数相等

 其中能够看出，第二条才是最关键的，因此我们每次新插入节点时，必须插入红节点。

此时我们会面临两种情况：

  1. 父节点为黑色，插入即结束，无需调整。
  2. 父节点为红色，不满足上述性质1，需要调整。

下面我们来看特殊情况：

父亲为红节点，那么只有将父节点变为黑色节点，才能够满足性质。

但是如果父亲变为黑节点，就说明该路径上同样多出一个黑节点，而唯一的处理手段，就是让父亲的父亲，也就是爷爷节点，变为红色节点。

此时又存在问题，那就是关于父亲的兄弟节点，也就是叔叔节点，那么叔叔节点存在三种情况：

  1. 叔叔节点同样为红色。
  2. 叔叔节点不存在。
  3. 叔叔节点为黑色。

如果叔叔节点为红色，为了满足各路径黑节点数量相同，叔叔节点则需要和父节点一起变为黑色。

如果叔叔节点不存在，为了满足性质，需要将该子树从爷爷节点的位置进行旋转。

如果叔叔节点为黑色，而父节点为红色，如果还要满足性质，说明子节点原本应为黑色，是因为经过了上述的调整而作为爷爷节点变成了红色。此时我们仍需从爷爷节点的位置进行旋转。

分析完上述完整情况之后，还有关于新插入节点的两种情况：

  1. 父节点为爷爷节点的左子节点，同时新增节点也为父节点的左子节点，为一条斜线。
  2. 父节点为爷爷节点的左子节点，但是新增节点也为父节点的有子节点，为一条折线。

斜线情况下，我们在需要旋转时只需单旋即可；

而当为折线时，就需要进行双旋，先变为斜线，在进行调整。

同时父节点也需要考虑是爷爷节点的左节点还是右节点两种情况，彼此的规则相反。

按照上边的步骤，我们能够得出代码情况：

  1. //插入
  2. 	bool Insert(const pair<K,V>& kv)
  3. 	{
  4. 		if (_root == nullptr)
  5. 		{
  6. 			_root = new Node(kv);
  7. 			_root->_col = BLACK;//根给黑色
  8. 			return true;
  9. 		}
  10. 		Node* parent = nullptr;
  11. 		Node* cur = _root;
  12. 		while (cur)
  13. 		{
  14. 			if (cur->_kv.first < kv.first)
  15. 			{
  16. 				parent = cur;
  17. 				cur = cur->_right;
  18. 			}
  19. 			else if (cur->_kv.first > kv.first)
  20. 			{
  21. 				parent = cur;
  22. 				cur = cur->_left;
  23. 			}
  24. 			else
  25. 			{
  26. 				return false;
  27. 			}
  28. 		}
  29. 		cur = new Node(kv);
  30. 		cur->_col = RED;//新增节点给红色
  31. 		if (kv.first < parent->_kv.first)
  32. 		{
  33. 			parent->_left = cur;
  34. 		}
  35. 		else
  36. 		{
  37. 			parent->_right = cur;
  38. 		}
  39. 		cur->_parent = parent;
  40. 		//parent是黑色就结束
  41. 		while (parent && parent->_col == RED)
  42. 		{
  43. 			Node* Grandfather = parent->_parent;
  44. 			if (parent == Grandfather->_left)
  45. 			{
  46. 				Node* uncle = Grandfather->_right;
  47. 				if (uncle && uncle->_col == RED)//叔叔存在且为红，直接变色
  48. 				{
  49. 					parent->_col = BLACK;
  50. 					uncle->_col = BLACK;
  51. 					Grandfather->_col = RED;
  52. 					//继续往上处理
  53. 					cur = Grandfather;
  54. 					parent = Grandfather->_parent;
  55. 				}
  56. 				else//叔叔不存在或叔叔存在但为黑
  57. 				{
  58. 					if (cur == parent->_left)//左边直接右旋
  59. 					{
  60. 						RotateR(Grandfather);
  61. 						parent->_col = BLACK;
  62. 						Grandfather->_col = RED;
  63. 					}
  64. 					else//右边则左右双旋
  65. 					{
  66. 						RotateL(parent);
  67. 						RotateR(Grandfather);
  68. 						cur->_col = BLACK;
  69. 						Grandfather->_col = RED;
  70. 					}
  71. 					break;
  72. 				}
  73. 			}
  74. 			else
  75. 			{
  76. 				Node* uncle = Grandfather->_left;
  77. 				if (uncle && uncle->_col == RED)
  78. 				{
  79. 					parent->_col = BLACK;
  80. 					uncle->_col = BLACK;
  81. 					Grandfather->_col = RED;
  82.  
  83. 					cur = Grandfather;
  84. 					parent = Grandfather->_parent;
  85. 				}
  86. 				else
  87. 				{
  88. 					if (cur == parent->_right)
  89. 					{
  90. 						RotateL(Grandfather);
  91. 						Grandfather->_col = RED;
  92. 						parent->_col = BLACK;
  93. 					}
  94. 					else
  95. 					{
  96. 						RotateR(parent);
  97. 						RotateL(Grandfather);
  98. 						cur->_col = BLACK;
  99. 						Grandfather->_col = RED;
  100. 					}
  101. 					break;
  102. 				}
  103. 			}
  104. 		}
  105. 		_root->_col = BLACK;
  106. 		return true;
  107. 	}

 需要考虑的情况确实很多，但如果自己画图认真分析，理解起来还是易如反掌的。

3.判断平衡

判断红黑树的平衡，我们自然要从其性质入手：

  1. 首先就是判断根节点是否为黑色。
  2. 其次容易判断的是是否有两个相邻的红色节点，注意这里我们不去判断一个节点与其子节点，反而去判断一个节点与其父节点。因为如果判断子节点，则可能需要判断两次，而父节点则只需判断一次。
  3. 最后就是判断所有路径上的黑节点数量是否相同。

其中前两种都比较容易想到代码方式，最重要的是如何比较黑节点的数量。

我们可以通过增加参数的方式。来记录到达每个节点位置时，该路径上出现过的黑节点的数量。而如何进行比较，因为每条路径上黑节点的数量都必须相同，所以我们直接记录一下最左边的一条路径上黑节点的数量，然后求出一条路径上的黑节点数之后，就进行比较即可。

  1. 	//判断平衡
  2. 	bool IsBalance()
  3. 	{
  4. 		if (_root->_col == RED)
  5. 			return false;
  6. 		int refnum = 0;
  7. 		Node* cur = _root;
  8. 		while (cur)
  9. 		{
  10. 			if (cur->_col == BLACK)
  11. 				refnum++;
  12. 			cur = cur->_left;
  13. 		}
  14. 		return Check(_root, 0, refnum);
  15. 	}
  16. 	bool Check(Node* root, int BlackNum,const int refnum)
  17. 	{
  18. 		if (root == nullptr)
  19. 		{
  20. 			if (refnum != BlackNum)
  21. 			{
  22. 				cout << "存在黑色节点个数不相等" << endl;
  23. 				return false;
  24. 			}
  25. 			cout << BlackNum << endl;
  26. 			return true;
  27. 		}
  28. 		if (root->_col == RED && root->_parent->_col == RED)
  29. 		{
  30. 			cout << root->_kv.first << "->存在连续的红色节点" << endl;
  31. 			return false;
  32. 		}
  33. 		if (root->_col == BLACK)
  34. 			BlackNum++;
  35. 		return Check(root->_left, BlackNum,refnum)
  36. 			&& Check(root->_right, BlackNum,refnum);
  37. 	}

 四.完整代码

  1. enum Colour
  2. {
  3. 	RED,
  4. 	BLACK
  5. };
  6.  
  7. template<class K,class V>
  8. struct RBTreeNode
  9. {
  10. 	RBTreeNode<K, V>* _left;
  11. 	RBTreeNode<K, V>* _right;
  12. 	RBTreeNode<K, V>* _parent;
  13.  
  14. 	pair<K, V> _kv;
  15. 	Colour _col;
  16.  
  17. 	RBTreeNode(const pair<K, V>& kv)
  18. 		:_left(nullptr)
  19. 		, _right(nullptr)
  20. 		, _parent(nullptr)
  21. 		, _kv(kv)
  22. 		,_col(RED)
  23. 	{}
  24. };
  25. template<class K, class V>
  26. class RBTree
  27. {
  28. 	typedef RBTreeNode<K, V> Node;
  29. public:
  30. 	//插入
  31. 	bool Insert(const pair<K,V>& kv)
  32. 	{
  33. 		if (_root == nullptr)
  34. 		{
  35. 			_root = new Node(kv);
  36. 			_root->_col = BLACK;//根给黑色
  37. 			return true;
  38. 		}
  39. 		Node* parent = nullptr;
  40. 		Node* cur = _root;
  41. 		while (cur)
  42. 		{
  43. 			if (cur->_kv.first < kv.first)
  44. 			{
  45. 				parent = cur;
  46. 				cur = cur->_right;
  47. 			}
  48. 			else if (cur->_kv.first > kv.first)
  49. 			{
  50. 				parent = cur;
  51. 				cur = cur->_left;
  52. 			}
  53. 			else
  54. 			{
  55. 				return false;
  56. 			}
  57. 		}
  58. 		cur = new Node(kv);
  59. 		cur->_col = RED;//新增节点给红色
  60. 		if (kv.first < parent->_kv.first)
  61. 		{
  62. 			parent->_left = cur;
  63. 		}
  64. 		else
  65. 		{
  66. 			parent->_right = cur;
  67. 		}
  68. 		cur->_parent = parent;
  69. 		//parent是黑色就结束
  70. 		while (parent && parent->_col == RED)
  71. 		{
  72. 			Node* Grandfather = parent->_parent;
  73. 			if (parent == Grandfather->_left)
  74. 			{
  75. 				Node* uncle = Grandfather->_right;
  76. 				if (uncle && uncle->_col == RED)//叔叔存在且为红，直接变色
  77. 				{
  78. 					parent->_col = BLACK;
  79. 					uncle->_col = BLACK;
  80. 					Grandfather->_col = RED;
  81. 					//继续往上处理
  82. 					cur = Grandfather;
  83. 					parent = Grandfather->_parent;
  84. 				}
  85. 				else//叔叔不存在或叔叔存在但为黑
  86. 				{
  87. 					if (cur == parent->_left)//左边直接右旋
  88. 					{
  89. 						RotateR(Grandfather);
  90. 						parent->_col = BLACK;
  91. 						Grandfather->_col = RED;
  92. 					}
  93. 					else//右边则左右双旋
  94. 					{
  95. 						RotateL(parent);
  96. 						RotateR(Grandfather);
  97. 						cur->_col = BLACK;
  98. 						Grandfather->_col = RED;
  99. 					}
  100. 					break;
  101. 				}
  102. 			}
  103. 			else
  104. 			{
  105. 				Node* uncle = Grandfather->_left;
  106. 				if (uncle && uncle->_col == RED)
  107. 				{
  108. 					parent->_col = BLACK;
  109. 					uncle->_col = BLACK;
  110. 					Grandfather->_col = RED;
  111.  
  112. 					cur = Grandfather;
  113. 					parent = Grandfather->_parent;
  114. 				}
  115. 				else
  116. 				{
  117. 					if (cur == parent->_right)
  118. 					{
  119. 						RotateL(Grandfather);
  120. 						Grandfather->_col = RED;
  121. 						parent->_col = BLACK;
  122. 					}
  123. 					else
  124. 					{
  125. 						RotateR(parent);
  126. 						RotateL(Grandfather);
  127. 						cur->_col = BLACK;
  128. 						Grandfather->_col = RED;
  129. 					}
  130. 					break;
  131. 				}
  132. 			}
  133. 		}
  134. 		_root->_col = BLACK;
  135. 		return true;
  136. 	}
  137. 	//右单旋
  138. 	void RotateR(Node* parent)
  139. 	{
  140. 		//定义左子节点
  141. 		Node* subL = parent->_left;
  142. 		//定义左子节点的右子节点
  143. 		Node* subLR = subL->_right;
  144. 		//调整
  145. 		parent->_left = subLR;
  146. 		//判空
  147. 		if (subLR)
  148. 			subLR->_parent = parent;
  149. 		//调整
  150. 		subL->_right = parent;
  151. 		Node* ppNode = parent->_parent;
  152. 		parent->_parent = subL;
  153. 		if (parent == _root)//判断是否为根
  154. 		{
  155. 			_root = subL;
  156. 			_root->_parent = nullptr;
  157. 		}
  158. 		else//不是根节点，调整父节点指向
  159. 		{
  160. 			if (ppNode->_left == parent)
  161. 				ppNode->_left = subL;
  162. 			else
  163. 				ppNode->_right = subL;
  164.  
  165. 			subL->_parent = ppNode;
  166. 		}
  167. 	}
  168. 	//左单旋
  169. 	void RotateL(Node* parent)
  170. 	{
  171. 		//定义右子节点
  172. 		Node* subR = parent->_right;
  173. 		//定义右子节点的左子节点
  174. 		Node* subRL = subR->_left;
  175. 		//调整
  176. 		parent->_right = subRL;
  177. 		//判空
  178. 		if (subRL)
  179. 			subRL->_parent = parent;
  180. 		//调整
  181. 		subR->_left = parent;
  182. 		Node* ppNode = parent->_parent;
  183. 		parent->_parent = subR;
  184. 		if (parent == _root)//判断是否为根
  185. 		{
  186. 			_root = subR;
  187. 			_root->_parent = nullptr;
  188. 		}
  189. 		else//不是根节点，调整父节点指向
  190. 		{
  191. 			if (ppNode->_left == parent)
  192. 				ppNode->_left = subR;
  193. 			else
  194. 				ppNode->_right = subR;
  195.  
  196. 			subR->_parent = ppNode;
  197. 		}
  198. 	}
  199. 	//遍历
  200. 	void InOrder()
  201. 	{
  202. 		inOrder(_root);
  203. 		cout << endl;
  204. 	}
  205. 	void inOrder(const Node* root)
  206. 	{
  207. 		if (root == nullptr)
  208. 		{
  209. 			return;
  210. 		}
  211. 		inOrder(root->_left);
  212. 		cout << root->_kv.first << ':' << root->_kv.second << endl;
  213. 		inOrder(root->_right);
  214. 	}
  215. 	//判断平衡
  216. 	bool IsBalance()
  217. 	{
  218. 		if (_root->_col == RED)
  219. 			return false;
  220. 		int refnum = 0;
  221. 		Node* cur = _root;
  222. 		while (cur)
  223. 		{
  224. 			if (cur->_col == BLACK)
  225. 				refnum++;
  226. 			cur = cur->_left;
  227. 		}
  228. 		return Check(_root, 0, refnum);
  229. 	}
  230. 	bool Check(Node* root, int BlackNum,const int refnum)
  231. 	{
  232. 		if (root == nullptr)
  233. 		{
  234. 			if (refnum != BlackNum)
  235. 			{
  236. 				cout << "存在黑色节点个数不相等" << endl;
  237. 				return false;
  238. 			}
  239. 			cout << BlackNum << endl;
  240. 			return true;
  241. 		}
  242. 		if (root->_col == RED && root->_parent->_col == RED)
  243. 		{
  244. 			cout << root->_kv.first << "->存在连续的红色节点" << endl;
  245. 			return false;
  246. 		}
  247. 		if (root->_col == BLACK)
  248. 			BlackNum++;
  249. 		return Check(root->_left, BlackNum,refnum)
  250. 			&& Check(root->_right, BlackNum,refnum);
  251. 	}
  252. private:
  253. 	Node* _root = nullptr;
  254. 	//size_t _size = 0;
  255. };

总结

关于红黑树的知识就分享这么多，喜欢本篇文章记得一键三连，我们下期再见！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/寸_铁/article/detail/946923
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号