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

【C++】-- STL之用红黑树模拟实现map和set_stl 红黑树

作者：人工智能uu | 2024-06-20 05:28:05

赞

踩

stl 红黑树

目录

一、map和set类模板​​​​​​

二、红黑树节点定义

1.红黑树的节点修改 

2.仿函数 

（1）节点比较大小时存在的问题 

（2）仿函数

（3）修改红黑树定义

（4）修改红黑树插入

（5）修改红黑树查找

三、红黑树迭代器

1.红黑树中迭代器重命名

2.正向迭代器定义

3.迭代器构造 

4.正向迭代器重载* 

5.正向迭代器重载-> 

6.正向迭代器重载==

7.正向迭代器重载!=

8.正向迭代器++

9.正向迭代器--

10.红黑树中实现迭代器

四、set模拟实现

五、map模拟实现

六、红黑树完整代码段

一、map和set类模板​​​​​​

在【C++】-- STL之map和set详解一文中提到，set用value标识元素(value就是key，类型为T)，并且每个value必须唯一 。

template < class Key>//set

在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair：

typedef pair<const Key, T> value_type;
template < class Key, class T>//map

 用红黑树同时封装出set和map时，set传给value的是一个value，map传给value的是一个pair，set和map传给红黑树的value决定了这棵树里面存的节点值类型。上层容器不同，底层红黑树的Key和T也不同。

 ​​​​​​

在上层容器set中，K和T都代表Key，底层红黑树节点当中存储K和T都是一样的；map中，K代表键值Key，T代表由Key和Value构成的键值对，底层红黑树中只能存储T。所以红黑树为了满足同时支持set和map，节点当中存储T。

这就要对红黑树进行改动。

二、红黑树节点定义

1.红黑树的节点修改 

把【C++】-- 红黑树详解的红黑树节点定义由类模板

template<class K,class V>

修改为

template<class T>

 那么节点定义就修改为

  1. //红黑树节点定义
  2. template<class T>
  3. struct RBTreeNode
  4. {
  5. 	RBTreeNode<T>* _left;//节点的左孩子
  6. 	RBTreeNode<T>* _right;//节点的右孩子
  7. 	RBTreeNode<T>* _parent;//节点的父亲
  8.  
  9. 	T _data;//节点的值，_data里面存的是K就传K，存的是pair就传pair
  10. 	Colour _col;//节点颜色
  11.  
  12. 	RBTreeNode(const T& x)
  13. 		:_left(nullptr)
  14. 		, _right(nullptr)
  15. 		, _parent(nullptr)
  16. 		, _data(x)
  17. 		, _col(RED)
  18. 	{}
  19. };

由于红黑树不知道上层传的是K还是pair，这是由上层传递的模板参数T决定的，上层是封装我的map和set。

2.仿函数 

（1）节点比较大小时存在的问题 

红黑树插入节点时，需要比较节点的大小，kv需要改成_data：

  1. 	//插入
  2. 	pair<Node*, bool> Insert(const T& data)
  3. 	{
  4. 		if (_root == nullptr)
  5. 		{
  6. 			_root = new Node(data);
  7. 			_root->_col = BLACK;
  8. 			return make_pair(_root, true);
  9. 		}
  10.  
  11. 		//1.先看树中，kv是否存在
  12. 		Node* parent = nullptr;
  13. 		Node* cur = _root;
  14. 		while (cur)
  15. 		{
  16. 			if (cur->_data < data)
  17. 			{
  18. 				//kv比当前节点值大，向右走
  19. 				parent = cur;
  20. 				cur = cur->_right;
  21. 			}
  22. 			else if (cur->_data > data)
  23. 			{
  24. 				//kv比当前节点值小，向左走
  25. 				parent = cur;
  26. 				cur = cur->_left;
  27. 			}
  28. 			else
  29. 			{
  30. 				//kv和当前节点值相等，已存在，插入失败
  31. 				return make_pair(cur, false);
  32. 			}
  33. 		}
  34.  
  35. 		//2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了
  36. 		Node* newNode = new Node(kv);
  37. 		newNode->_col = RED;
  38. 		if (parent->_data < data)
  39. 		{
  40. 			//kv比parent值大，插入到parent的右边
  41. 			parent->_right = newNode;
  42. 			newNode->_parent = parent;
  43. 		}
  44. 		else
  45. 		{
  46. 			//kv比parent值小，插入到parent的左边
  47. 			parent->_left = newNode;
  48. 			newNode->_parent = parent;
  49. 		}
  50. 		cur = newNode;
  51. 		
  52.         //如果父亲存在，且父亲颜色为红就要处理
  53. 		while (parent && parent->_col == RED)
  54. 		{
  55. 			//情况一和情况二、三的区别关键看叔叔
  56. 			Node* grandfather = parent->_parent;//当父亲是红色时，根据规则（2）根节点一定是黑色，祖父一定存在
  57. 			if (parent == grandfather->_left)//父亲是祖父的左子树
  58. 			{
  59. 				Node* uncle = grandfather->_right;
  60. 				//情况一：叔叔存在且为红
  61. 				if (uncle->_col == RED)
  62. 				{
  63. 					parent->_col = uncle->_col = BLACK;
  64. 					grandfather->_col = RED;
  65.  
  66. 					//继续向上调整
  67. 					cur = grandfather;
  68. 					parent = cur->_parent;
  69. 				}
  70. 				else//情况二+情况三：叔叔不存在或叔叔存在且为黑
  71. 				{
  72. 					//情况二：单旋
  73. 					if (cur == parent->_left)
  74. 					{
  75. 						RotateR(grandfather);
  76. 						parent->_col = BLACK;
  77. 						grandfather->_col = RED;
  78. 					}
  79. 					else//情况三：双旋
  80. 					{
  81. 						RotateL(parent);
  82. 						RotateR(grandfather);
  83. 						cur->_col = BLACK;
  84. 						grandfather->_col = RED;
  85. 					}
  86. 					break;//插入结束
  87. 				}
  88. 			}
  89. 			else//父亲是祖父的右子树
  90. 			{
  91. 				Node* uncle = grandfather->_left;
  92. 				//情况一：叔叔存在且为红
  93. 				if (uncle && uncle->_col == RED)
  94. 				{
  95. 					parent->_col = uncle->_col = BLACK;
  96. 					grandfather->_col = RED;
  97.  
  98. 					//继续往上调整
  99. 					cur = grandfather;
  100. 					parent = grandfather->_parent;
  101. 				}
  102. 				else//情况二+情况三：叔叔不存在或叔叔存在且为黑
  103. 				{
  104. 					//情况二：单旋
  105. 					if (cur == parent->_right)
  106. 					{
  107. 						RotateL(grandfather);
  108. 						parent->_col = BLACK;
  109. 						grandfather->_col = RED;
  110. 					}
  111. 					else//情况三：双旋
  112. 					{
  113. 						RotateR(parent);
  114. 						RotateL(grandfather);
  115. 						cur->_col = BLACK;
  116. 						grandfather->_col = RED;
  117. 					}
  118. 					break;//插入结束
  119. 				}
  120. 			}
  121.  
  122. 		}
  123. 		_root->_col = BLACK;
  124.  
  125. 		return make_pair(newNode, true);
  126. 	}

但是以上代码在插入新节和查找节点时，当和当前节点比较大小时，Key可以比较，但是pair比较不了，也就是set可以比较，但是map比较不了。这就需要写一个仿函数，如果是map就取_data里面的first也就是Key进行比较，通过泛型解决红黑树里面存的是什么。所以上层容器map需要向底层的红黑树提供仿函数来获取T里面的Key，这样无论上层容器是set还是map，都可以用统一的方式进行比较了。

（2）仿函数

仿函数让一个类的使用看上去像个函数。仿函数是在类中实现了一个operator( )，是一个类的对象，这个类就有了类似函数的行为，所以这个类就是一个仿函数类，目的是为了让函数拥有类的性质。

这个类的对象即仿函数，可以当作一般函数去用，只不过仿函数的功能是在一个类中的运算符operator()中实现的，使用的时候把函数作为参进行传递即可。更详细的理解请参考【C++】-- STL容器适配器之priority_queue第三节第1小节的内容。

set有set的仿函数，map有map的仿函数，尽管set的仿函数看起来没有什么作用，但是，必须要把它传给底层红黑树，这样红黑树就能根据仿函数分别获取set的key和map的first。

 ①set的仿函数

  1. namespace delia
  2. {
  3. 	template<class K>
  4. 	class set
  5. 	{
  6. 		//仿函数，获取set的key
  7. 		struct SetKeyOfT
  8. 		{
  9. 			const K& operator()(const K& key)
  10. 			{
  11. 				return key;
  12. 			}
  13. 		};
  14.     
  15.     public:
  16. 		bool insert(const K& k)
  17. 		{
  18. 			_t.Insert(k);
  19. 			return true;
  20. 		}
  21.  
  22. 	private:
  23. 		RBTree<K, K,SetKeyOfT> _t;
  24. 	};
  25. }

 ②map的仿函数

  1. namespace delia
  2. {
  3. 	template<class K,class V>
  4. 	class map
  5. 	{
  6. 		//仿函数，获取map的first
  7. 		struct MapKeyOfT
  8. 		{
  9. 			const K& operator()(const pair<const K, V>& kv)
  10. 			{
  11. 				return kv.first;
  12. 			}
  13. 		};
  14.  
  15.     public:
  16.         //插入
  17. 		bool insert(const pair<const K, V>& kv)
  18. 		{
  19. 			_t.Insert(kv);
  20. 			return true;
  21. 		}
  22. 	private:
  23. 		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  24. 	};
  25. }

 有了仿函数红黑树的类在实现时，就要在模板参数中增加KeyOfT仿函数。

（3）修改红黑树定义

  1. template<class K, class T, class KeyOfT>
  2. class RBTree
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5. 	
  6. private:
  7. 	Node* _root;
  8. };

（4）修改红黑树插入

  1. 	//插入
  2. 	pair<Node*, bool> Insert(const pair<K, V>& kv)
  3. 	{
  4. 		if (_root == nullptr)
  5. 		{
  6. 			_root = new Node(kv);
  7. 			_root->_col = BLACK;
  8. 			return make_pair(_root, true);
  9. 		}
  10.  
  11. 		KeyOfT kot;
  12.  
  13. 		//1.先看树中，kv是否存在
  14. 		Node* parent = nullptr;
  15. 		Node* cur = _root;
  16. 		while (cur)
  17. 		{
  18. 			if (kot(cur->_data) < kot(data))
  19. 			{
  20. 				//kv比当前节点值大，向右走
  21. 				parent = cur;
  22. 				cur = cur->_right;
  23. 			}
  24. 			else if (kot(cur->_data) > kot(data))
  25. 			{
  26. 				//kv比当前节点值小，向左走
  27. 				parent = cur;
  28. 				cur = cur->_left;
  29. 			}
  30. 			else
  31. 			{
  32. 				//kv和当前节点值相等，已存在，插入失败
  33. 				return make_pair(cur, false);
  34. 			}
  35. 		}
  36.  
  37. 		//2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了
  38. 		Node* newNode = new Node(kv);
  39. 		newNode->_col = RED;
  40. 		if (kot(parent->_data) < kot(data))
  41. 		{
  42. 			//kv比parent值大，插入到parent的右边
  43. 			parent->_right = newNode;
  44. 			newNode->_parent = parent;
  45. 		}
  46. 		else
  47. 		{
  48. 			//kv比parent值小，插入到parent的左边
  49. 			parent->_left = newNode;
  50. 			newNode->_parent = parent;
  51. 		}
  52. 		cur = newNode;
  53.  
  54. 		//如果父亲存在，且父亲颜色为红就要处理
  55. 		while (parent && parent->_col == RED)
  56. 		{
  57. 			//情况一和情况二、三的区别关键看叔叔
  58. 			Node* grandfather = parent->_parent;//当父亲是红色时，根据规则（2）根节点一定是黑色，祖父一定存在
  59. 			if (parent == grandfather->_left)//父亲是祖父的左子树
  60. 			{
  61. 				Node* uncle = grandfather->_right;
  62. 				//情况一：叔叔存在且为红
  63. 				if (uncle->_col == RED)
  64. 				{
  65. 					parent->_col = uncle->_col = BLACK;
  66. 					grandfather->_col = RED;
  67.  
  68. 					//继续向上调整
  69. 					cur = grandfather;
  70. 					parent = cur->_parent;
  71. 				}
  72. 				else//情况二+情况三：叔叔不存在或叔叔存在且为黑
  73. 				{
  74. 					//情况二：单旋
  75. 					if (cur == parent->_left)
  76. 					{
  77. 						RotateR(grandfather);
  78. 						parent->_col = BLACK;
  79. 						grandfather->_col = RED;
  80. 					}
  81. 					else//情况三：双旋
  82. 					{
  83. 						RotateL(parent);
  84. 						RotateR(grandfather);
  85. 						cur->_col = BLACK;
  86. 						grandfather->_col = RED;
  87. 					}
  88. 					break;//插入结束
  89. 				}
  90. 			}
  91. 			else//父亲是祖父的右子树
  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. 					//继续往上调整
  101. 					cur = grandfather;
  102. 					parent = grandfather->_parent;
  103. 				}
  104. 				else//情况二+情况三：叔叔不存在或叔叔存在且为黑
  105. 				{
  106. 					//情况二：单旋
  107. 					if (cur == parent->_right)
  108. 					{
  109. 						RotateL(grandfather);
  110. 						parent->_col = BLACK;
  111. 						grandfather->_col = RED;
  112. 					}
  113. 					else//情况三：双旋
  114. 					{
  115. 						RotateR(parent);
  116. 						RotateL(grandfather);
  117. 						cur->_col = BLACK;
  118. 						grandfather->_col = RED;
  119. 					}
  120. 					break;//插入结束
  121. 				}
  122. 			}
  123.  
  124. 		}
  125. 		_root->_col = BLACK;
  126.  
  127. 		return make_pair(newNode, true);
  128. 	}
  129.  
  130. 	void RotateR(Node* parent)
  131. 	{
  132. 		Node* subL = parent->_left;
  133. 		Node* subLR = nullptr;
  134.  
  135. 		if (subL)
  136. 		{
  137. 			subLR = subL->_right;
  138. 		}
  139. 		//1.左子树的右子树变我的左子树
  140. 		parent->_left = subLR;
  141.  
  142. 		if (subLR)
  143. 		{
  144. 			subLR->_parent = parent;
  145. 		}
  146.  
  147. 		//左子树变父亲
  148. 		subL->_right = parent;
  149. 		Node* parentParent = parent->_parent;
  150. 		parent->_parent = subL;
  151.  
  152.  
  153. 		if (parent == _root)//parent是根
  154. 		{
  155. 			_root = subL;
  156. 			_root->_parent = nullptr;
  157. 		}
  158. 		else//parent不是根，是子树
  159. 		{
  160. 			if (parentParent->_left == parent)
  161. 			{
  162. 				//parent是自己父亲的左子树,将subL作为parent父亲的左孩子
  163. 				parentParent->_left = subL;
  164. 			}
  165. 			else
  166. 			{
  167. 				//parent是自己父亲的右子树,将subL作为parent父亲的右孩子
  168. 				parentParent->_right = subL;
  169. 			}
  170.  
  171. 			//subL的父亲就是parent的父亲
  172. 			subL->_parent = parentParent;
  173. 		}
  174. 	}
  175.  
  176. 	void RotateL(Node* parent)
  177. 	{
  178. 		Node* subR = parent->_right;
  179. 		Node* subRL = nullptr;
  180.  
  181. 		if (subR)
  182. 		{
  183. 			subRL = subR->_left;
  184. 		}
  185.  
  186. 		//1.右子树的左子树变我的右子树
  187. 		parent->_right = subRL;
  188.  
  189. 		if (subRL)
  190. 		{
  191. 			subRL->_parent = parent;
  192. 		}
  193.  
  194. 		//2.右子树变父亲
  195. 		subR->_left = parent;
  196. 		Node* parentParent = parent->_parent;
  197. 		parent->_parent = subR;
  198.  
  199. 		if (parent == _root)//parent是根
  200. 		{
  201. 			_root = parent;
  202. 			_root->_parent = nullptr;
  203. 		}
  204. 		else//parent不是根，是子树
  205. 		{
  206. 			if (parentParent->_left == parent)
  207. 			{
  208. 				//parent是自己父亲的左子树,将subR作为parent父亲的左孩子
  209. 				parentParent->_left = subR;
  210. 			}
  211. 			else
  212. 			{
  213. 				//parent是自己父亲的右子树,将subR作为parent父亲的右孩子
  214. 				parentParent->_right = subR;
  215. 			}
  216.  
  217. 			//subR的父亲就是parent的父亲
  218. 			subR->_parent = parentParent;
  219. 		}
  220. 	}

（5）修改红黑树查找

  1. 	//查找
  2. 	Node* Find(const K& key)
  3. 	{
  4. 		KeyOfT kot;
  5. 		Node* cur = _root;
  6. 		while (cur)
  7. 		{
  8. 			if (kot(cur->_data) < key)
  9. 			{
  10. 				cur = cur->_right;
  11. 			}
  12. 			else if (kot(cur->_data) > key)
  13. 			{
  14. 				cur = cur->_left;
  15. 			}
  16. 			else
  17. 			{
  18. 				return cur;
  19. 			}
  20. 		}
  21. 		return nullptr;//空树，直接返回
  22. 	}

三、红黑树迭代器

map和set的迭代器的实现其实本质上是红黑树迭代器的实现，迭代器的实现需要定义模板类型、模板类型引用、模板类型指针。 

1.红黑树中迭代器重命名

 在红黑树中重命名模板类型、模板类型引用、模板类型指针，定义为public，外部就能使用iterator了：

  1. template<class K, class T, class KeyOfT>
  2. class RBTree
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5.  
  6. public:
  7. 	typedef __TreeIterator<T, T&, T*> iterator;//模板类型、模板类型引用、模板类型指针
  8.     
  9.     //红黑树函数...
  10.     
  11. private:
  12. 	Node* _root;
  13. };

2.正向迭代器定义

红黑树的迭代器的本质是对节点指针进行封装，所以迭代器中只有封装红黑树节点指针这一个成员变量 。正向迭代器：

  1. template<class T,class Ref,class ptr>
  2. struct __TreeIterator
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5. 	typedef __TreeIterator<T, Ref, ptr> Self;
  6.       
  7. 	Node* _node;//成员变量
  8. 	
  9. };

3.迭代器构造 

用节点指针构造正向迭代器：

  1. 	//构造函数
  2. 	__TreeIterator(Node* node)
  3. 		:_node(node)
  4. 	{}

4.正向迭代器重载* 

Ref对正向迭代器解引用，返回节点数据引用：

  1. 	//* 解引用，返回节点数据
  2. 	Ref Operator*()
  3. 	{
  4. 		return _node->_data;
  5. 	}

5.正向迭代器重载-> 

Ptr对正向迭代器使用->，返回节点数据指针：

  1. 	//-> 返回节点数据地址
  2. 	Ptr Operator->()
  3. 	{
  4. 		return &_node->_data;
  5. 	}

6.正向迭代器重载==

判断节点是否相同 

  1. 	//判断两个迭代器是否相同
  2. 	bool operator==(const Self& s)
  3. 	{
  4. 		return _node == s._node;//判断节点是否相同
  5. 	}

7.正向迭代器重载!=

判断节点是否不同 

  1. 	//判断两个迭代器是否不同
  2. 	bool operator!=(const Self& s)
  3. 	{
  4. 		return _node != s._node;//判断节点是否不同
  5. 	}

8.正向迭代器++

 ①当节点的右子树不为空时，++就要走到右子树的最左节点

 ②当节点的右子树为空时，++就要走到节点的父亲

  1. 	//红黑树迭代器的++也就是红黑树的++
  2. 	Self operator++()
  3. 	{
  4. 		//1.右子树不为空
  5. 		if (_node->_right)
  6. 		{
  7. 			//下一个访问的是右树的中序第一个节点（即右子树最左节点）。
  8. 			Node* left = _node->_right;
  9.  
  10. 			//找最左节点
  11. 			while (left->_left)
  12. 			{
  13. 				left = left->_left;
  14. 			}
  15. 			_node = left;
  16. 		}
  17. 		else//2.右子树为空，下一个访问的就是当前节点的父亲
  18. 		{
  19. 			Node* cur = _node;
  20. 			Node* parent = cur->_parent;
  21. 			while (parent && cur == parent->_right)
  22. 			{
  23. 				cur = cur->_parent;
  24. 				parent = parent->_parent;
  25. 			}
  26. 			_node = parent;
  27. 		}
  28.  
  29. 		return *this;
  30. 	}
  31. };

9.正向迭代器--

 ①当节点的左子树不为空时，++就要走到左子树的最右节点

 ②当节点的左子树为空时，++就要走到节点的父亲

  1. 	//红黑树迭代器的--也就是红黑树的--
  2. 	Self operator--()
  3. 	{
  4. 		//1.左子树不为空
  5. 		if (_node->_left)
  6. 		{
  7. 			//下一个访问的是左树的中序左后节点（即做子树最右节点）。
  8. 			Node* right = _node->_left;
  9.  
  10. 			//找最右节点
  11. 			while (right->_right)
  12. 			{
  13. 				right = right->_right;
  14. 			}
  15. 			_node = right;
  16. 		}
  17. 		else//2.左子树为空，下一个访问的就是当前节点的父亲
  18. 		{
  19. 			Node* cur = _node;
  20. 			Node* parent = cur->_parent;
  21. 			while (parent && cur == parent->_left)
  22. 			{
  23. 				cur = cur->_parent;
  24. 				parent = parent->_parent;
  25. 			}
  26. 			_node = parent;
  27. 		}
  28.  
  29. 		return *this;
  30. 	}

10.红黑树中实现迭代器

 实现begin( )找最左节点，end( )最后一个节点的下一个位置

  1. template<class K, class T, class KeyOfT>
  2. class RBTree
  3. {
  4. 	typedef RBTreeNode<T> Node;
  5.  
  6. public:
  7. 	typedef __TreeIterator<T, T&, T*> iterator;//模板类型、模板类型引用、模板类型指针
  8.     
  9.     //找最左节点
  10. 	iterator begin()
  11. 	{
  12. 		Node* left = _root;
  13. 		while (left && left->_left)
  14. 		{
  15. 			left = left->_left;
  16. 		}
  17.  
  18. 		return iterator(left)//返回最左节点的正向迭代器
  19. 	}
  20.  
  21. 	//结束
  22. 	iterator end()
  23. 	{
  24. 		return iterator(nullptr);
  25. 	}
  26.     
  27. private:
  28. 	Node* _root;
  29. };

四、set模拟实现

调用红黑树对应接口实现set，插入和查找函数返回值当中的节点指针改为迭代器:

  1. #pragma once
  2. #include "RBTree.h"
  3. namespace delia
  4. {
  5. 	template<class K>
  6. 	class set
  7. 	{
  8. 		//仿函数，获取set的key
  9. 		struct SetKeyOfT
  10. 		{
  11. 			const K& operator()(const K& key)
  12. 			{
  13. 				return key;
  14. 			}
  15. 		};
  16. 	public:
  17. 		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
  18. 		
  19. 		//迭代器开始
  20. 		iterator begin()
  21. 		{
  22. 			return _t.begin();
  23. 		}
  24.  
  25. 		//迭代器结束
  26. 		iterator end()
  27. 		{
  28. 			return _t.end();
  29. 		}
  30.  
  31. 		//插入函数
  32. 		pair<iterator,bool> insert(const K& key)
  33. 		{
  34. 			
  35. 			return _t.Insert(key);
  36. 		}
  37.  
  38. 		//查找
  39. 		iterator find(const K& key)
  40. 		{
  41. 			return _t.find(key);
  42. 		}
  43. 	private:
  44. 		RBTree<K, K, SetKeyOfT> _t;
  45. 	};
  46. }

五、map模拟实现

调用红黑树对应接口实现map，插入和查找函数返回值当中的节点指针改为迭代器，增加operator[ ]的重载:

  1. #pragma once
  2. #include "RBTree.h"
  3. namespace delia
  4. {
  5. 	template<class K, class V>
  6. 	class map
  7. 	{
  8. 		//仿函数，获取map的first
  9. 		struct MapKeyOfT
  10. 		{
  11. 			const K& operator()(const pair<const K, V>& kv)
  12. 			{
  13. 				return kv.first;
  14. 			}
  15. 		};
  16. 	public:
  17. 		typedef typename RBTree<K, K, MapKeyOfT>::iterator iterator;
  18.  
  19. 		//迭代器开始
  20. 		iterator begin()
  21. 		{
  22. 			return _t.begin();
  23. 		}
  24.  
  25. 		//迭代器结束
  26. 		iterator end()
  27. 		{
  28. 			return _t.end();
  29. 		}
  30.  
  31. 		//插入
  32. 		pair<iterator, bool> insert(const pair<const K, V>& kv)
  33. 		{
  34. 			return _t.Insert(kv);
  35. 		}
  36.  
  37. 		//重载operator[]
  38. 		V& operator[](const K& key)
  39. 		{
  40. 			pair<iterator, bool> ret = insert(make_pair(key, V()));
  41. 			iterator it = ret.first;
  42. 			return it->second;
  43. 		}
  44.  
  45. 		//查找
  46. 		iterator find(const K& key)
  47. 		{
  48. 			return _t.find(key);
  49. 		}
  50.  
  51. 	private:
  52. 		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  53. 	};
  54. }

六、红黑树完整代码段

  1. #pragma once
  2. #include<iostream>
  3. using namespace std;
  4.  
  5.  
  6. //节点颜色
  7. enum Colour
  8. {
  9. 	RED,
  10. 	BLACK,
  11. };
  12.  
  13. //红黑树节点定义
  14. template<class T>
  15. struct RBTreeNode
  16. {
  17. 	RBTreeNode<T>* _left;//节点的左孩子
  18. 	RBTreeNode<T>* _right;//节点的右孩子
  19. 	RBTreeNode<T>* _parent;//节点的父亲
  20.  
  21. 	T _data;//节点的值
  22. 	Colour _col;//节点颜色
  23.  
  24. 	RBTreeNode(const T& x)
  25. 		:_left(nullptr)
  26. 		, _right(nullptr)
  27. 		, _parent(nullptr)
  28. 		, _data(x)
  29. 		, _col(RED)
  30. 	{}
  31. };
  32.  
  33.  
  34. template<class T,class Ref,class ptr>
  35. struct __TreeIterator
  36. {
  37. 	typedef RBTreeNode<T> Node;
  38. 	typedef __TreeIterator<T, Ref, ptr> Self;
  39.  
  40. 	Node* _node;
  41.  
  42. 	//构造函数
  43. 	__TreeIterator(Node* node)
  44. 		:_node(node)
  45. 	{}
  46. 	
  47. 	//* 解引用，返回节点数据
  48. 	Ref operator*()
  49. 	{
  50. 		return _node->_data;
  51. 	}
  52.  
  53. 	//-> 返回节点数据地址
  54. 	//Ptr operator->()
  55. 	//{
  56. 	//	return &_node->_data;
  57. 	//}
  58.  
  59. 	//判断两个迭代器是否相同
  60. 	bool operator==(const Self& s)
  61. 	{
  62. 		return _node == s._node;
  63. 	}
  64.  
  65. 	//判断两个迭代器是否不同
  66. 	bool operator!=(const Self& s)
  67. 	{
  68. 		return _node != s._node;
  69. 	}
  70.  
  71. 	//红黑树迭代器的++也就是红黑树的++
  72. 	Self operator++()
  73. 	{
  74. 		//1.右子树不为空
  75. 		if (_node->_right)
  76. 		{
  77. 			//下一个访问的是右树的中序第一个节点（即右子树最左节点）。
  78. 			Node* left = _node->_right;
  79.  
  80. 			//找最左节点
  81. 			while (left->_left)
  82. 			{
  83. 				left = left->_left;
  84. 			}
  85. 			_node = left;
  86. 		}
  87. 		else//2.右子树为空，下一个访问的就是当前节点的父亲
  88. 		{
  89. 			Node* cur = _node;
  90. 			Node* parent = cur->_parent;
  91. 			while (parent && cur == parent->_right)
  92. 			{
  93. 				cur = cur->_parent;
  94. 				parent = parent->_parent;
  95. 			}
  96. 			_node = parent;
  97. 		}
  98.  
  99. 		return *this;
  100. 	}
  101.  
  102. 	//红黑树迭代器的--也就是红黑树的--
  103. 	Self operator--()
  104. 	{
  105. 		//1.左子树不为空
  106. 		if (_node->_left)
  107. 		{
  108. 			//下一个访问的是左树的中序左后节点（即做子树最右节点）。
  109. 			Node* right = _node->_left;
  110.  
  111. 			//找最右节点
  112. 			while (right->_right)
  113. 			{
  114. 				right = right->_right;
  115. 			}
  116. 			_node = right;
  117. 		}
  118. 		else//2.左子树为空，下一个访问的就是当前节点的父亲
  119. 		{
  120. 			Node* cur = _node;
  121. 			Node* parent = cur->_parent;
  122. 			while (parent && cur == parent->_left)
  123. 			{
  124. 				cur = cur->_parent;
  125. 				parent = parent->_parent;
  126. 			}
  127. 			_node = parent;
  128. 		}
  129.  
  130. 		return *this;
  131. 	}
  132.  
  133.  
  134. };
  135.  
  136. //插入节点颜色是红色好，还是黑色好，红色
  137. //因为插入红色节点，可能破坏规则3，影响不大
  138. //插入黑色节点，一定破坏规则4 ，并且影响其他路径，影响很大
  139.  
  140. template<class K, class T, class KeyOfT>
  141. class RBTree
  142. {
  143. 	typedef RBTreeNode<T> Node;
  144. public:
  145. 	typedef __TreeIterator<T, T&, T*> iterator;//模板类型、模板类型引用、模板类型指针
  146.  
  147. 	//构造函数
  148. 	RBTree()
  149. 		:_root(nullpte)
  150. 	{}
  151.  
  152. 	//析构
  153. 	~RBTree()
  154. 	{
  155. 		_Destroy(_root);
  156. 		_root = nullptr;
  157. 	}
  158.  
  159. 	void _Destroy(Node* root)
  160. 	{
  161. 		if (root == nullptr)
  162. 		{
  163. 			return;
  164. 		}
  165. 		_Destroy(root->_left);
  166. 		_Destroy(root->_right);
  167. 		delete root;
  168. 	}
  169.  
  170. 	//找最左节点
  171. 	iterator begin()
  172. 	{
  173. 		Node* left = _root;
  174. 		while (left && left->_left)
  175. 		{
  176. 			left = left->_left;
  177. 		}
  178.  
  179. 		return iterator(left);//返回最左节点的正向迭代器
  180. 	}
  181.  
  182. 	//结束
  183. 	iterator end()
  184. 	{
  185. 		return iterator(nullptr);
  186. 	}
  187.  
  188. 	//构造函数
  189. 	RBTree()
  190. 		:_root(nullptr)
  191. 	{}
  192.  
  193. 	void Destroy(Node* root)
  194. 	{
  195. 		if (root == nullptr)
  196. 		{
  197. 			return;
  198. 		}
  199.  
  200. 		Destroy(root->_left);
  201. 		Destroy(root->_right);
  202. 	}
  203. 	~RBTree()
  204. 	{
  205. 		Destroy(_root);
  206. 		_root = nullptr;
  207. 	}
  208.  
  209. 	//插入
  210. 	pair<Node*, bool> Insert(const T& data)
  211. 	{
  212. 		if (_root == nullptr)
  213. 		{
  214. 			_root = new Node(data);
  215. 			_root->_col = BLACK;
  216. 			return make_pair(_root, true);
  217. 		}
  218.  
  219. 		KeyOfT kot;
  220.  
  221. 		//1.先看树中，kv是否存在
  222. 		Node* parent = nullptr;
  223. 		Node* cur = _root;
  224. 		while (cur)
  225. 		{
  226. 			if (kot(cur->_data) < kot(data))
  227. 			{
  228. 				//kv比当前节点值大，向右走
  229. 				parent = cur;
  230. 				cur = cur->_right;
  231. 			}
  232. 			else if (kot(cur->_data) > kot(data))
  233. 			{
  234. 				//kv比当前节点值小，向左走
  235. 				parent = cur;
  236. 				cur = cur->_left;
  237. 			}
  238. 			else
  239. 			{
  240. 				//kv和当前节点值相等，已存在，插入失败
  241. 				return make_pair(cur, false);
  242. 			}
  243. 		}
  244.  
  245. 		//2.走到这里，说明kv在树中不存在，需要插入kv，并且cur已经为空，parent已经是叶子节点了
  246. 		Node* newNode = new Node(data);
  247. 		newNode->_col = RED;
  248. 		if (kot(parent->_data) < kot(data))
  249. 		{
  250. 			//kv比parent值大，插入到parent的右边
  251. 			parent->_right = newNode;
  252. 			newNode->_parent = parent;
  253. 		}
  254. 		else
  255. 		{
  256. 			//kv比parent值小，插入到parent的左边
  257. 			parent->_left = newNode;
  258. 			newNode->_parent = parent;
  259. 		}
  260. 		cur = newNode;
  261.  
  262. 		//如果父亲存在，且父亲颜色为红就要处理
  263. 		while (parent && parent->_col == RED)
  264. 		{
  265. 			//情况一和情况二、三的区别关键看叔叔
  266. 			Node* grandfather = parent->_parent;//当父亲是红色时，根据规则（2）根节点一定是黑色，祖父一定存在
  267. 			if (parent == grandfather->_left)//父亲是祖父的左子树
  268. 			{
  269. 				Node* uncle = grandfather->_right;
  270. 				//情况一：叔叔存在且为红
  271. 				if (uncle->_col == RED)
  272. 				{
  273. 					parent->_col = uncle->_col = BLACK;
  274. 					grandfather->_col = RED;
  275.  
  276. 					//继续向上调整
  277. 					cur = grandfather;
  278. 					parent = cur->_parent;
  279. 				}
  280. 				else//情况二+情况三：叔叔不存在或叔叔存在且为黑
  281. 				{
  282. 					//情况二：单旋
  283. 					if (cur == parent->_left)
  284. 					{
  285. 						RotateR(grandfather);
  286. 						parent->_col = BLACK;
  287. 						grandfather->_col = RED;
  288. 					}
  289. 					else//情况三：双旋
  290. 					{
  291. 						RotateL(parent);
  292. 						RotateR(grandfather);
  293. 						cur->_col = BLACK;
  294. 						grandfather->_col = RED;
  295. 					}
  296. 					break;//插入结束
  297. 				}
  298. 			}
  299. 			else//父亲是祖父的右子树
  300. 			{
  301. 				Node* uncle = grandfather->_left;
  302. 				//情况一：叔叔存在且为红
  303. 				if (uncle && uncle->_col == RED)
  304. 				{
  305. 					parent->_col = uncle->_col = BLACK;
  306. 					grandfather->_col = RED;
  307.  
  308. 					//继续往上调整
  309. 					cur = grandfather;
  310. 					parent = grandfather->_parent;
  311. 				}
  312. 				else//情况二+情况三：叔叔不存在或叔叔存在且为黑
  313. 				{
  314. 					//情况二：单旋
  315. 					if (cur == parent->_right)
  316. 					{
  317. 						RotateL(grandfather);
  318. 						parent->_col = BLACK;
  319. 						grandfather->_col = RED;
  320. 					}
  321. 					else//情况三：双旋
  322. 					{
  323. 						RotateR(parent);
  324. 						RotateL(grandfather);
  325. 						cur->_col = BLACK;
  326. 						grandfather->_col = RED;
  327. 					}
  328. 					break;//插入结束
  329. 				}
  330. 			}
  331.  
  332. 		}
  333. 		_root->_col = BLACK;
  334.  
  335. 		return make_pair(newNode, true);
  336. 	}
  337.  
  338. 	void RotateR(Node* parent)
  339. 	{
  340. 		Node* subL = parent->_left;
  341. 		Node* subLR = nullptr;
  342.  
  343. 		if (subL)
  344. 		{
  345. 			subLR = subL->_right;
  346. 		}
  347. 		//1.左子树的右子树变我的左子树
  348. 		parent->_left = subLR;
  349.  
  350. 		if (subLR)
  351. 		{
  352. 			subLR->_parent = parent;
  353. 		}
  354.  
  355. 		//左子树变父亲
  356. 		subL->_right = parent;
  357. 		Node* parentParent = parent->_parent;
  358. 		parent->_parent = subL;
  359.  
  360.  
  361. 		if (parent == _root)//parent是根
  362. 		{
  363. 			_root = subL;
  364. 			_root->_parent = nullptr;
  365. 		}
  366. 		else//parent不是根，是子树
  367. 		{
  368. 			if (parentParent->_left == parent)
  369. 			{
  370. 				//parent是自己父亲的左子树,将subL作为parent父亲的左孩子
  371. 				parentParent->_left = subL;
  372. 			}
  373. 			else
  374. 			{
  375. 				//parent是自己父亲的右子树,将subL作为parent父亲的右孩子
  376. 				parentParent->_right = subL;
  377. 			}
  378.  
  379. 			//subL的父亲就是parent的父亲
  380. 			subL->_parent = parentParent;
  381. 		}
  382. 	}
  383.  
  384. 	void RotateL(Node* parent)
  385. 	{
  386. 		Node* subR = parent->_right;
  387. 		Node* subRL = nullptr;
  388.  
  389. 		if (subR)
  390. 		{
  391. 			subRL = subR->_left;
  392. 		}
  393.  
  394. 		//1.右子树的左子树变我的右子树
  395. 		parent->_right = subRL;
  396.  
  397. 		if (subRL)
  398. 		{
  399. 			subRL->_parent = parent;
  400. 		}
  401.  
  402. 		//2.右子树变父亲
  403. 		subR->_left = parent;
  404. 		Node* parentParent = parent->_parent;
  405. 		parent->_parent = subR;
  406.  
  407. 		if (parent == _root)//parent是根
  408. 		{
  409. 			_root = parent;
  410. 			_root->_parent = nullptr;
  411. 		}
  412. 		else//parent不是根，是子树
  413. 		{
  414. 			if (parentParent->_left == parent)
  415. 			{
  416. 				//parent是自己父亲的左子树,将subR作为parent父亲的左孩子
  417. 				parentParent->_left = subR;
  418. 			}
  419. 			else
  420. 			{
  421. 				//parent是自己父亲的右子树,将subR作为parent父亲的右孩子
  422. 				parentParent->_right = subR;
  423. 			}
  424.  
  425. 			//subR的父亲就是parent的父亲
  426. 			subR->_parent = parentParent;
  427. 		}
  428. 	}
  429.  
  430. 	//查找
  431. 	Node* Find(const K& key)
  432. 	{
  433. 		KeyOfT kot;
  434. 		Node* cur = _root;
  435. 		while (cur)
  436. 		{
  437. 			if (kot(cur->_data) < key)
  438. 			{
  439. 				cur = cur->_right;
  440. 			}
  441. 			else if (kot(cur->_data) > key)
  442. 			{
  443. 				cur = cur->_left;
  444. 			}
  445. 			else
  446. 			{
  447. 				return cur;
  448. 			}
  449. 		}
  450. 		return nullptr;//空树，直接返回
  451. 	}
  452.  
  453. 	bool _CheckBalance(Node* root, int blackNum, int count)
  454. 	{
  455. 		if (root == nullptr)
  456. 		{
  457. 			if (count != blackNum)
  458. 			{
  459. 				cout << "黑色节点数量不相等" << endl;
  460. 				return false;
  461. 			}
  462. 			return true;
  463. 		}
  464.  
  465. 		if (root->_col == RED && root->_parent->_col == RED)
  466. 		{
  467. 			cout << "存在连续红色节点" << endl;
  468. 			return false;
  469. 		}
  470.  
  471. 		if (root->_col == BLACK)
  472. 		{
  473. 			count++;
  474. 		}
  475.  
  476. 		return _CheckBalance(root->_left, blackNum, count)
  477. 			&& _CheckBalance(root->_right, blackNum, count);
  478. 	}
  479.  
  480. 	//检查是否平衡
  481. 	bool CheckBalance()
  482. 	{
  483. 		if (_root == nullptr)
  484. 		{
  485. 			return true;
  486. 		}
  487.  
  488. 		if (_root->_col == RED)
  489. 		{
  490. 			cout << "根节点为红色" << endl;
  491. 			return false;
  492. 		}
  493.  
  494. 		//找最左路径做黑色节点数量参考值
  495. 		int blackNum = 0;
  496. 		Node* left = _root;
  497. 		while (left)
  498. 		{
  499. 			if (left->_col == BLACK)
  500. 			{
  501. 				blackNum++;
  502. 			}
  503. 			left = left->_left;
  504. 		}
  505.  
  506. 		int count = 0;
  507. 		return _CheckBalance(_root, blackNum, count);
  508. 	}
  509.  
  510.  
  511. 	//遍历
  512. 	void _InOrder(Node* root)
  513. 	{
  514. 		if (root == nullptr)
  515. 		{
  516. 			return;
  517. 		}
  518.  
  519. 		_InOrder(root->_left);
  520. 		cout << root->_kv.first << ":" << root->_kv.second << endl;
  521. 		_InOrder(root->_right);
  522. 	}
  523.  
  524. 	void InOrder()
  525. 	{
  526. 		_InOrder(_root);
  527. 		cout << endl;
  528. 	}
  529. private:
  530. 	Node* _root;
  531. };

验证代码：

  1. #pragma once
  2. #include "RBTree.h"
  3. #include <vector>
  4. #include <stdlib.h>
  5. #include <time.h>
  6. #include "Map.h"
  7. #include "Set.h"
  8.  
  9. int main()
  10. {
  11. 	delia::map<int, int> m;
  12. 	m.insert(make_pair(1, 1));
  13. 	m.insert(make_pair(3, 3));
  14. 	m.insert(make_pair(0, 0));
  15. 	m.insert(make_pair(9, 9));
  16.  
  17.  
  18. 	delia::set<int> s;
  19. 	s.insert(1);
  20. 	s.insert(5);
  21. 	s.insert(2);
  22. 	s.insert(1);
  23. 	s.insert(13);
  24. 	s.insert(0);
  25. 	s.insert(15);
  26. 	s.insert(18);
  27.  
  28.  
  29. 	delia::set<int>::iterator sit = s.begin();
  30. 	while (sit != s.end())
  31. 	{
  32. 		cout << *sit << " ";
  33. 		++sit;
  34. 	}
  35. 	cout << endl;
  36.  
  37.  
  38. 	return 0;
  39. }

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

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

  

闽ICP备14008679号