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

C++之红黑树_c++ 红黑树

作者：煮酒与君饮 | 2024-07-28 13:58:11

赞

踩

c++ 红黑树

目录

1.红黑树

1.1红黑树的概念

1.2红黑树的性质

1.3红黑树节点的定义

1.4红黑树的结构

1.5红黑树的插入操作

情况一

情况二

情况三

1.6红黑树的验证

红黑树的实现中使用了旋转的几个函数

C++之AVL树的使用以及原理详解-CSDN博客

 

1.红黑树

1.1红黑树的概念

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

1.2红黑树的性质

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

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的

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

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

以上红黑树的性质使得    其最长路径中节点个数不会超过最短路径节点个数的两倍

1.3红黑树节点的定义

  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. 	pair<K, V> _kv;
  14. 	Colour _col;
  15.  
  16. 	RBTreeNode(const pair<K, V>& kv)
  17. 		:_left(nullptr)
  18. 		, _right(nullptr)
  19. 		, parent(nullptr)
  20. 		, _kv(kv)
  21. 		, _col(RED)
  22. 	{}
  23. };

红黑树中新插入节点的颜色一般都初始化成为红色，因为如果插入黑色就会导致各个分支上黑色节点的数量不同，初始化成红色节点也方便向上调整

1.4红黑树的结构

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

1.5红黑树的插入操作

插入操作：

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

1. 按照二叉搜索的树规则插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏

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

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点情况一: cur为红，p为红，g为黑，u存在且为红

分为了几种情况：

情况一

cur为红，p为红，g为黑，u存在且为红

如果g是根节点，调整完成后，需要将g改为黑色如果g是子树，g一定有双亲，且g的双亲如果是红色，需要继续向上调整。

cur和p均为红，不符合红黑树的规则

所以将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二

cur为红，p为红，g为黑，u不存在/u存在且为黑

u的情况有两种
1.如果u节点不存在，则cur一定是新插入节点，因为如果cur不是新插入节点则cur和p一定有一个节点的颜色是黑色，就不满足性质4:每条路径黑色节点个数相同。
2.如果u节点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色的现在看到其是红色的原因是因为cur的子树在调整的过程中将cur节点的颜色由黑色改成红色。

p为g的左孩子，cur为p的左孩子，则进行右单旋转;相反p为g的右孩子，cur为p的右孩子，则进行左单旋转p、g变色--p变黑，g变红

情况三

cur为红，p为红，g为黑，u不存在/u存在且为黑

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，这样旋转完了之后就变成了我们上面所分析的情况二。

  1. bool Insert(const pair<K, V>& kv)
  2. 	{
  3. 		if (_root == nullptr)
  4. 		{
  5. 			_root = new Node(kv);
  6. 			_root->_col = BLACK;
  7. 			return true;
  8. 		}
  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.  
  30. 		cur = new Node(kv); // 红色的
  31. 		if (parent->_kv.first < kv.first)
  32. 		{
  33. 			parent->_right = cur;
  34. 		}
  35. 		else
  36. 		{
  37. 			parent->_left = cur;
  38. 		}
  39. 		cur->_parent = parent;
  40.  
  41. 		while (parent && parent->_col == RED)
  42. 		{
  43. 			Node* grandfather = parent->_parent;
  44. 			if (parent == grandfather->_left)
  45. 			{
  46. 				Node* uncle = grandfather->_right;
  47. 				// 情况一：叔叔存在且为红
  48. 				if (uncle && uncle->_col == RED)
  49. 				{
  50. 					// 变色
  51. 					parent->_col = uncle->_col = BLACK;
  52. 					grandfather->_col = RED;
  53.  
  54. 					// 继续往上处理
  55. 					cur = grandfather;
  56. 					parent = cur->_parent;
  57. 				}
  58. 				else
  59. 				{
  60. 					// 情况二：叔叔不存在或者存在且为黑
  61. 					// 旋转+变色
  62. 					if (cur == parent->_left)
  63. 					{
  64. 						//       g
  65. 						//    p    u
  66. 						// c
  67. 						RotateR(grandfather);
  68. 						parent->_col = BLACK;
  69. 						grandfather->_col = RED;
  70. 					}
  71. 					else
  72. 					{
  73. 						//       g
  74. 						//    p     u
  75. 						//      c
  76. 						RotateL(parent);
  77. 						RotateR(grandfather);
  78. 						cur->_col = BLACK;
  79. 						grandfather->_col = RED;
  80. 					}
  81.  
  82. 					break;
  83. 				} 
  84. 			}
  85. 			else
  86. 			{
  87. 				Node* uncle = grandfather->_left;
  88. 				// 情况一：叔叔存在且为红
  89. 				if (uncle && uncle->_col == RED)
  90. 				{
  91. 					// 变色
  92. 					parent->_col = uncle->_col = BLACK;
  93. 					grandfather->_col = RED;
  94.  
  95. 					// 继续往上处理
  96. 					cur = grandfather;
  97. 					parent = cur->_parent;
  98. 				}
  99. 				else
  100. 				{
  101. 					// 情况二：叔叔不存在或者存在且为黑
  102. 					// 旋转+变色
  103. 					//      g
  104. 					//   u     p
  105. 					//            c
  106. 					if (cur == parent->_right)
  107. 					{
  108. 						RotateL(grandfather);
  109. 						parent->_col = BLACK;
  110. 						grandfather->_col = RED;
  111. 					}
  112. 					else
  113. 					{
  114. 						//		g
  115. 						//   u     p
  116. 						//      c
  117. 						RotateR(parent);
  118. 						RotateL(grandfather);
  119. 						cur->_col = BLACK;
  120. 						grandfather->_col = RED;
  121. 					}
  122.  
  123. 					break;
  124. 				}
  125. 			}
  126. 		}
  127.  
  128. 		_root->_col = BLACK;
  129.  
  130. 		return true;
  131. 	}

1.6红黑树的验证

红黑树的验证就是 判断一下 这课树是否满足 红黑树的这几条性质， 但是 不能用这四条性质推出来的结论来判断这棵树是不是红黑树。

  1. bool Check(Node* cur)
  2. 	{
  3. 		if (cur == nullptr)
  4. 			return true; //空树也是红黑树
  5.  
  6. 		if (cur->_col == RED && cur->_parent->_col == RED)
  7. 		{
  8. 			cout << cur->_kv.first << "存在连续的红色节点" << endl;
  9. 			return false;
  10. 		}//判断是否存在红色节点
  11. 		
  12. 		return Check(cur->_left)
  13. 			&& Check(cur->_right);
  14. 	}
  15.  
  16. 	bool IsBalance()
  17. 	{
  18. 		if (_root && _root->_col == RED)//判断根节点是否为黑色
  19. 			return false;
  20.  
  21. 		return Check(_root);
  22. 	}

1.7总体实现

  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. 	pair<K, V> _kv;
  14. 	Colour _col;
  15.  
  16. 	RBTreeNode(const pair<K, V>& kv)
  17. 		:_left(nullptr)
  18. 		, _right(nullptr)
  19. 		, _parent(nullptr)
  20. 		, _kv(kv)
  21. 		,_col(RED)
  22. 	{}
  23. };
  24.  
  25. template<class K, class V>
  26. class RBTree
  27. {
  28. 	typedef RBTreeNode<K, V> Node;
  29. public:
  30. 	bool Insert(const pair<K, V>& kv)
  31. 	{
  32. 		if (_root == nullptr)
  33. 		{
  34. 			_root = new Node(kv);
  35. 			_root->_col = BLACK;
  36. 			return true;
  37. 		}
  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.  
  59. 		cur = new Node(kv); // 红色的
  60. 		if (parent->_kv.first < kv.first)
  61. 		{
  62. 			parent->_right = cur;
  63. 		}
  64. 		else
  65. 		{
  66. 			parent->_left = cur;
  67. 		}
  68. 		cur->_parent = parent;
  69.  
  70. 		while (parent && parent->_col == RED)
  71. 		{
  72. 			Node* grandfather = parent->_parent;
  73. 			if (parent == grandfather->_left)
  74. 			{
  75. 				Node* uncle = grandfather->_right;
  76. 				// 情况一：叔叔存在且为红
  77. 				if (uncle && uncle->_col == RED)
  78. 				{
  79. 					// 变色
  80. 					parent->_col = uncle->_col = BLACK;
  81. 					grandfather->_col = RED;
  82.  
  83. 					// 继续往上处理
  84. 					cur = grandfather;
  85. 					parent = cur->_parent;
  86. 				}
  87. 				else
  88. 				{
  89. 					// 情况二：叔叔不存在或者存在且为黑
  90. 					// 旋转+变色
  91. 					if (cur == parent->_left)
  92. 					{
  93. 						//       g
  94. 						//    p    u
  95. 						// c
  96. 						RotateR(grandfather);
  97. 						parent->_col = BLACK;
  98. 						grandfather->_col = RED;
  99. 					}
  100. 					else
  101. 					{
  102. 						//       g
  103. 						//    p     u
  104. 						//      c
  105. 						RotateL(parent);
  106. 						RotateR(grandfather);
  107. 						cur->_col = BLACK;
  108. 						grandfather->_col = RED;
  109. 					}
  110.  
  111. 					break;
  112. 				} 
  113. 			}
  114. 			else
  115. 			{
  116. 				Node* uncle = grandfather->_left;
  117. 				// 情况一：叔叔存在且为红
  118. 				if (uncle && uncle->_col == RED)
  119. 				{
  120. 					// 变色
  121. 					parent->_col = uncle->_col = BLACK;
  122. 					grandfather->_col = RED;
  123.  
  124. 					// 继续往上处理
  125. 					cur = grandfather;
  126. 					parent = cur->_parent;
  127. 				}
  128. 				else
  129. 				{
  130. 					// 情况二：叔叔不存在或者存在且为黑
  131. 					// 旋转+变色
  132. 					//      g
  133. 					//   u     p
  134. 					//            c
  135. 					if (cur == parent->_right)
  136. 					{
  137. 						RotateL(grandfather);
  138. 						parent->_col = BLACK;
  139. 						grandfather->_col = RED;
  140. 					}
  141. 					else
  142. 					{
  143. 						//		g
  144. 						//   u     p
  145. 						//      c
  146. 						RotateR(parent);
  147. 						RotateL(grandfather);
  148. 						cur->_col = BLACK;
  149. 						grandfather->_col = RED;
  150. 					}
  151.  
  152. 					break;
  153. 				}
  154. 			}
  155. 		}
  156.  
  157. 		_root->_col = BLACK;
  158.  
  159. 		return true;
  160. 	}
  161.  
  162. 	void RotateL(Node* parent)
  163. 	{
  164. 		Node* subR = parent->_right;
  165. 		Node* subRL = subR->_left;
  166.  
  167. 		parent->_right = subRL;
  168. 		if (subRL)
  169. 			subRL->_parent = parent;
  170.  
  171. 		subR->_left = parent;
  172. 		Node* ppnode = parent->_parent;
  173. 		parent->_parent = subR;
  174.  
  175. 		if (parent == _root)
  176. 		{
  177. 			_root = subR;
  178. 			subR->_parent = nullptr;
  179. 		}
  180. 		else
  181. 		{
  182. 			if (ppnode->_left == parent)
  183. 			{
  184. 				ppnode->_left = subR;
  185. 			}
  186. 			else
  187. 			{
  188. 				ppnode->_right = subR;
  189. 			}
  190. 			subR->_parent = ppnode;
  191. 		}
  192. 	}
  193.  
  194. 	void RotateR(Node* parent)
  195. 	{
  196. 		Node* subL = parent->_left;
  197. 		Node* subLR = subL->_right;
  198.  
  199. 		parent->_left = subLR;
  200. 		if (subLR)
  201. 			subLR->_parent = parent;
  202.  
  203. 		subL->_right = parent;
  204.  
  205. 		Node* ppnode = parent->_parent;
  206. 		parent->_parent = subL;
  207.  
  208. 		if (parent == _root)
  209. 		{
  210. 			_root = subL;
  211. 			subL->_parent = nullptr;
  212. 		}
  213. 		else
  214. 		{
  215. 			if (ppnode->_left == parent)
  216. 			{
  217. 				ppnode->_left = subL;
  218. 			}
  219. 			else
  220. 			{
  221. 				ppnode->_right = subL;
  222. 			}
  223. 			subL->_parent = ppnode;
  224. 		}
  225. 	}
  226.  
  227. 	void _InOrder(Node* root)
  228. 	{
  229. 		if (root == nullptr)
  230. 			return;
  231.  
  232. 		_InOrder(root->_left);
  233. 		cout << root->_kv.first << endl;
  234. 		_InOrder(root->_right);
  235. 	}
  236.  
  237. 	void InOrder()
  238. 	{
  239. 		_InOrder(_root);
  240. 	}
  241.  
  242. 	bool Check(Node* cur)
  243. 	{
  244. 		if (cur == nullptr)
  245. 			return true;
  246.  
  247. 		if (cur->_col == RED && cur->_parent->_col == RED)
  248. 		{
  249. 			cout << cur->_kv.first << "存在连续的红色节点" << endl;
  250. 			return false;
  251. 		}
  252. 		
  253. 		return Check(cur->_left)
  254. 			&& Check(cur->_right);
  255. 	}
  256.  
  257. 	bool IsBalance()
  258. 	{
  259. 		if (_root && _root->_col == RED)
  260. 			return false;
  261.  
  262. 		return Check(_root);
  263. 	}
  264.  
  265. private:
  266. 	Node* _root = nullptr;
  267. };

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

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

  

闽ICP备14008679号