• ＜map与set的模拟实现＞——《C++高阶》

     目录

    <红黑树模拟实现STL中的map与set> 

    1.红黑树的迭代器

    2. 改造红黑树

    3.map的模拟实现

    附用红黑树：

    （1）map.h:

    （2）RBTree.h:

    （3）test.cpp:

    4.set的模拟实现

    附用红黑树：

    （1）set.h:

    （2）RBTree.h:

    后记：●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

    STL源码剖析 高清文字版 简体中文
    pdf 1星 超过10%的资源 3.32MB
    下载

    <红黑树模拟实现STL中的map与set> 

    GIF：

    1.红黑树的迭代器

    迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题： begin()与end()
    STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，
    可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位
    置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
    能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最
    后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：
    图片源于网络：（这里仅做学习用途，如有侵权，请联系删除！） 
    •  operator++()与operator--() 
      1. // 找迭代器的下一个节点，下一个节点肯定比其大
      2. void Increasement()
      3. {
      4. 	//分两种情况讨论:_pNode的右子树存在和不存在
      5. 	// 右子树存在
      6. 	if (_pNode->_pRight)
      7. 	{
      8. 		// 右子树中最小的节点，即右子树中最左侧节点
      9. 		_pNode = _pNode->_pRight;
      10. 		while (_pNode->_pLeft)
      11. 			_pNode = _pNode->_pLeft;
      12. 	}
      13. 	else
      14. 	{
      15. 		// 右子树不存在，向上查找，直到_pNode != pParent->right
      16. 		PNode pParent = _pNode->_pParent;
      17. 		while (pParent->_pRight == _pNode)
      18. 		{
      19. 			_pNode = pParent;
      20. 			pParent = _pNode->_pParent;
      21. 		}
      22. 		// 特殊情况：根节点没有右子树
      23. 		if (_pNode->_pRight != pParent)
      24. 			_pNode = pParent;
      25. 	}
      26. }
      27. // 获取迭代器指向节点的前一个节点
      28. void Decreasement()
      29. {
      30. 	//分三种情况讨论：_pNode 在head的位置，_pNode 左子树存在，_pNode 左子树不存在
      31. 		// 1. _pNode 在head的位置，--应该将_pNode放在红黑树中最大节点的位置
      32. 		if (_pNode->_pParent->_pParent == _pNode && _pNode->_color == RED)
      33. 			_pNode = _pNode->_pRight;
      34. 		else if (_pNode->_pLeft)
      35. 		{
      36. 			// 2. _pNode的左子树存在,在左子树中找最大的节点，即左子树中最右侧节点
      37. 			_pNode = _pNode->_pLeft;
      38. 			while (_pNode->_pRight)
      39. 				_pNode = _pNode->_pRight;
      40. 		}
      41. 		else
      42. 		{
      43. 			// _pNode的左子树不存在，只能向上找
      44. 			PNode pParent = _pNode->_pParent;
      45. 			while (_pNode == pParent->_pLeft)
      46. 			{
      47. 				_pNode = pParent;
      48. 				pParent = _pNode->_pParent;
      49. 			}
      50. 			_pNode = pParent;
      51. 		}
      52. }

    2. 改造红黑树

    1. // 因为关联式容器中存储的是的键值对，因此
    2. // k为key的类型，
    3. // ValueType: 如果是map，则为pair; 如果是set，则为k
    4. // KeyOfValue: 通过value来获取key的一个仿函数类
    5. template<class K, class ValueType, class KeyOfValue>
    6. class RBTree
    7. {
    8. 	typedef RBTreeNode Node;
    9. 	typedef Node* PNode;
    10. public:
    11. 	typedef RBTreeIterator Iterator;
    12. public:
    13. 	RBTree();
    14. 	~RBTree()
    15. 		/
    16. 		// Iterator
    17. 		Iterator Begin() { return Iterator(_pHead->_pLeft); }
    18. 	Iterator End() { return Iterator(_pHead); }
    19. 	//
    20. 	// Modify
    21. 	pairbool> Insert(const ValueType& data)
    22. 	{
    23. 		// 插入节点并进行调整
    24. 		// 参考上文...
    25. 		return make_pair(Iterator(pNewNode), true);
    26. 	}
    27. 	// 将红黑树中的节点清空
    28. 	void Clear();
    29. 	Iterator Find(const K& key);
    30. 	//
    31. 	// capacity
    32. 	size_t Size()const;
    33. 	bool Empty()const;
    34. 	// ……
    35. private:
    36. 	PNode _pHead;
    37. 	size_t _size;  // 红黑树中有效节点的个数
    38. };

    3.map的模拟实现

    map的底层结构就是红黑树，因此在map中直接封装一棵红黑树，然后将其接口包装下即可 
    1. namespace bite
    2. {
    3. 	template<class K, class V>
    4. 	class map
    5. 	{
    6. 		typedef pair ValueType;
    7. 		// 作用：将value中的key提取出来
    8. 		struct KeyOfValue
    9. 		{
    10. 			const K& operator()(const ValueType& v)
    11. 			{
    12. 				return v.first;
    13. 			}
    14. 		};
    15. 		typedef RBTree RBTree;
    16. 	public:
    17. 		typedef typename RBTree::Iterator iterator;
    18. 	public:
    19. 		map() {}
    20. 		/
    21. 		// Iterator
    22. 		iterator begin() { return _t.Begin(); }
    23. 		iterator end() { return _t.End(); }
    24. 		/
    25. 		// Capacity
    26. 		size_t size()const { return _t.Size(); }
    27. 		bool empty()const { return _t.Empty(); }
    28. 		/
    29.         // Acess
    30. 		V& operator[](const K& key)
    31. 		{
    32. 			return (*(_t.Insert(ValueType(key, V()))).first).second;
    33. 		}
    34. 		const V& operator[](const K& key)const;
    35. 		
    36. 		// modify
    37. 		pairbool> insert(const ValueType& data)
    38. 		{
    39. 			return _t.Insert(data);
    40. 		}
    41. 		void clear() { _t.Clear(); }
    42. 		iterator find(const K& key) { return _t.Find(key); }
    43. 	private:
    44. 		RBTree _t;
    45. 	};
    46. }

    附用红黑树：

    （1）map.h:

    1. #pragma once
    2. #include"RBTree.h"
    3.  
    4. namespace my
    5. {
    6. 	template<class K, class V>
    7. 	class map
    8. 	{
    9. 		struct MapKeyOfT
    10. 		{
    11. 			const K& operator()(const pair& kv)
    12. 			{
    13. 				return kv.first;
    14. 			}
    15. 		};
    16. 	public:
    17. 		typedef typename RBTree, MapKeyOfT>::iterator iterator;
    18. 		typedef typename RBTree, MapKeyOfT>::const_iterator const_iterator;
    19.  
    20. 		iterator begin()
    21. 		{
    22. 			return _t.Begin();
    23. 		}
    24.  
    25. 		iterator end()
    26. 		{
    27. 			return _t.End();
    28. 		}
    29.  
    30. 		pairbool> insert(const pair& kv)
    31. 		{
    32. 			return _t.Insert(kv);
    33. 		}
    34.  
    35. 		iterator find(const K& key)
    36. 		{
    37. 			return _t.Find(key);
    38. 		}
    39.  
    40. 		V& operator[](const K& key)
    41. 		{
    42. 			pairbool> ret = insert(make_pair(key, V()));
    43. 			return ret.first->second;
    44. 		}
    45.  
    46. 	private:
    47. 		RBTree, MapKeyOfT> _t;
    48. 	};
    49.  
    50. 	void test_map1()
    51. 	{
    52. 		mapint> m;
    53. 		m.insert(make_pair("111", 1));
    54. 		m.insert(make_pair("555", 5));
    55. 		m.insert(make_pair("333", 3));
    56. 		m.insert(make_pair("222", 2));
    57. 		//迭代器遍历
    58. 		mapint>::iterator it = m.begin();
    59. 		while (it != m.end())
    60. 		{
    61. 			cout << it->first << ":" << it->second << endl;
    62. 			++it;
    63. 		}
    64. 		cout << endl;
    65. 		//范围for遍历
    66. 		for (auto& kv : m)
    67. 		{
    68. 			cout << kv.first << ":" << kv.second << endl;
    69. 		}
    70. 		cout << endl;
    71. 	}
    72.  
    73. 	void test_map2()
    74. 	{
    75. 		string arr[] = { "ƻ", "", "ƻ", "", "ƻ", "ƻ", "", "ƻ", "㽶", "ƻ", "㽶" };
    76. 		//迭代器遍历
    77. 		mapint> countMap;
    78. 		for (auto& str : arr)
    79. 		{
    80. 			countMap[str]++;
    81. 		}
    82. 		//范围for遍历
    83. 		for (const auto& kv : countMap)
    84. 		{
    85. 			cout << kv.first << ":" << kv.second << endl;
    86. 		}
    87. 	} 
    88.  
    89. 	void test_map3()
    90. 	{
    91. 		map dict;
    92. 		dict["insert"];
    93. 		dict["insert"] = "";
    94. 		dict["left"] = "";
    95.  
    96. 	}
    97. }

    （2）RBTree.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. enum Colour
    9. {
    10. 	RED,
    11. 	BLACK,
    12. };
    13.    
    14. template<class T>
    15. struct RBTreeNode
    16. {
    17. 	RBTreeNode* _left;
    18. 	RBTreeNode* _right;
    19. 	RBTreeNode* _parent;
    20. 	T _data;    
    21.  
    22. 	Colour _col;
    23.  
    24. 	RBTreeNode(const T& data)
    25. 		:_data(data)
    26. 		, _left(nullptr)
    27. 		, _right(nullptr)
    28. 		, _parent(nullptr)
    29. 		, _col(RED)
    30. 	{}
    31. };
    32.  
    33. //T决定红黑树存什么数据
    34. //set   RBTree
    35. //map   RBTree>
    36. //KeyOfT -> 支持取出T对象中key的仿函数
    37. template<class T, class Ref, class Ptr>
    38. struct __RBTreeIterator
    39. {
    40. 	typedef RBTreeNode Node;
    41. 	typedef __RBTreeIterator Self;
    42. 	Node* _node;
    43.  
    44. 	__RBTreeIterator(Node* node)
    45. 		:_node(node)
    46. 	{}
    47. 	//运算符*重载
    48. 	Ref operator*()
    49. 	{
    50. 		return _node->_data;
    51. 	}
    52. 	//运算符->重载
    53. 	Ptr operator->()
    54. 	{
    55. 		return &_node->_data;
    56. 	}
    57. 	//重载 前置++
    58. 	Self& operator++()
    59. 	{
    60. 		if (_node->_right == nullptr)
    61. 		{
    62. 			// 找祖先里面，孩子是父亲左的那个
    63. 			Node* cur = _node;
    64. 			Node* parent = cur->_parent;
    65. 			while (parent && parent->_right == cur)
    66. 			{
    67. 				cur = cur->_parent;
    68. 				parent = parent->_parent;
    69. 			}
    70.  
    71. 			_node = parent;
    72. 		}
    73. 		else
    74. 		{
    75. 			// 右子树的最左节点
    76. 			Node* subLeft = _node->_right;
    77. 			while (subLeft->_left)
    78. 			{
    79. 				subLeft = subLeft->_left;
    80. 			}
    81. 			_node = subLeft;
    82. 		}
    83. 		return *this;
    84. 	}
    85. 	//重载 后置++
    86. 	Self operator++(int)
    87. 	{
    88. 		Self tmp(*this);
    89.  
    90. 		++(*this);
    91.  
    92. 		return tmp;
    93. 	}
    94. 	//重载 前置--
    95. 	Self& operator--()
    96. 	{
    97. 		if (_node->_left == nullptr)
    98. 		{
    99. 			// 找祖先里面，孩子是父亲
    100. 			Node* cur = _node;
    101. 			Node* parent = cur->_parent;
    102. 			while (parent && cur == parent->_left)
    103. 			{
    104. 				cur = cur->_parent;
    105. 				parent = parent->_parent;
    106. 			}
    107. 			_node = parent;
    108. 		}
    109. 		else
    110. 		{
    111. 			// 左子树的最右节点
    112. 			Node* subRight = _node->_left;
    113. 			while (subRight->_right)
    114. 			{
    115. 				subRight = subRight->_right;
    116. 			}
    117.  
    118. 			_node = subRight;
    119. 		}
    120. 		return *this;
    121. 	}
    122. 	//重载 后置--
    123. 	Self operator--(int)
    124. 	{
    125. 		Self tmp(*this);
    126.  
    127. 		--(*this);
    128.  
    129. 		return tmp;
    130. 	}
    131. 	//重载 ！=
    132. 	bool operator!=(const Self& s) const
    133. 	{
    134. 		return _node != s._node;
    135. 	}
    136. 	//重载 ==
    137. 	bool operator==(const Self& s) const
    138. 	{
    139. 		return _node == s->_node;
    140. 	}
    141.  
    142. };
    143.  
    144. template<class K, class T, class KeyOfT>
    145. class RBTree
    146. {
    147. 	typedef RBTreeNode Node;   //默认为私有
    148. public:
    149. 	typedef __RBTreeIterator iterator;
    150. 	typedef __RBTreeIteratorconst T&, const T*> const_iterator;
    151.  
    152. 	// 构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的
    153.  
    154. 	iterator Begin()
    155. 	{
    156. 		Node* subLeft = _root;
    157. 		while (subLeft && subLeft->_left)
    158. 		{
    159. 			subLeft = subLeft->_left;
    160. 		}
    161.  
    162. 		return iterator(subLeft);
    163. 	}
    164.  
    165. 	iterator End() 
    166. 	{
    167. 		return iterator(nullptr);
    168. 	}
    169.  
    170. 	const_iterator Begin() const
    171. 	{
    172. 		Node* subLeft = _root;
    173. 		while (subLeft && subLeft->_left)
    174. 		{
    175. 			subLeft = subLeft->_left;
    176. 		}
    177.  
    178. 		return const_iterator(subLeft);
    179. 	}
    180.  
    181. 	const_iterator End() const
    182. 	{
    183. 		return const_iterator(nullptr);
    184. 	}
    185. 	//insert数据
    186. 	pairbool> Insert(const T& data)
    187. 	{
    188. 		// 1、搜索树的规则插入
    189. 		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
    190. 		if (_root == nullptr)
    191. 		{
    192. 			_root = new Node(data);
    193. 			_root->_col = BLACK;
    194. 			return make_pair(iterator(_root), true);
    195. 		}
    196. 		KeyOfT kot;
    197. 		Node* parent = nullptr;
    198. 		Node* cur = _root;
    199. 		while (cur)
    200. 		{
    201. 			if (kot(cur->_data) < kot(data))
    202. 			{
    203. 				parent = cur;
    204. 				cur = cur->_right;
    205. 			}
    206. 			else if (kot(cur->_data) > kot(data))
    207. 			{
    208. 				parent = cur;
    209. 				cur = cur->_left;
    210. 			}
    211. 			else
    212. 			{
    213. 				return make_pair(iterator(cur), true);
    214. 			}
    215. 		}
    216. 		cur = new Node(data);
    217. 		Node* newnode = cur;
    218. 		cur->_col = RED;
    219. 		if (kot(parent->_data) < kot(data))
    220. 		{
    221. 			parent->_right = cur;
    222. 		}
    223. 		else
    224. 		{
    225. 			parent->_left = cur;
    226. 		}
    227.  
    228. 		cur->_parent = parent;
    229. 		// 存在连续红色节点
    230. 		while (parent && parent->_col == RED)
    231. 		{
    232. 			Node* grandfater = parent->_parent;
    233. 			assert(grandfater);
    234.  
    235. 			if (grandfater->_left == parent)
    236. 			{
    237. 				Node* uncle = grandfater->_right;
    238. 				// 情况一：
    239. 				if (uncle && uncle->_col == RED) // 叔叔存在且为红
    240. 				{
    241. 					// 变色
    242. 					parent->_col = uncle->_col = BLACK;
    243. 					grandfater->_col = RED;
    244.  
    245. 					// 继续往上处理
    246. 					cur = grandfater;
    247. 					parent = cur->_parent;
    248. 				}
    249. 				else // 叔叔不存在 或者 叔叔存在且为黑
    250. 				{
    251. 					if (cur == parent->_left) // 单旋
    252. 					{
    253. 						//     g
    254. 						//   p
    255. 						// c
    256. 						RotateR(grandfater);
    257. 						parent->_col = BLACK;
    258. 						grandfater->_col = RED;
    259. 					}
    260. 					else // 双旋
    261. 					{
    262. 						//     g
    263. 						//   p
    264. 						//     c 
    265. 						RotateL(parent);
    266. 						RotateR(grandfater);
    267. 						cur->_col = BLACK;
    268. 						grandfater->_col = RED;
    269. 					}
    270.  
    271. 					break;
    272. 				}
    273. 			}
    274. 			else //(grandfater->_right == parent)
    275. 			{
    276. 				Node* uncle = grandfater->_left;
    277. 				// 情况一：
    278. 				if (uncle && uncle->_col == RED)
    279. 				{
    280. 					// 变色
    281. 					parent->_col = uncle->_col = BLACK;
    282. 					grandfater->_col = RED;
    283.  
    284. 					// 继续往上处理
    285. 					cur = grandfater;
    286. 					parent = cur->_parent;
    287. 				}
    288. 				else
    289. 				{
    290. 					if (cur == parent->_right)
    291. 					{
    292. 						// g
    293. 						//   p
    294. 						//     c 
    295. 						RotateL(grandfater);
    296. 						parent->_col = BLACK;
    297. 						grandfater->_col = RED;
    298. 					}
    299. 					else // 双旋
    300. 					{
    301. 						// g
    302. 						//   p
    303. 						// c
    304. 						RotateR(parent);
    305. 						RotateL(grandfater);
    306. 						cur->_col = BLACK;
    307. 						grandfater->_col = RED;
    308. 					}
    309.  
    310. 					break;
    311. 				}
    312. 			}
    313. 		}
    314. 		_root->_col = BLACK;
    315. 		return make_pair(iterator(newnode), true);
    316. 	}
    317. 	
    318. 	//左旋
    319. 	void RotateL(Node* parent)
    320. 	{
    321. 		Node* subR = parent->_right;
    322. 		Node* subRL = subR->_left;
    323.  
    324. 		parent->_right = subRL;
    325. 		if (subRL)
    326. 			subRL->_parent = parent;
    327.  
    328. 		Node* ppNode = parent->_parent;
    329.  
    330. 		subR->_left = parent;
    331. 		parent->_parent = subR;
    332.  
    333. 		if (parent == _root)
    334. 		{
    335. 			_root = subR;
    336. 			_root->_parent = nullptr;
    337. 		}
    338. 		else
    339. 		{
    340. 			if (parent == ppNode->_left)
    341. 			{
    342. 				ppNode->_left = subR;
    343. 			}
    344. 			else
    345. 			{
    346. 				ppNode->_right = subR;
    347. 			}
    348.  
    349. 			subR->_parent = ppNode;
    350. 		}
    351. 	}
    352. 	//右旋
    353. 	void RotateR(Node* parent)
    354. 	{
    355. 		Node* subL = parent->_left;
    356. 		Node* subLR = subL->_right;
    357.  
    358. 		parent->_left = subLR;
    359. 		if (subLR)
    360. 			subLR->_parent = parent;
    361.  
    362. 		Node* ppNode = parent->_parent;
    363.  
    364. 		subL->_right = parent;
    365. 		parent->_parent = subL;
    366.  
    367. 		if (parent == _root)
    368. 		{
    369. 			_root = subL;
    370. 			_root->_parent = nullptr;
    371. 		}
    372. 		else
    373. 		{
    374. 			if (ppNode->_left == parent)
    375. 			{
    376. 				ppNode->_left = subL;
    377. 			}
    378. 			else
    379. 			{
    380. 				ppNode->_right = subL;
    381. 			}
    382. 			subL->_parent = ppNode;
    383. 		}
    384.  
    385. 	}
    386.  
    387. 	iterator Find(const K& key)
    388. 	{
    389. 		Node* cur = _root;
    390. 		KeyOfT kot;
    391. 		while (cur)
    392. 		{
    393. 			if (kot(cur->_data) < key)
    394. 			{
    395. 				cur = cur->_right;
    396. 			}
    397. 			else if (kot(cur->_data) > key)
    398. 			{
    399. 				cur = cur->_left;
    400. 			}
    401. 			else
    402. 			{
    403. 				return iterator(cur);
    404. 			}
    405. 		}
    406.  
    407. 		return End();
    408. 	}
    409.  
    410. private:
    411. 	Node* _root = nullptr;
    412. };
    413.  
    414. 层序遍历
    415. //vector> levelOrder()
    416. //{
    417. //	cout << "层序遍历：" << endl;
    418. //	vector> vv;
    419. //	if (_root == nullptr)
    420. //		return vv;
    421. //
    422. //	queue q;
    423. //	int levelSize = 1;
    424. //	q.push(_root);
    425. //
    426. //	while (!q.empty())
    427. //	{
    428. //
    429. //		// levelSize控制一层一层出
    430. //		vector levelV;
    431. //		while (levelSize--)
    432. //		{
    433. //			Node* front = q.front();
    434. //			q.pop();
    435. //			levelV.push_back(front->_kv.first);
    436. //			if (front->_left)
    437. //				q.push(front->_left);
    438. //
    439. //			if (front->_right)
    440. //				q.push(front->_right);
    441. //		}
    442. //		vv.push_back(levelV);
    443. //		for (auto e : levelV)
    444. //		{
    445. //			cout << e << " ";
    446. //		}
    447. //		cout << endl;
    448. //
    449. //		// 上一层出完，下一层就都进队列
    450. //		levelSize = q.size();
    451. //	}
    452. //
    453. //	return vv;
    454. //}
    455. //
    456. //
    457. 求最长路径
    458. //int _maxHeight(Node* root)
    459. //{
    460. //	if (root == nullptr)
    461. //		return 0;
    462. //
    463. //	int lh = _maxHeight(root->_left);
    464. //	int rh = _maxHeight(root->_right);
    465. //
    466. //	return lh > rh ? lh + 1 : rh + 1;
    467. //}
    468. 求最短路径
    469. //int _minHeight(Node* root)
    470. //{
    471. //	if (root == nullptr)
    472. //		return 0;
    473. //
    474. //	int lh = _minHeight(root->_left);
    475. //	int rh = _minHeight(root->_right);
    476. //
    477. //	return lh < rh ? lh + 1 : rh + 1;
    478. //}
    479. 1.中序遍历（递归版）
    480. //void _InOrder(Node* root)
    481. //{
    482. //	if (root == nullptr)
    483. //		return;
    484. //
    485. //	_InOrder(root->_left);
    486. //	cout << root->_kv.first << " ";
    487. //	_InOrder(root->_right);
    488. //}
    489. 2.前序遍历（递归版）
    490. //void _PrevOrder(Node* root)
    491. //{
    492. //	if (root == nullptr)
    493. //		return;
    494. //
    495. //	cout << root->_kv.first << " ";
    496. //	_PrevOrder(root->_left);
    497. //	_PrevOrder(root->_right);
    498. //}
    499. 3.后序遍历（递归版）
    500. //void _PostOrder(Node* root)
    501. //{
    502. //	if (root == nullptr)
    503. //		return;
    504. //
    505. //	_PostOrder(root->_left);
    506. //	_PostOrder(root->_right);
    507. //	cout << root->_kv.first << " ";
    508. //}
    509. 判断是否为有效红黑树
    510. //bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
    511. //{
    512. //	//走到null之后，判断k和black是否相等
    513. //	if (nullptr == pRoot)
    514. //	{
    515. //		if (k != blackCount)
    516. //		{
    517. //			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
    518. //			return false;
    519. //		}
    520. //		return true;
    521. //	}
    522. //
    523. //	// 统计黑色节点的个数
    524. //	if (BLACK == pRoot->_col)
    525. //		k++;
    526. //
    527. //	// 检测当前节点与其双亲是否都为红色
    528. //	if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
    529. //	{
    530. //		cout << "违反性质三：存在连在一起的红色节点" << endl;
    531. //		return false;
    532. //	}
    533. //
    534. //	return _IsValidRBTree(pRoot->_left, k, blackCount) &&
    535. //		_IsValidRBTree(pRoot->_right, k, blackCount);
    536. //}
    537. //
    538. //public:
    539. //	//遍历
    540. //	void InOrder()
    541. //	{
    542. //		cout << "中序遍历：";
    543. //		_InOrder(_root);
    544. //		cout << endl;
    545. //	}
    546. //	void PrevOrder()
    547. //	{
    548. //		cout << "前序遍历：";
    549. //		_PrevOrder(_root);
    550. //		cout << endl;
    551. //	}
    552. //	void PostOrder()
    553. //	{
    554. //		cout << "后序遍历：";
    555. //		_PostOrder(_root);
    556. //		cout << endl;
    557. //	}
    558. //
    559. //	void Height()
    560. //	{
    561. //		cout << "最长路径:" << _maxHeight(_root) << endl;
    562. //		cout << "最短路径:" << _minHeight(_root) << endl;
    563. //	}
    564. //
    565. //	bool IsBalanceTree()
    566. //	{
    567. //		// 检查红黑树几条规则
    568. //
    569. //		Node* pRoot = _root;
    570. //		// 空树也是红黑树
    571. //		if (nullptr == pRoot)
    572. //			return true;
    573. //
    574. //		// 检测根节点是否满足情况
    575. //		if (BLACK != pRoot->_col)
    576. //		{
    577. //			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
    578. //			return false;
    579. //		}
    580. //
    581. //		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
    582. //		size_t blackCount = 0;
    583. //		Node* pCur = pRoot;
    584. //		while (pCur)
    585. //		{
    586. //			if (BLACK == pCur->_col)
    587. //				blackCount++;
    588. //
    589. //			pCur = pCur->_left;
    590. //		}
    591. //
    592. //		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    593. //		size_t k = 0;
    594. //		return _IsValidRBTree(pRoot, k, blackCount);
    595. //	}

    （3）test.cpp:

    1. #include"map.h"
    2.  
    3. int main()
    4. {
    5. 	//my::test_map1();
    6. 	my::test_map2();
    7. 	//my::test_map3();
    8.  
    9. 	return 0;
    10. }

    4.set的模拟实现

    set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来(具体实现可参 考map)。 
    1. namespace bite
    2. {
    3. 	template<class K>
    4. 	class set
    5. 	{
    6. 		typedef K ValueType;
    7. 		// 作用是：将value中的key提取出来
    8. 		struct KeyOfValue
    9. 		{
    10. 			const K& operator()(const ValueType& key)
    11. 			{
    12. 				return key;
    13. 			}
    14. 		};
    15. 		// 红黑树类型重命名
    16. 		typedef RBTree RBTree;
    17. 	public:
    18. 		typedef typename RBTree::Iterator iterator;
    19. 	public:
    20. 		Set() {}
    21. 		/
    22. 		// Iterator
    23. 		iterator Begin();
    24. 		iterator End();
    25. 		/
    26. 		// Capacity
    27. 		size_t size()const;
    28. 		bool empty()const;
    29. 		
    30. 		// modify
    31. 		pairbool> insert(const ValueType& data)
    32. 		{
    33. 			return _t.Insert(data);
    34. 		}
    35. 		void clear();
    36. 		iterator find(const K& key); 
    37. 	private:
    38. 			RBTree _t;
    39. 	};
    40. }

    附用红黑树：

    （1）set.h:

    1. #pragma once
    2. #include "RBTree.h"
    3.  
    4. namespace my
    5. {
    6. 	template<class K>
    7. 	class set
    8. 	{
    9. 		struct SetKeyOfT
    10. 		{
    11. 			const K& operator()(const K& key)
    12. 			{
    13. 				return key;
    14. 			}
    15. 		};
    16. 	public:
    17. 		typedef typename RBTree::const_iterator iterator;
    18. 		typedef typename RBTree::const_iterator const_iterator;
    19.  
    20. 		iterator begin() const
    21. 		{
    22. 			return _t.Begin();
    23. 		}
    24.  
    25. 		iterator end() const
    26. 		{
    27. 			return _t.End();
    28. 		}
    29.  
    30. 		pairbool> insert(const K& key)
    31. 		{
    32. 			//pair::iterator, bool> ret = _t.Insert(key);
    33. 			auto ret = _t.Insert(key);
    34. 			return pairbool>(iterator(ret.first._node), ret.second);
    35. 		}
    36.  
    37. 		iterator find(const K& key)
    38. 		{
    39. 			return _t.Find(key);
    40. 		}
    41. 	private:
    42. 		RBTree _t;
    43. 	};
    44.  
    45. 	void test_set1()
    46. 	{
    47. 		set<int> s;
    48. 		s.insert(8);
    49. 		s.insert(6);
    50. 		s.insert(11);
    51. 		s.insert(5);
    52. 		s.insert(6);
    53. 		s.insert(7);
    54. 		s.insert(10);
    55. 		s.insert(13);
    56. 		s.insert(12);
    57. 		s.insert(15);
    58. 		//迭代器遍历
    59. 		set<int>::iterator it = s.begin();
    60. 		while (it != s.end())
    61. 		{
    62. 			cout << *it << " ";
    63. 			++it;
    64. 		}
    65. 		cout << endl;
    66. 		//范围for遍历
    67. 		for (auto e : s)
    68. 		{
    69. 			cout << e << " ";
    70. 		}
    71. 		cout << endl;
    72. 	}
    73. }

    （2）RBTree.h:

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. enum Colour
    9. {
    10. 	RED,
    11. 	BLACK,
    12. };
    13.    
    14. template<class T>
    15. struct RBTreeNode
    16. {
    17. 	RBTreeNode* _left;
    18. 	RBTreeNode* _right;
    19. 	RBTreeNode* _parent;
    20. 	T _data;    
    21.  
    22. 	Colour _col;
    23.  
    24. 	RBTreeNode(const T& data)
    25. 		:_data(data)
    26. 		, _left(nullptr)
    27. 		, _right(nullptr)
    28. 		, _parent(nullptr)
    29. 		, _col(RED)
    30. 	{}
    31. };
    32.  
    33. //T决定红黑树存什么数据
    34. //set   RBTree
    35. //map   RBTree>
    36. //KeyOfT -> 支持取出T对象中key的仿函数
    37. template<class T, class Ref, class Ptr>
    38. struct __RBTreeIterator
    39. {
    40. 	typedef RBTreeNode Node;
    41. 	typedef __RBTreeIterator Self;
    42. 	Node* _node;
    43.  
    44. 	__RBTreeIterator(Node* node)
    45. 		:_node(node)
    46. 	{}
    47. 	//运算符*重载
    48. 	Ref operator*()
    49. 	{
    50. 		return _node->_data;
    51. 	}
    52. 	//运算符->重载
    53. 	Ptr operator->()
    54. 	{
    55. 		return &_node->_data;
    56. 	}
    57. 	//重载 前置++
    58. 	Self& operator++()
    59. 	{
    60. 		if (_node->_right == nullptr)
    61. 		{
    62. 			// 找祖先里面，孩子是父亲左的那个
    63. 			Node* cur = _node;
    64. 			Node* parent = cur->_parent;
    65. 			while (parent && parent->_right == cur)
    66. 			{
    67. 				cur = cur->_parent;
    68. 				parent = parent->_parent;
    69. 			}
    70.  
    71. 			_node = parent;
    72. 		}
    73. 		else
    74. 		{
    75. 			// 右子树的最左节点
    76. 			Node* subLeft = _node->_right;
    77. 			while (subLeft->_left)
    78. 			{
    79. 				subLeft = subLeft->_left;
    80. 			}
    81. 			_node = subLeft;
    82. 		}
    83. 		return *this;
    84. 	}
    85. 	//重载 后置++
    86. 	Self operator++(int)
    87. 	{
    88. 		Self tmp(*this);
    89.  
    90. 		++(*this);
    91.  
    92. 		return tmp;
    93. 	}
    94. 	//重载 前置--
    95. 	Self& operator--()
    96. 	{
    97. 		if (_node->_left == nullptr)
    98. 		{
    99. 			// 找祖先里面，孩子是父亲
    100. 			Node* cur = _node;
    101. 			Node* parent = cur->_parent;
    102. 			while (parent && cur == parent->_left)
    103. 			{
    104. 				cur = cur->_parent;
    105. 				parent = parent->_parent;
    106. 			}
    107. 			_node = parent;
    108. 		}
    109. 		else
    110. 		{
    111. 			// 左子树的最右节点
    112. 			Node* subRight = _node->_left;
    113. 			while (subRight->_right)
    114. 			{
    115. 				subRight = subRight->_right;
    116. 			}
    117.  
    118. 			_node = subRight;
    119. 		}
    120. 		return *this;
    121. 	}
    122. 	//重载 后置--
    123. 	Self operator--(int)
    124. 	{
    125. 		Self tmp(*this);
    126.  
    127. 		--(*this);
    128.  
    129. 		return tmp;
    130. 	}
    131. 	//重载 ！=
    132. 	bool operator!=(const Self& s) const
    133. 	{
    134. 		return _node != s._node;
    135. 	}
    136. 	//重载 ==
    137. 	bool operator==(const Self& s) const
    138. 	{
    139. 		return _node == s->_node;
    140. 	}
    141.  
    142. };
    143.  
    144. template<class K, class T, class KeyOfT>
    145. class RBTree
    146. {
    147. 	typedef RBTreeNode Node;   //默认为私有
    148. public:
    149. 	typedef __RBTreeIterator iterator;
    150. 	typedef __RBTreeIteratorconst T&, const T*> const_iterator;
    151.  
    152. 	// 构造 拷贝构造 赋值 和析构 跟搜索树实现方式是一样的
    153.  
    154. 	iterator Begin()
    155. 	{
    156. 		Node* subLeft = _root;
    157. 		while (subLeft && subLeft->_left)
    158. 		{
    159. 			subLeft = subLeft->_left;
    160. 		}
    161.  
    162. 		return iterator(subLeft);
    163. 	}
    164.  
    165. 	iterator End() 
    166. 	{
    167. 		return iterator(nullptr);
    168. 	}
    169.  
    170. 	const_iterator Begin() const
    171. 	{
    172. 		Node* subLeft = _root;
    173. 		while (subLeft && subLeft->_left)
    174. 		{
    175. 			subLeft = subLeft->_left;
    176. 		}
    177.  
    178. 		return const_iterator(subLeft);
    179. 	}
    180.  
    181. 	const_iterator End() const
    182. 	{
    183. 		return const_iterator(nullptr);
    184. 	}
    185. 	//insert数据
    186. 	pairbool> Insert(const T& data)
    187. 	{
    188. 		// 1、搜索树的规则插入
    189. 		// 2、看是否违反平衡规则，如果违反就需要处理：旋转
    190. 		if (_root == nullptr)
    191. 		{
    192. 			_root = new Node(data);
    193. 			_root->_col = BLACK;
    194. 			return make_pair(iterator(_root), true);
    195. 		}
    196. 		KeyOfT kot;
    197. 		Node* parent = nullptr;
    198. 		Node* cur = _root;
    199. 		while (cur)
    200. 		{
    201. 			if (kot(cur->_data) < kot(data))
    202. 			{
    203. 				parent = cur;
    204. 				cur = cur->_right;
    205. 			}
    206. 			else if (kot(cur->_data) > kot(data))
    207. 			{
    208. 				parent = cur;
    209. 				cur = cur->_left;
    210. 			}
    211. 			else
    212. 			{
    213. 				return make_pair(iterator(cur), true);
    214. 			}
    215. 		}
    216. 		cur = new Node(data);
    217. 		Node* newnode = cur;
    218. 		cur->_col = RED;
    219. 		if (kot(parent->_data) < kot(data))
    220. 		{
    221. 			parent->_right = cur;
    222. 		}
    223. 		else
    224. 		{
    225. 			parent->_left = cur;
    226. 		}
    227.  
    228. 		cur->_parent = parent;
    229. 		// 存在连续红色节点
    230. 		while (parent && parent->_col == RED)
    231. 		{
    232. 			Node* grandfater = parent->_parent;
    233. 			assert(grandfater);
    234.  
    235. 			if (grandfater->_left == parent)
    236. 			{
    237. 				Node* uncle = grandfater->_right;
    238. 				// 情况一：
    239. 				if (uncle && uncle->_col == RED) // 叔叔存在且为红
    240. 				{
    241. 					// 变色
    242. 					parent->_col = uncle->_col = BLACK;
    243. 					grandfater->_col = RED;
    244.  
    245. 					// 继续往上处理
    246. 					cur = grandfater;
    247. 					parent = cur->_parent;
    248. 				}
    249. 				else // 叔叔不存在 或者 叔叔存在且为黑
    250. 				{
    251. 					if (cur == parent->_left) // 单旋
    252. 					{
    253. 						//     g
    254. 						//   p
    255. 						// c
    256. 						RotateR(grandfater);
    257. 						parent->_col = BLACK;
    258. 						grandfater->_col = RED;
    259. 					}
    260. 					else // 双旋
    261. 					{
    262. 						//     g
    263. 						//   p
    264. 						//     c 
    265. 						RotateL(parent);
    266. 						RotateR(grandfater);
    267. 						cur->_col = BLACK;
    268. 						grandfater->_col = RED;
    269. 					}
    270.  
    271. 					break;
    272. 				}
    273. 			}
    274. 			else //(grandfater->_right == parent)
    275. 			{
    276. 				Node* uncle = grandfater->_left;
    277. 				// 情况一：
    278. 				if (uncle && uncle->_col == RED)
    279. 				{
    280. 					// 变色
    281. 					parent->_col = uncle->_col = BLACK;
    282. 					grandfater->_col = RED;
    283.  
    284. 					// 继续往上处理
    285. 					cur = grandfater;
    286. 					parent = cur->_parent;
    287. 				}
    288. 				else
    289. 				{
    290. 					if (cur == parent->_right)
    291. 					{
    292. 						// g
    293. 						//   p
    294. 						//     c 
    295. 						RotateL(grandfater);
    296. 						parent->_col = BLACK;
    297. 						grandfater->_col = RED;
    298. 					}
    299. 					else // 双旋
    300. 					{
    301. 						// g
    302. 						//   p
    303. 						// c
    304. 						RotateR(parent);
    305. 						RotateL(grandfater);
    306. 						cur->_col = BLACK;
    307. 						grandfater->_col = RED;
    308. 					}
    309.  
    310. 					break;
    311. 				}
    312. 			}
    313. 		}
    314. 		_root->_col = BLACK;
    315. 		return make_pair(iterator(newnode), true);
    316. 	}
    317. 	
    318. 	//左旋
    319. 	void RotateL(Node* parent)
    320. 	{
    321. 		Node* subR = parent->_right;
    322. 		Node* subRL = subR->_left;
    323.  
    324. 		parent->_right = subRL;
    325. 		if (subRL)
    326. 			subRL->_parent = parent;
    327.  
    328. 		Node* ppNode = parent->_parent;
    329.  
    330. 		subR->_left = parent;
    331. 		parent->_parent = subR;
    332.  
    333. 		if (parent == _root)
    334. 		{
    335. 			_root = subR;
    336. 			_root->_parent = nullptr;
    337. 		}
    338. 		else
    339. 		{
    340. 			if (parent == ppNode->_left)
    341. 			{
    342. 				ppNode->_left = subR;
    343. 			}
    344. 			else
    345. 			{
    346. 				ppNode->_right = subR;
    347. 			}
    348.  
    349. 			subR->_parent = ppNode;
    350. 		}
    351. 	}
    352. 	//右旋
    353. 	void RotateR(Node* parent)
    354. 	{
    355. 		Node* subL = parent->_left;
    356. 		Node* subLR = subL->_right;
    357.  
    358. 		parent->_left = subLR;
    359. 		if (subLR)
    360. 			subLR->_parent = parent;
    361.  
    362. 		Node* ppNode = parent->_parent;
    363.  
    364. 		subL->_right = parent;
    365. 		parent->_parent = subL;
    366.  
    367. 		if (parent == _root)
    368. 		{
    369. 			_root = subL;
    370. 			_root->_parent = nullptr;
    371. 		}
    372. 		else
    373. 		{
    374. 			if (ppNode->_left == parent)
    375. 			{
    376. 				ppNode->_left = subL;
    377. 			}
    378. 			else
    379. 			{
    380. 				ppNode->_right = subL;
    381. 			}
    382. 			subL->_parent = ppNode;
    383. 		}
    384.  
    385. 	}
    386.  
    387. 	iterator Find(const K& key)
    388. 	{
    389. 		Node* cur = _root;
    390. 		KeyOfT kot;
    391. 		while (cur)
    392. 		{
    393. 			if (kot(cur->_data) < key)
    394. 			{
    395. 				cur = cur->_right;
    396. 			}
    397. 			else if (kot(cur->_data) > key)
    398. 			{
    399. 				cur = cur->_left;
    400. 			}
    401. 			else
    402. 			{
    403. 				return iterator(cur);
    404. 			}
    405. 		}
    406.  
    407. 		return End();
    408. 	}
    409.  
    410. private:
    411. 	Node* _root = nullptr;
    412. };
    413.  
    414. 层序遍历
    415. //vector> levelOrder()
    416. //{
    417. //	cout << "层序遍历：" << endl;
    418. //	vector> vv;
    419. //	if (_root == nullptr)
    420. //		return vv;
    421. //
    422. //	queue q;
    423. //	int levelSize = 1;
    424. //	q.push(_root);
    425. //
    426. //	while (!q.empty())
    427. //	{
    428. //
    429. //		// levelSize控制一层一层出
    430. //		vector levelV;
    431. //		while (levelSize--)
    432. //		{
    433. //			Node* front = q.front();
    434. //			q.pop();
    435. //			levelV.push_back(front->_kv.first);
    436. //			if (front->_left)
    437. //				q.push(front->_left);
    438. //
    439. //			if (front->_right)
    440. //				q.push(front->_right);
    441. //		}
    442. //		vv.push_back(levelV);
    443. //		for (auto e : levelV)
    444. //		{
    445. //			cout << e << " ";
    446. //		}
    447. //		cout << endl;
    448. //
    449. //		// 上一层出完，下一层就都进队列
    450. //		levelSize = q.size();
    451. //	}
    452. //
    453. //	return vv;
    454. //}
    455. //
    456. //
    457. 求最长路径
    458. //int _maxHeight(Node* root)
    459. //{
    460. //	if (root == nullptr)
    461. //		return 0;
    462. //
    463. //	int lh = _maxHeight(root->_left);
    464. //	int rh = _maxHeight(root->_right);
    465. //
    466. //	return lh > rh ? lh + 1 : rh + 1;
    467. //}
    468. 求最短路径
    469. //int _minHeight(Node* root)
    470. //{
    471. //	if (root == nullptr)
    472. //		return 0;
    473. //
    474. //	int lh = _minHeight(root->_left);
    475. //	int rh = _minHeight(root->_right);
    476. //
    477. //	return lh < rh ? lh + 1 : rh + 1;
    478. //}
    479. 1.中序遍历（递归版）
    480. //void _InOrder(Node* root)
    481. //{
    482. //	if (root == nullptr)
    483. //		return;
    484. //
    485. //	_InOrder(root->_left);
    486. //	cout << root->_kv.first << " ";
    487. //	_InOrder(root->_right);
    488. //}
    489. 2.前序遍历（递归版）
    490. //void _PrevOrder(Node* root)
    491. //{
    492. //	if (root == nullptr)
    493. //		return;
    494. //
    495. //	cout << root->_kv.first << " ";
    496. //	_PrevOrder(root->_left);
    497. //	_PrevOrder(root->_right);
    498. //}
    499. 3.后序遍历（递归版）
    500. //void _PostOrder(Node* root)
    501. //{
    502. //	if (root == nullptr)
    503. //		return;
    504. //
    505. //	_PostOrder(root->_left);
    506. //	_PostOrder(root->_right);
    507. //	cout << root->_kv.first << " ";
    508. //}
    509. 判断是否为有效红黑树
    510. //bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
    511. //{
    512. //	//走到null之后，判断k和black是否相等
    513. //	if (nullptr == pRoot)
    514. //	{
    515. //		if (k != blackCount)
    516. //		{
    517. //			cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
    518. //			return false;
    519. //		}
    520. //		return true;
    521. //	}
    522. //
    523. //	// 统计黑色节点的个数
    524. //	if (BLACK == pRoot->_col)
    525. //		k++;
    526. //
    527. //	// 检测当前节点与其双亲是否都为红色
    528. //	if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
    529. //	{
    530. //		cout << "违反性质三：存在连在一起的红色节点" << endl;
    531. //		return false;
    532. //	}
    533. //
    534. //	return _IsValidRBTree(pRoot->_left, k, blackCount) &&
    535. //		_IsValidRBTree(pRoot->_right, k, blackCount);
    536. //}
    537. //
    538. //public:
    539. //	//遍历
    540. //	void InOrder()
    541. //	{
    542. //		cout << "中序遍历：";
    543. //		_InOrder(_root);
    544. //		cout << endl;
    545. //	}
    546. //	void PrevOrder()
    547. //	{
    548. //		cout << "前序遍历：";
    549. //		_PrevOrder(_root);
    550. //		cout << endl;
    551. //	}
    552. //	void PostOrder()
    553. //	{
    554. //		cout << "后序遍历：";
    555. //		_PostOrder(_root);
    556. //		cout << endl;
    557. //	}
    558. //
    559. //	void Height()
    560. //	{
    561. //		cout << "最长路径:" << _maxHeight(_root) << endl;
    562. //		cout << "最短路径:" << _minHeight(_root) << endl;
    563. //	}
    564. //
    565. //	bool IsBalanceTree()
    566. //	{
    567. //		// 检查红黑树几条规则
    568. //
    569. //		Node* pRoot = _root;
    570. //		// 空树也是红黑树
    571. //		if (nullptr == pRoot)
    572. //			return true;
    573. //
    574. //		// 检测根节点是否满足情况
    575. //		if (BLACK != pRoot->_col)
    576. //		{
    577. //			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
    578. //			return false;
    579. //		}
    580. //
    581. //		// 获取任意一条路径中黑色节点的个数 -- 比较基准值
    582. //		size_t blackCount = 0;
    583. //		Node* pCur = pRoot;
    584. //		while (pCur)
    585. //		{
    586. //			if (BLACK == pCur->_col)
    587. //				blackCount++;
    588. //
    589. //			pCur = pCur->_left;
    590. //		}
    591. //
    592. //		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
    593. //		size_t k = 0;
    594. //		return _IsValidRBTree(pRoot, k, blackCount);
    595. //	}

    （3）test.cpp:

    1. #include"set.h"
    2.  
    3. int main()
    4. {
    5. 	my::test_set1();
    6. 	return 0;
    7. }

    后记：
    ●由于作者水平有限，文章难免存在谬误之处，敬请读者斧正，俚语成篇，恳望指教！

                                                                           ——By 作者：新晓·故知

  • 相关阅读:
    计算机毕业设计（附源码）python疫情期间的校园防控管理系统
    《优化接口设计的思路》系列：第四篇—接口的权限控制
    React重新渲染指南
    借势热点：如何快速讲今日热点跟我们的视频结合起来？支招三把斧
    电拖基础JIAOXUE
    CppCheck
    图解网络（四）——IP篇
    28. 使用 k8e 玩转 kube-vip with Cilium‘s Egress Gateway 特性
    【JavaWeb从零到一】JSP&EL&JSTL
    电脑如何截屏？一起来揭晓答案！
  • 原文地址：https://blog.csdn.net/m0_57859086/article/details/126325178