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

    目录

    一、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* _left;//节点的左孩子
    6. 	RBTreeNode* _right;//节点的右孩子
    7. 	RBTreeNode* _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. 	pairbool> 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 _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. 		RBTreeconst K, V>, MapKeyOfT> _t;
    24. 	};
    25. }

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

    （3）修改红黑树定义

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

    （4）修改红黑树插入

    1. 	//插入
    2. 	pairbool> Insert(const pair& 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 Node;
    5.  
    6. public:
    7. 	typedef __TreeIterator 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 Node;
    5. 	typedef __TreeIterator 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 Node;
    5.  
    6. public:
    7. 	typedef __TreeIterator 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::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. 		pairbool> 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 _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::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. 		pairbool> 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. 			pairbool> 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. 		RBTreeconst K, V>, MapKeyOfT> _t;
    53. 	};
    54. }

    六、红黑树完整代码段

    1. #pragma once
    2. #include
    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* _left;//节点的左孩子
    18. 	RBTreeNode* _right;//节点的右孩子
    19. 	RBTreeNode* _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 Node;
    38. 	typedef __TreeIterator 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 Node;
    144. public:
    145. 	typedef __TreeIterator 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. 	pairbool> 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 
    4. #include 
    5. #include 
    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. }

  • 相关阅读:
    【机器学习-周志华】学习笔记-第三章
    递归：快速排序，归并排序和堆排序
    每日一题 1993. 树上的操作
    Leetcode Daily Challenge 1845. Seat Reservation Manager
    浏览器“四巨头”首度合作 解决网页适配问题
    贝塞尔曲线的一些资料收集
    【C语言】sizeof操作符详解
    数字信号处理-10-并行FIR滤波器MATLAB与FPGA实现
    智慧公厕：探索未来公共厕所的创新设计
    17:00面试，17:04就出来了 ，问的实在是太...
  • 原文地址：https://blog.csdn.net/gx714433461/article/details/126721634