devbox
信息技术墨韵书生
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

C++&&数据结构——红黑树

作者：信息技术墨韵书生 | 2024-01-31 15:42:57

赞

踩

C++&&数据结构——红黑树

一，关于红黑树

红黑树也是一种平衡二叉搜索树，但在每个节点上增加一个存储位表示节点的颜色，颜色右两种，红与黑，因此也称为红黑树。

通过对任意一条从根到叶子的路径上各个节点着色方式的限制，红黑树可以确保没有一条路径会比其他路径长出两倍，因此是“近似平衡”。

下面就是一棵红黑树：

结合上面的图，我们可以了解下红黑树成立的各种条件：

①每个节点不是红色就是黑色

②根节点是黑色的

③如果一个节点是红色的，那么这个红色节点的两个孩子节点都是黑色的

④对于每个节点，从该节点到其所有后代叶结点的路径上，黑色节点的数量相同

⑤每个叶子节点都是黑色的（这里所说的叶子节点是上图中的空节点）

二，红黑树节点和结构定义

2.1 节点

  1. //用枚举来标识颜色
  2. enum Colour
  3. {
  4. 	RED,
  5. 	BLACK
  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. };

2.2 结构

  1. template<class K, class V>
  2. class RBTree
  3. {
  4. 	typedef RBTreeNode<K, V> Node;
  5. public:
  6.  
  7.     //此处实现各种成员函数和接口
  8.  
  9. private:
  10.     Node* _root = nullptr;
  11. }

三，红黑树插入*

3.1 基本插入

基本插入也和之前的差不多，直接上代码：

  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. 	cur->_col = RED;//把新插入的节点都搞成红色，因为如果插入后改为黑色，一定违反规则四：每条路径的黑色节点数量相同
  42. 	//如果父亲是黑色节点或者插入前是空树，直接摊牌不玩了，不进入循环
  43.  
  44. 	while (parent && parent->_col == RED)//父节点存在且父节点为红色
  45. 	{
  46.         //这里的循环控制平衡，具体看下面的各种情况
  47.         
  48.     }
  49. }

按搜索树的性质插入之后就是要判断红黑树的性质是否遭到破坏。

新插入节点默认为红色，因此：如果双亲节点颜色是黑色，那么没有违反红黑树的任何性质，不需要调整，就是上面代码最后的循环直接跳过；但是如果新插入的节点的双亲为红色，就违反了上面的规则“红节点的孩子为黑”，也就是出现了连续的红节点，需要调整，就是进入上面的循环部分

此时就要分下面的几条情况来讨论，维持平衡的方法的关键就是看叔叔也就是父亲的兄弟节点的状态

3.2 情况一：uncle节点存在且为红

3.2.1 cur是新增节点

如下图（假设cur是新增）：

uncle存在且为红时，我们直接将父节点和叔叔节点都变成黑，再将爷爷节点变为红，但是只这样做肯定不行，比如下图：

一次调整过后就会出现上面的情况，所以需要不断往上调整

3.2.2 cur不是新增节点

如下图：

如上图，cur本身是黑色，是树中原来的节点，因为子树有新增变成了红，所以对于cur节点有两种情况符合情况一：

①本身是新增，默认新增节点为红

②子树有新增，通过情况一的向上调整变成了红 

3.3 情况二+情况三：uncle不存在或者存在为黑

从情况一我们可以看出，cur可能是新节点也可能不是新节点，但最终结果都是变红。

如果uncle节点不存在，那么cur一定是新增，如果cur不是新增，最开始循环的条件为父节点存在且为红，又因为红节点的孩子为黑这条性质，cur必定为黑，但是由于uncle不存在，导致以爷爷节点为根的子树左右子树黑节点数量不一样。

所以如果uncle不存在，cur必定为新增，如下图：

而对于uncle节点存在且为黑时， 那么cur原来肯定是黑色的因为父节点是红的，右因为左右两边黑色节点数量要一致，cur的孩子也为红，这时候在cur孩子后面新增节点时，就变成了情况一，会不断向上调整颜色，也会把cur变成红色，如下图：

所以，情况二和情况三的最终情况都是cur为红，所以可以放在一起讨论

3.4 插入代码

  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. 	cur->_col = RED;//把新插入的节点都搞成红色，因为如果插入后改为黑色，一定违反规则四：每条路径的黑色节点数量相同
  42. 	//如果父亲是黑色节点或者插入前是空树，直接摊牌不玩了，不进入循环
  43.  
  44. 	while (parent && parent->_col == RED)//父节点存在且父节点为红色
  45. 	{
  46. 		//找祖父
  47. 		Node* grandfather = parent->_parent;
  48. 		assert(grandfather);
  49. 		assert(grandfather->_col == BLACK);
  50. 		//红黑树的关键看叔叔，也就是父亲的兄弟
  51. 		if (parent == grandfather->_left)//父亲在爷爷的左边，叔叔分为几种情况分开讨论
  52. 		{
  53. 			Node* uncle = grandfather->_right;//父亲在左边，那么叔叔就在右边
  54. 			//情况一:uncle存在且为红
  55. 			if (uncle && uncle->_col == RED)
  56. 			{
  57. 				//父亲和叔叔变黑是为了替代祖父的黑，祖父变红是为了保持黑色节点数量不变
  58. 				parent->_col = uncle->_col = BLACK;//把父亲和叔叔变黑
  59. 				grandfather->_col = RED;//把祖父变红
  60. 				//继续往上处理 -- 将祖父当成新增节点，循环往上处理
  61. 				cur = grandfather;
  62. 				parent = cur->_parent;
  63. 			}
  64. 			//情况二+三,uncle不存在 + 存在且为黑
  65. 			else
  66. 			{
  67. 				//新增在左边:右单旋+变色
  68. 				//      g            p
  69. 				//   p     u  --> c     g 
  70. 				//c                         u
  71. 				if (cur == parent->_left)
  72. 				{
  73. 					RotateR(grandfather);
  74. 					parent->_col = BLACK;
  75. 					grandfather->_col = RED;
  76. 				}
  77. 				//新增在右边:左单旋 + 右双旋+变色
  78. 				//     g
  79. 				//  p     u   -->   
  80. 				//    c
  81. 				else
  82. 				{
  83. 					RotateL(parent);
  84. 					RotateR(grandfather);
  85. 					cur->_col = BLACK;
  86. 					grandfather->_col = RED;
  87. 				}
  88. 				break;
  89. 			}
  90. 		}
  91. 		else//父亲在右边，叔叔可能在左边  (parent == grandfather->_right)
  92. 		{
  93. 			Node* uncle = grandfather->_left;
  94. 			//情况一
  95. 			if (uncle && uncle->_col == RED)
  96. 			{
  97. 				parent->_col = uncle->_col = BLACK;
  98. 				grandfather->_col = RED;
  99. 				//继续往上处理
  100. 				cur = grandfather;
  101. 				parent = cur->_parent;
  102. 			}
  103. 			else //情况二+三,uncle不存在 + 存在且为黑
  104. 			{
  105. 				//新增在右边:左单旋+变色
  106. 				//      g
  107. 				//   u     p
  108. 				//            c
  109. 				if (cur == parent->_right)
  110. 				{
  111. 					RotateL(grandfather);
  112. 					parent->_col = BLACK;
  113. 					grandfather->_col = RED;
  114. 				}
  115. 				//新增在左边:左右双旋+变色
  116. 				//     g
  117. 				//  u     p
  118. 				//       c
  119. 				else
  120. 				{
  121. 					RotateR(parent);
  122. 					RotateL(grandfather);
  123. 					cur->_col = BLACK;
  124. 					grandfather->_col = RED;
  125. 				}
  126.  
  127. 				break;
  128. 			}
  129.  
  130. 		}
  131. 	}
  132. 	//循环结束
  133. 	_root->_col = BLACK;
  134. 	return true;
  135. }

四，其他接口实现

4.1 左旋转函数

  1. //左旋转函数
  2. void RotateL(Node* parent)
  3. {
  4. 	Node* subR = parent->_right;
  5. 	Node* subRL = subR->_left;
  6.  
  7. 	parent->_right = subRL;
  8. 	//subRL可能是空
  9. 	if (subRL)
  10. 	{
  11. 		subRL->_parent = parent;
  12. 	}
  13. 	//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
  14. 	Node* ppNode = parent->_parent;
  15.  
  16. 	subR->_left = parent;
  17. 	parent->_parent = subR;
  18.  
  19. 	//parent是整棵树的根
  20. 	if (_root == parent)
  21. 	{
  22. 		_root = subR;
  23. 		subR->_parent = nullptr;
  24. 	}
  25. 	else//parent是子树的根
  26. 	{
  27. 		if (ppNode->_left == parent)
  28. 		{
  29. 			ppNode->_left = subR;
  30. 		}
  31. 		else
  32. 		{
  33. 			ppNode->_right = subR;
  34. 		}
  35. 		subR->_parent = ppNode;
  36. 	}
  37. }

4.2 右旋转函数

  1. //右旋转函数
  2. void RotateR(Node* parent)
  3. {
  4. 	Node* subL = parent->_left;
  5. 	Node* subLR = subL->_right;
  6.  
  7. 	parent->_left = subLR;
  8. 	//subLR可能是空
  9. 	if (subLR)
  10. 	{
  11. 		subLR->_parent = parent;
  12. 	}
  13. 	//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
  14. 	Node* ppNode = parent->_parent;
  15.  
  16. 	subL->_right = parent;
  17. 	parent->_parent = subL;
  18.  
  19. 	//parent是整颗树的根
  20. 	if (_root == parent)
  21. 	{
  22. 		_root = subL;
  23. 		subL->_parent = nullptr;
  24. 	}
  25. 	else
  26. 	{
  27. 		if (ppNode->_left == parent)
  28. 		{
  29. 			ppNode->_left = subL;
  30. 		}
  31. 		else
  32. 		{
  33. 			ppNode->_right = subL;
  34. 		}
  35. 		subL->_parent = ppNode;
  36. 	}
  37. }

4.3 检查函数

  1. public:
  2. 	bool IsBalance() //根据规则来检查
  3. 	{
  4. 		if (_root && _root->_col == RED)
  5. 		{
  6. 			cout << "根节点不是黑色" << endl;
  7. 			return false;
  8. 		}
  9.  
  10. 		//定义基准值，用来判断每条路径的黑色节点数量是否相同
  11. 		int benchmark = 0;
  12. 		Node* cur = _root;
  13. 		while (cur)
  14. 		{
  15. 			if (cur->_col == BLACK)
  16. 			{
  17. 				++benchmark;
  18. 			}
  19. 			cur = cur->_left;
  20. 		}
  21.  
  22. 		//检查连续红色节点
  23. 		return _Check(_root,0,benchmark);
  24.  
  25. 	}
  26. private:
  27. 	bool _Check(Node* root,int blackNum,int benchmark)
  28. 	{
  29. 		if (root == nullptr)
  30. 		{
  31. 			if (benchmark != blackNum)
  32. 			{
  33. 				cout << "某条路径黑色节点数量不相等";
  34. 				return false;
  35. 			}
  36. 			return true;
  37. 		}
  38. 		if (root->_col == BLACK)
  39. 		{
  40. 			++blackNum;
  41. 		}
  42. 		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
  43. 		{
  44. 			cout << "存在连续红节点" << endl;
  45. 			return false;
  46. 		}
  47. 		return _Check(root->_left,blackNum,benchmark) && _Check(root->_right,blackNum,benchmark);
  48. 	}

 4.4 打印

  1. void InOrder()
  2. {
  3. 	_InOrder(_root);
  4. 	cout << endl;
  5. }
  6. private:
  7. void _InOrder(Node* root)
  8. {
  9. 	if (root == nullptr)
  10. 	{
  11. 		return;
  12. 	}
  13.  
  14. 	_InOrder(root->_left);
  15. 	cout << root->_kv.first << ":" << root->_kv.second << endl;
  16. 	_InOrder(root->_right);
  17. }

4.5 查找

  1. Node* Find(const K& key)
  2. {
  3. 	Node* cur = _root;
  4. 	while (cur)
  5. 	{
  6. 		if (cur->_kv.first < key)
  7. 		{
  8. 			cur = cur->_right;
  9. 		}
  10. 		else if (cur->_kv.first > key)
  11. 		{
  12. 			cur = cur->_left;
  13. 		}
  14. 		else
  15. 		{
  16. 			return cur;
  17. 		}
  18. 	}
  19. }

4.6 析构

  1. ~RBTree()
  2. {
  3. 	_Destroy(_root);
  4. 	_root == nullptr;
  5. }
  6. private:
  7. 	void _Destroy(Node* root)
  8. 	{
  9. 		if (root == nullptr)
  10. 		{
  11. 			return;
  12. 		}
  13. 		_Destroy(root->_left);
  14. 		_Destroy(root->_right);
  15. 		delete root;
  16. 		root == nullptr;
  17. 	}

五，红黑树源代码和测试代码

源代码(RBTree.h)

  1. #pragma once
  2. //最长路径不超过最短路径的两倍
  3.  
  4. //红黑树和AVL树相比来说，红黑树的优点是旋转的次数更少
  5. //如果两个树都插入1万个树，查找时，AVL树最多要查找30次，红黑树最多查找60次
  6. // 但是这种差别对于CPU来说可以忽略不计，所以论综合性能，还是红黑树更胜一筹
  7. #include<iostream>
  8. #include<assert.h>
  9. using namespace std;
  10.  
  11. //用枚举来标识颜色
  12. enum Colour
  13. {
  14. 	RED,
  15. 	BLACK
  16. };
  17. template<class K, class V>
  18. struct RBTreeNode
  19. {
  20. 	RBTreeNode<K, V>* _left;
  21. 	RBTreeNode<K, V>* _right;
  22. 	RBTreeNode<K, V>* _parent;
  23.  
  24. 	pair<K, V> _kv;
  25. 	Colour _col;
  26.  
  27. 	RBTreeNode(const pair<K, V>& kv)
  28. 		:_left(nullptr)
  29. 		, _right(nullptr)
  30. 		, _parent(nullptr)
  31. 		, _kv(kv)
  32. 		, _col(RED)
  33. 	{}
  34. };
  35.  
  36. template<class K, class V>
  37. class RBTree
  38. {
  39. 	typedef RBTreeNode<K, V> Node;
  40. public:
  41. 	Node* Find(const K& key)
  42. 	{
  43. 		Node* cur = _root;
  44. 		while (cur)
  45. 		{
  46. 			if (cur->_kv.first < key)
  47. 			{
  48. 				cur = cur->_right;
  49. 			}
  50. 			else if (cur->_kv.first > key)
  51. 			{
  52. 				cur = cur->_left;
  53. 			}
  54. 			else
  55. 			{
  56. 				return cur;
  57. 			}
  58. 		}
  59. 	}
  60. 	~RBTree()
  61. 	{
  62. 		_Destroy(_root);
  63. 		_root == nullptr;
  64. 	}
  65. 	//插入时和搜索树一样的插入
  66. 	bool Insert(const pair<K, V>& kv)
  67. 	{
  68. 		if (_root == nullptr)
  69. 		{
  70. 			_root = new Node(kv);
  71. 			_root->_col = BLACK;
  72. 			return true;
  73. 		}
  74.  
  75. 		Node* parent = nullptr;
  76. 		Node* cur = _root;
  77. 		while (cur)
  78. 		{
  79. 			if (cur->_kv.first < kv.first)
  80. 			{
  81. 				parent = cur;
  82. 				cur = cur->_right;
  83. 			}
  84. 			else if (cur->_kv.first > kv.first)
  85. 			{
  86. 				parent = cur;
  87. 				cur = cur->_left;
  88. 			}
  89. 			else
  90. 			{
  91. 				return false;
  92. 			}
  93. 		}
  94.  
  95. 		cur = new Node(kv);
  96. 		if (parent->_kv.first < kv.first)
  97. 		{
  98. 			parent->_right = cur;
  99. 		}
  100. 		else
  101. 		{ 
  102. 			parent->_left = cur;
  103. 		}
  104. 		cur->_parent = parent;
  105. 		//插入完成，开始改变颜色和调整旋转
  106. 		cur->_col = RED;//把新插入的节点都搞成红色，因为如果插入后改为黑色，一定违反规则四：每条路径的黑色节点数量相同
  107. 		//如果父亲是黑色节点或者插入前是空树，直接摊牌不玩了，不进入循环
  108.  
  109. 		while (parent && parent->_col == RED)//父节点存在且父节点为红色
  110. 		{
  111. 			//找祖父
  112. 			Node* grandfather = parent->_parent;
  113. 			assert(grandfather);
  114. 			assert(grandfather->_col == BLACK);
  115. 			//红黑树的关键看叔叔，也就是父亲的兄弟
  116. 			if (parent == grandfather->_left)//父亲在爷爷的左边，叔叔分为几种情况分开讨论
  117. 			{
  118. 				Node* uncle = grandfather->_right;//父亲在左边，那么叔叔就在右边
  119. 				//情况一:uncle存在且为红
  120. 				if (uncle && uncle->_col == RED)
  121. 				{
  122. 					//父亲和叔叔变黑是为了替代祖父的黑，祖父变红是为了保持黑色节点数量不变
  123. 					parent->_col = uncle->_col = BLACK;//把父亲和叔叔变黑
  124. 					grandfather->_col = RED;//把祖父变红
  125. 					//继续往上处理 -- 将祖父当成新增节点，循环往上处理
  126. 					cur = grandfather;
  127. 					parent = cur->_parent;
  128. 				}
  129. 				//情况二+三,uncle不存在 + 存在且为黑
  130. 				else
  131. 				{
  132. 					//新增在左边:右单旋+变色
  133. 					//      g            p
  134. 					//   p     u  --> c     g 
  135. 					//c                         u
  136. 					if (cur == parent->_left)
  137. 					{
  138. 						RotateR(grandfather);
  139. 						parent->_col = BLACK;
  140. 						grandfather->_col = RED;
  141. 					}
  142. 					//新增在右边:左单旋 + 右双旋+变色
  143. 					//     g
  144. 					//  p     u   -->   
  145. 					//    c
  146. 					else
  147. 					{
  148. 						RotateL(parent);
  149. 						RotateR(grandfather);
  150. 						cur->_col = BLACK;
  151. 						grandfather->_col = RED;
  152. 					}
  153. 					break;
  154. 				}
  155. 			}
  156. 			else//父亲在右边，叔叔可能在左边  (parent == grandfather->_right)
  157. 			{
  158. 				Node* uncle = grandfather->_left;
  159. 				//情况一
  160. 				if (uncle && uncle->_col == RED)
  161. 				{
  162. 					parent->_col = uncle->_col = BLACK;
  163. 					grandfather->_col = RED;
  164. 					//继续往上处理
  165. 					cur = grandfather;
  166. 					parent = cur->_parent;
  167. 				}
  168. 				else //情况二+三,uncle不存在 + 存在且为黑
  169. 				{
  170. 					//新增在右边:左单旋+变色
  171. 					//      g
  172. 					//   u     p
  173. 					//            c
  174. 					if (cur == parent->_right)
  175. 					{
  176. 						RotateL(grandfather);
  177. 						parent->_col = BLACK;
  178. 						grandfather->_col = RED;
  179. 					}
  180. 					//新增在左边:左右双旋+变色
  181. 					//     g
  182. 					//  u     p
  183. 					//       c
  184. 					else
  185. 					{
  186. 						RotateR(parent);
  187. 						RotateL(grandfather);
  188. 						cur->_col = BLACK;
  189. 						grandfather->_col = RED;
  190. 					}
  191.  
  192. 					break;
  193. 				}
  194.  
  195. 			}
  196. 		}
  197. 		//循环结束
  198. 		_root->_col = BLACK;
  199. 		return true;
  200. 	}
  201.  
  202. 	void InOrder()
  203. 	{
  204. 		_InOrder(_root);
  205. 		cout << endl;
  206. 	}
  207. 	bool IsBalance() //根据规则来检查
  208. 	{
  209. 		if (_root && _root->_col == RED)
  210. 		{
  211. 			cout << "根节点不是黑色" << endl;
  212. 			return false;
  213. 		}
  214.  
  215. 		//定义基准值，用来判断每条路径的黑色节点数量是否相同
  216. 		int benchmark = 0;
  217. 		Node* cur = _root;
  218. 		while (cur)
  219. 		{
  220. 			if (cur->_col == BLACK)
  221. 			{
  222. 				++benchmark;
  223. 			}
  224. 			cur = cur->_left;
  225. 		}
  226.  
  227. 		//检查连续红色节点
  228. 		return _Check(_root,0,benchmark);
  229.  
  230. 	}
  231. private:
  232. 	bool _Check(Node* root,int blackNum,int benchmark)
  233. 	{
  234. 		if (root == nullptr)
  235. 		{
  236. 			if (benchmark != blackNum)
  237. 			{
  238. 				cout << "某条路径黑色节点数量不相等";
  239. 				return false;
  240. 			}
  241. 			return true;
  242. 		}
  243. 		if (root->_col == BLACK)
  244. 		{
  245. 			++blackNum;
  246. 		}
  247. 		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
  248. 		{
  249. 			cout << "存在连续红节点" << endl;
  250. 			return false;
  251. 		}
  252. 		return _Check(root->_left,blackNum,benchmark) && _Check(root->_right,blackNum,benchmark);
  253. 	}
  254. 	//左旋转函数
  255. 	void RotateL(Node* parent)
  256. 	{
  257. 		Node* subR = parent->_right;
  258. 		Node* subRL = subR->_left;
  259.  
  260. 		parent->_right = subRL;
  261. 		//subRL可能是空
  262. 		if (subRL)
  263. 		{
  264. 			subRL->_parent = parent;
  265. 		}
  266. 		//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
  267. 		Node* ppNode = parent->_parent;
  268.  
  269. 		subR->_left = parent;
  270. 		parent->_parent = subR;
  271.  
  272. 		//parent是整棵树的根
  273. 		if (_root == parent)
  274. 		{
  275. 			_root = subR;
  276. 			subR->_parent = nullptr;
  277. 		}
  278. 		else//parent是子树的根
  279. 		{
  280. 			if (ppNode->_left == parent)
  281. 			{
  282. 				ppNode->_left = subR;
  283. 			}
  284. 			else
  285. 			{
  286. 				ppNode->_right = subR;
  287. 			}
  288. 			subR->_parent = ppNode;
  289. 		}
  290. 	}
  291. 	//右旋转函数
  292. 	void RotateR(Node* parent)
  293. 	{
  294. 		Node* subL = parent->_left;
  295. 		Node* subLR = subL->_right;
  296.  
  297. 		parent->_left = subLR;
  298. 		//subLR可能是空
  299. 		if (subLR)
  300. 		{
  301. 			subLR->_parent = parent;
  302. 		}
  303. 		//记录一下要旋转的parent节点的_parent，用于当parent是子树根时的调整
  304. 		Node* ppNode = parent->_parent;
  305.  
  306. 		subL->_right = parent;
  307. 		parent->_parent = subL;
  308.  
  309. 		//parent是整颗树的根
  310. 		if (_root == parent)
  311. 		{
  312. 			_root = subL;
  313. 			subL->_parent = nullptr;
  314. 		}
  315. 		else
  316. 		{
  317. 			if (ppNode->_left == parent)
  318. 			{
  319. 				ppNode->_left = subL;
  320. 			}
  321. 			else
  322. 			{
  323. 				ppNode->_right = subL;
  324. 			}
  325. 			subL->_parent = ppNode;
  326. 		}
  327. 	}
  328. 	//打印子函数
  329. 	void _InOrder(Node* root)
  330. 	{
  331. 		if (root == nullptr)
  332. 		{
  333. 			return;
  334. 		}
  335.  
  336. 		_InOrder(root->_left);
  337. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
  338. 		_InOrder(root->_right);
  339. 	}
  340. 	void _Destroy(Node* root)
  341. 	{
  342. 		if (root == nullptr)
  343. 		{
  344. 			return;
  345. 		}
  346. 		_Destroy(root->_left);
  347. 		_Destroy(root->_right);
  348. 		delete root;
  349. 		root == nullptr;
  350. 	}
  351. private:
  352. 	Node* _root = nullptr;
  353. };

测试

  1. #include"RBTree.h"
  2.  
  3. void TestRBTree1()
  4. {
  5. 	int a[] = { 4,2,6,1,3,5,15,7,16,14 };
  6. 	RBTree<int, int> t1;
  7. 	for (auto e : a)
  8. 	{
  9. 		t1.Insert(make_pair(e, e));
  10. 	}
  11. 	cout << "IsBalance:" << t1.IsBalance() << endl;
  12. }
  13.  
  14. void TestRBTree2()
  15. {
  16. 	size_t N = 10000;
  17. 	srand(time(0));
  18. 	RBTree<int, int> t1;
  19. 	for (size_t i = 0; i < N; ++i)
  20. 	{
  21. 		int x = rand();
  22. 		cout << "Insert:" << x << ":" << i << endl;
  23. 		t1.Insert(make_pair(x, i));
  24. 	}
  25. 	cout << "IsBalance:" << t1.IsBalance() << endl;
  26. }
  27.  
  28.  
  29. int main()
  30. {
  31. 	TestRBTree2();
  32. 	cout << endl;
  33. 	TestRBTree1();
  34. 	return 0;
  35. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50980
推荐阅读
相关标签

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

  

闽ICP备14008679号