• 【C++】如何用一棵红黑树同时封装出set与map

    👀樊梓慕：个人主页

     🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

    🌝每一个不曾起舞的日子，都是对生命的辜负

    目录

    前言

    1.红黑树模板参数的控制

    2.红黑树节点的定义 

    3.pair的比较规则引出红黑树仿函数设计

    4.红黑树的正向迭代器 

    4.1迭代器的定义 

    4.2迭代器的构造 

    4.3重载解引用操作符 * 

    4.4重载箭头操作符 -> 

    4.5重载 == 和 != 操作符 

    4.6重载 ++、-- 操作符 

    5.红黑树的反向迭代器

    6.完整代码

    RBTree.h

    MySet.h

    MyMap.h

    前言

    在之前的学习中，我们了解到set中存储的一般为键K即可，而map存储的一般都是键值对KV，也就是说他们结构是不同的，那么我们如何才能用一颗红黑树同时封装出set与map两种容器呢？

    简单的说就是模板的使用，对于set存储的，对于map存储的是>;

    那么红黑树我们就可以使用模板，比如RBTree，T就是这个模板类，当set使用时就是K，当map使用时就是pair。

    那么接下来我们具体地来研究下STL库中是怎样实现的，并且进行模拟实现。

    欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。 

    =========================================================================

    GITEE相关代码：🌟樊飞 (fanfei_c) - Gitee.com🌟

    =========================================================================

    1.红黑树模板参数的控制

    1. template<class K, class T>
    2. class RBTree

    那么对于set：

    1. template<class K>
    2. class set
    3. {
    4. public:
    5. 	//...
    6. private:
    7. 	RBTree _t;
    8. };

    对于map：

    1. template<class K, class V>
    2. class map
    3. {
    4. public:
    5. 	//...
    6. private:
    7. 	RBTree> _t;
    8. };

    即：

     思考：既然对于map来说pair中有K，那么是不是可以将第一个模板参数省略呢？

    • 对于set容器来说：可以，因为set传入红黑树的第二个参数与第一个参数是一样的；
    • 对于map容器来说：不行，因为map容器所提供的接口当中有些是只要求给出键值Key的，比如find和erase。

    2.红黑树节点的定义 

    1. //红黑树结点的定义
    2. template<class T>
    3. struct RBTreeNode
    4. {
    5. 	//三叉链
    6. 	RBTreeNode* _left;
    7. 	RBTreeNode* _right;
    8. 	RBTreeNode* _parent;
    9.  
    10. 	//存储的数据
    11. 	T _data;
    12.  
    13. 	//结点的颜色
    14. 	int _col;
    15.  
    16. 	//构造函数
    17. 	RBTreeNode(const T& data)
    18. 		: _left(nullptr)
    19. 		, _right(nullptr)
    20. 		, _parent(nullptr)
    21. 		, _data(data)
    22. 		, _col(RED)
    23. 	{}
    24. };

    对于模板参数T来说，set使用就是K，map使用就是pair，对应着set与map中节点存储的数据类型。

    3.pair的比较规则引出红黑树仿函数设计

    红黑树是一棵二叉搜索树，所以当我们寻找插入位置或者查找时一定会比较节点值之间的大小。

    新插入节点值小于当前节点值，就往左走；

    新插入节点值大于当前节点值，就往右走；

    这是之前学习二叉搜索树最基本的特性，那么问题来了，对于map而言，节点值存储的是pair，可是pair是依据什么来决定自身的大小呢？first？second？还是什么？

    我们来看一下STL库中对pair比较大小的定义：

    可我们期望的比较规则是这样么？

    很明显不是，我们期望的是set与map都只依据Key来比较大小。

    那么我们就需要想办法构造一个我们自己比较的方式出来。

    首先比较的是Key，所以我们需要想办法取出Key，对于set而言那就是Key，对于map而言是pair的first，所以我们可以在红黑树中设计仿函数来统一设计，然后在set和map中具体实现即可。

    set：

    1. template<class K>
    2. class set
    3. {
    4. 	//仿函数
    5. 	struct SetKeyOfT
    6. 	{
    7. 		const K& operator()(const K& key) //返回键值Key
    8. 		{
    9. 			return key;
    10. 		}
    11. 	};
    12. public:
    13. 	//...
    14. private:
    15. 	RBTree _t;
    16. };

    map：

    1. template<class K, class V>
    2. class map
    3. {
    4. 	//仿函数
    5. 	struct MapKeyOfT
    6. 	{
    7. 		const K& operator()(const pair& kv) //返回键值对当中的键值Key
    8. 		{
    9. 			return kv.first;
    10. 		}
    11. 	};
    12. public:
    13. 	//...
    14. private:
    15. 	RBTree, MapKeyOfT> _t;
    16. };

    RBTree：

    1. template<class K, class T, class KeyOfT>
    2. class RBTree
    3. {
    4. 	typedef RBTreeNode Node; //结点的类型
    5. public:
    6.     //...
    7. private:
    8.     Node* _root;
    9. }

    即：

    在实现红黑树时，只需要创建这个KeyOfT类对象，就相当于实例化了对应的set或map中实际的方法，比如：

    1. //查找函数
    2. iterator Find(const K& key)
    3. {
    4. 	KeyOfT kot;
    5. 	Node* cur = _root;
    6. 	while (cur)
    7. 	{
    8. 		if (key < kot(cur->_data)) //key值小于该结点的值
    9. 		{
    10. 			cur = cur->_left; //在该结点的左子树当中查找
    11. 		}
    12. 		else if (key > kot(cur->_data)) //key值大于该结点的值
    13. 		{
    14. 			cur = cur->_right; //在该结点的右子树当中查找
    15. 		}
    16. 		else //找到了目标结点
    17. 		{
    18. 			return iterator(cur); //返回该结点
    19. 		}
    20. 	}
    21. 	return end(); //查找失败
    22. }

    所以对于红黑树来说，所有对应的需要比较的部分我们都需要进行修改。 

    4.红黑树的正向迭代器 

    红黑树的正向迭代器实际上就是对结点指针进行了封装，因此在正向迭代器当中实际上就只有一个成员变量，那就是正向迭代器所封装结点的指针。

    4.1迭代器的定义 

    1. //正向迭代器
    2. template<class T, class Ref, class Ptr>
    3. struct __TreeIterator
    4. {
    5.     typedef RBTreeNode Node; //结点的类型
    6.     typedef __TreeIterator Self; //正向迭代器的类型
    7.  
    8.     Node* _node; //正向迭代器所封装结点的指针
    9. };

    4.2迭代器的构造 

    我们通过一个结点的指针便可以构造出一个正向迭代器。

    1. //构造函数
    2. __TreeIterator(Node* node)
    3.     :_node(node) //根据所给结点指针构造一个正向迭代器
    4. {}

    4.3重载解引用操作符 * 

    当对正向迭代器进行解引用操作时，我们直接返回对应结点数据的引用即可。

    1. Ref operator*()
    2. {
    3.     return _node->_data; //返回结点数据的引用
    4. }

    4.4重载箭头操作符 -> 

    当对正向迭代器进行->操作时，我们直接返回对应结点数据的指针即可。

    1. Ptr operator->()
    2. {
    3.     return &_node->_data; //返回结点数据的指针
    4. }

    注意：这里与链表List部分的->操作符重载一样，返回的是地址，即使用时为了可读性省略了一个->。 

    4.5重载 == 和 != 操作符 

    实现时直接判断两个迭代器所封装的结点是否是同一个即可。

    1. //判断两个正向迭代器是否不同
    2. bool operator!=(const Self& s) const
    3. {
    4.     return _node != s._node; //判断两个正向迭代器所封装的结点是否是同一个
    5. }
    6. //判断两个正向迭代器是否相同
    7. bool operator==(const Self& s) const
    8. {
    9.     return _node == s._node; //判断两个正向迭代器所封装的结点是否是同一个
    10. }

    4.6重载 ++、-- 操作符 

    之前链表List迭代器的 ++ 操作符重载的逻辑非常简单，只需要 node=node->next即可，但是对于一棵二叉搜索树而言显然不会这么简单。

    那么按照搜索的逻辑，我们知道++应该得到的是中序遍历的后一个节点。

    根据图像我们可以推导出 ++ 的逻辑： 

    1. 如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。
    2. 如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。
    1. //前置++
    2. Self operator++()
    3. {
    4. 	if (_node->_right) //结点的右子树不为空
    5. 	{
    6. 		//寻找该结点右子树当中的最左结点
    7. 		Node* left = _node->_right;
    8. 		while (left->_left)
    9. 		{
    10. 			left = left->_left;
    11. 		}
    12. 		_node = left; //++后变为该结点
    13. 	}
    14. 	else //结点的右子树为空
    15. 	{
    16. 		//寻找孩子不在父亲右的祖先
    17. 		Node* cur = _node;
    18. 		Node* parent = cur->_parent;
    19. 		while (parent&&cur == parent->_right)
    20. 		{
    21. 			cur = parent;
    22. 			parent = parent->_parent;
    23. 		}
    24. 		_node = parent; //++后变为该结点
    25. 	}
    26. 	return *this;
    27. }

    那么同样的对于 -- 操作符的逻辑如下：

    1. 如果当前结点的左子树不为空，则--操作后应该找到其左子树当中的最右结点。
    2. 如果当前结点的左子树为空，则--操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。
    1. //前置--
    2. Self operator--()
    3. {
    4. 	if (_node->_left) //结点的左子树不为空
    5. 	{
    6. 		//寻找该结点左子树当中的最右结点
    7. 		Node* right = _node->_left;
    8. 		while (right->_right)
    9. 		{
    10. 			right = right->_right;
    11. 		}
    12. 		_node = right; //--后变为该结点
    13. 	}
    14. 	else //结点的左子树为空
    15. 	{
    16. 		//寻找孩子不在父亲左的祖先
    17. 		Node* cur = _node;
    18. 		Node* parent = cur->_parent;
    19. 		while (parent&&cur == parent->_left)
    20. 		{
    21. 			cur = parent;
    22. 			parent = parent->_parent;
    23. 		}
    24. 		_node = parent; //--后变为该结点
    25. 	}
    26. 	return *this;
    27. }

    正向迭代器实现后，我们需要在红黑树的实现当中进行迭代器类型的typedef。

    需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。

    然后在红黑树当中实现成员函数begin和end：

    • begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
    • end函数返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器。
    1. template<class K, class T, class KeyOfT>
    2. class RBTree
    3. {
    4. 	typedef RBTreeNode Node; //结点的类型
    5. public:
    6. 	typedef __TreeIterator iterator; //正向迭代器
    7. 	
    8. 	iterator begin()
    9. 	{
    10. 		//寻找最左结点
    11. 		Node* left = _root;
    12. 		while (left&&left->_left)
    13. 		{
    14. 			left = left->_left;
    15. 		}
    16. 		//返回最左结点的正向迭代器
    17. 		return iterator(left);
    18. 	}
    19. 	iterator end()
    20. 	{
    21. 		//返回由nullptr构造得到的正向迭代器（不严谨）
    22. 		return iterator(nullptr);
    23. 	}
    24. private:
    25. 	Node* _root; //红黑树的根结点
    26. };

    但这样实现的end()迭代器其实并不符合要求，因为如果对end()位置的迭代器--后，应该得到最后一个位置的正向迭代器，但这里很明显无法实现。

    实际上在STL库中是这样设计的：

    在红黑树的根节点新增一个头节点，这个头结点的左孩子为最左节点，右孩子为最右节点。

    在这样的结构下，正向迭代器的begin()只需用头节点的左孩子构造即可，反向迭代器的rbegin()只需用头结点的右孩子构造出一个正向迭代器然后再对该正向迭代器进行封装，得到反向迭代器即可。end和rend()

    但是如果红黑树加入了这个头节点，就会改变之前我们实现的红黑树的很多逻辑，这里就不实现了。

    5.红黑树的反向迭代器

    还记得我们之前学习过的反向迭代器的实现么？

    【C++】反向迭代器模拟实现-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/2301_77112634/article/details/135837568?spm=1001.2014.3001.5502

    反向迭代器需不需要我们从零开始写呢？还是和适配器一样，利用普通迭代器的结构满足反向迭代器的特性即可？这样是不是比较方便？

    • rbegin()相当于end()
    • rend()相当于begin()
    • 反向迭代器++相当于正向迭代器--
    • 其他操作* != ->和正向迭代器相同
    1. //反向迭代器---迭代器适配器
    2. template<class Iterator>
    3. struct ReverseIterator
    4. {
    5. 	typedef ReverseIterator Self; //反向迭代器的类型
    6.     
    7.     //限定符不能区分静态变量和类型，所以前面可以加上typename标识为类型
    8. 	typedef typename Iterator::reference Ref; //结点指针的引用
    9. 	typedef typename Iterator::pointer Ptr; //结点指针
    10.  
    11. 	Iterator _it; //反向迭代器所封装的正向迭代器
    12.  
    13. 	//构造函数
    14. 	ReverseIterator(Iterator it)
    15. 		:_it(it) //根据所给正向迭代器构造一个反向迭代器
    16. 	{}
    17.  
    18. 	Ref operator*()
    19. 	{
    20. 		return *_it; //通过调用正向迭代器的operator*返回结点数据的引用
    21. 	}
    22. 	Ptr operator->()
    23. 	{
    24. 		return _it.operator->(); //通过调用正向迭代器的operator->返回结点数据的指针
    25. 	}
    26.  
    27. 	//前置++
    28. 	Self& operator++()
    29. 	{
    30. 		--_it; //调用正向迭代器的前置--
    31. 		return *this;
    32. 	}
    33. 	//前置--
    34. 	Self& operator--()
    35. 	{
    36. 		++_it; //调用正向迭代器的前置++
    37. 		return *this;
    38. 	}
    39.  
    40. 	bool operator!=(const Self& s) const
    41. 	{
    42. 		return _it != s._it; //调用正向迭代器的operator!=
    43. 	}
    44. 	bool operator==(const Self& s) const
    45. 	{
    46. 		return _it == s._it; //调用正向迭代器的operator==
    47. 	}
    48. };

    需要注意的是，反向迭代器只接收了一个模板参数，即正向迭代器的类型，也就是说，反向迭代器不知道结点的引用类型和结点的指针类型，因此我们需要在正向迭代器当中对这两个类型进行typedef，这样反向迭代器才能通过正向迭代器获取结点的引用类型和结点的指针类型。

    1. //正向迭代器
    2. template<class T, class Ref, class Ptr>
    3. struct __TreeIterator
    4. {
    5. 	typedef Ref reference; //结点指针的引用
    6. 	typedef Ptr pointer; //结点指针
    7. };

    反向迭代器的rbegin()：红黑树的最右节点；

    反向迭代器的rend()：空指针构造；

    1. template<class K, class T, class KeyOfT>
    2. class RBTree
    3. {
    4. 	typedef RBTreeNode Node; //结点的类型
    5. public:
    6. 	typedef ReverseIterator reverse_iterator; //反向迭代器
    7. 	
    8. 	reverse_iterator rbegin()
    9. 	{
    10. 		//寻找最右结点
    11. 		Node* right = _root;
    12. 		while (right&&right->_right)
    13. 		{
    14. 			right = right->_right;
    15. 		}
    16. 		//返回最右结点的反向迭代器
    17. 		return reverse_iterator(iterator(right));
    18. 	}
    19. 	reverse_iterator rend()
    20. 	{
    21. 		//返回由nullptr构造得到的反向迭代器（不严谨）
    22. 		return reverse_iterator(iterator(nullptr));
    23. 	}
    24. private:
    25. 	Node* _root; //红黑树的根结点
    26. };

    注意：此时迭代器指向的值可以被修改，而在set中我们存储的是,map中存储的是>，为了防止二叉树遭到破坏，所以我们需要进行类似这样的处理：

    • set;
    • map>;

    6.完整代码

    RBTree.h

    1. #pragma once
    2.  
    3. //枚举定义结点的颜色
    4. enum Colour
    5. {
    6. 	RED,
    7. 	BLACK
    8. };
    9.  
    10. //红黑树结点的定义
    11. template<class T>
    12. struct RBTreeNode
    13. {
    14. 	//三叉链
    15. 	RBTreeNode* _left;
    16. 	RBTreeNode* _right;
    17. 	RBTreeNode* _parent;
    18.  
    19. 	//存储的数据
    20. 	T _data;
    21.  
    22. 	//结点的颜色
    23. 	int _col; //红/黑
    24.  
    25. 	//构造函数
    26. 	RBTreeNode(const T& data)
    27. 		: _left(nullptr)
    28. 		, _right(nullptr)
    29. 		, _parent(nullptr)
    30. 		, _data(data)
    31. 		, _col(RED)
    32. 	{}
    33. };
    34.  
    35. //正向迭代器
    36. template<class T, class Ref, class Ptr>
    37. struct __TreeIterator
    38. {
    39. 	typedef Ref reference; //结点指针的引用
    40. 	typedef Ptr pointer; //结点指针
    41.  
    42. 	typedef RBTreeNode Node; //结点的类型
    43. 	typedef __TreeIterator Self; //正向迭代器的类型
    44.  
    45. 	Node* _node; //正向迭代器所封装结点的指针
    46.  
    47. 	//构造函数
    48. 	__TreeIterator(Node* node)
    49. 		:_node(node) //根据所给结点指针构造一个正向迭代器
    50. 	{}
    51.  
    52. 	Ref operator*()
    53. 	{
    54. 		return _node->_data; //返回结点数据的引用
    55. 	}
    56. 	Ptr operator->()
    57. 	{
    58. 		return &_node->_data; //返回结点数据的指针
    59. 	}
    60. 	//判断两个正向迭代器是否不同
    61. 	bool operator!=(const Self& s) const
    62. 	{
    63. 		return _node != s._node; //判断两个正向迭代器所封装的结点是否是同一个
    64. 	}
    65. 	//判断两个正向迭代器是否相同
    66. 	bool operator==(const Self& s) const
    67. 	{
    68. 		return _node == s._node; //判断两个正向迭代器所封装的结点是否是同一个
    69. 	}
    70.  
    71. 	//前置++
    72. 	Self operator++()
    73. 	{
    74. 		if (_node->_right) //结点的右子树不为空
    75. 		{
    76. 			//寻找该结点右子树当中的最左结点
    77. 			Node* left = _node->_right;
    78. 			while (left->_left)
    79. 			{
    80. 				left = left->_left;
    81. 			}
    82. 			_node = left; //++后变为该结点
    83. 		}
    84. 		else //结点的右子树为空
    85. 		{
    86. 			//寻找孩子不在父亲右的祖先
    87. 			Node* cur = _node;
    88. 			Node* parent = cur->_parent;
    89. 			while (parent && cur == parent->_right)
    90. 			{
    91. 				cur = parent;
    92. 				parent = parent->_parent;
    93. 			}
    94. 			_node = parent; //++后变为该结点
    95. 		}
    96. 		return *this;
    97. 	}
    98.  
    99. 	//前置--
    100. 	Self operator--()
    101. 	{
    102. 		if (_node->_left) //结点的左子树不为空
    103. 		{
    104. 			//寻找该结点左子树当中的最右结点
    105. 			Node* right = _node->_left;
    106. 			while (right->_right)
    107. 			{
    108. 				right = right->_right;
    109. 			}
    110. 			_node = right; //--后变为该结点
    111. 		}
    112. 		else //结点的左子树为空
    113. 		{
    114. 			//寻找孩子不在父亲左的祖先
    115. 			Node* cur = _node;
    116. 			Node* parent = cur->_parent;
    117. 			while (parent && cur == parent->_left)
    118. 			{
    119. 				cur = parent;
    120. 				parent = parent->_parent;
    121. 			}
    122. 			_node = parent; //--后变为该结点
    123. 		}
    124. 		return *this;
    125. 	}
    126. };
    127.  
    128. //反向迭代器---迭代器适配器
    129. template<class Iterator>
    130. struct ReverseIterator
    131. {
    132. 	typedef ReverseIterator Self; //反向迭代器的类型
    133. 	typedef typename Iterator::reference Ref; //结点指针的引用
    134. 	typedef typename Iterator::pointer Ptr; //结点指针
    135.  
    136. 	Iterator _it; //反向迭代器所封装的正向迭代器
    137.  
    138. 	//构造函数
    139. 	ReverseIterator(Iterator it)
    140. 		:_it(it) //根据所给正向迭代器构造一个反向迭代器
    141. 	{}
    142.  
    143. 	Ref operator*()
    144. 	{
    145. 		return *_it; //通过调用正向迭代器的operator*返回结点数据的引用
    146. 	}
    147. 	Ptr operator->()
    148. 	{
    149. 		return _it.operator->(); //通过调用正向迭代器的operator->返回结点数据的指针
    150. 	}
    151.  
    152. 	//前置++
    153. 	Self& operator++()
    154. 	{
    155. 		--_it; //调用正向迭代器的前置--
    156. 		return *this;
    157. 	}
    158. 	//前置--
    159. 	Self& operator--()
    160. 	{
    161. 		++_it; //调用正向迭代器的前置++
    162. 		return *this;
    163. 	}
    164.  
    165. 	bool operator!=(const Self& s) const
    166. 	{
    167. 		return _it != s._it; //调用正向迭代器的operator!=
    168. 	}
    169. 	bool operator==(const Self& s) const
    170. 	{
    171. 		return _it == s._it; //调用正向迭代器的operator==
    172. 	}
    173. };
    174.  
    175. //红黑树的实现
    176. template<class K, class T, class KeyOfT>
    177. class RBTree
    178. {
    179. 	typedef RBTreeNode Node; //结点的类型
    180. public:
    181. 	typedef __TreeIterator iterator; //正向迭代器
    182. 	typedef ReverseIterator reverse_iterator; //反向迭代器
    183.  
    184. 	reverse_iterator rbegin()
    185. 	{
    186. 		//寻找最右结点
    187. 		Node* right = _root;
    188. 		while (right && right->_right)
    189. 		{
    190. 			right = right->_right;
    191. 		}
    192. 		//返回最右结点的反向迭代器
    193. 		return reverse_iterator(iterator(right));
    194. 	}
    195. 	reverse_iterator rend()
    196. 	{
    197. 		//返回由nullptr构造得到的反向迭代器（不严谨）
    198. 		return reverse_iterator(iterator(nullptr));
    199. 	}
    200.  
    201. 	iterator begin()
    202. 	{
    203. 		//寻找最左结点
    204. 		Node* left = _root;
    205. 		while (left && left->_left)
    206. 		{
    207. 			left = left->_left;
    208. 		}
    209. 		//返回最左结点的正向迭代器
    210. 		return iterator(left);
    211. 	}
    212. 	iterator end()
    213. 	{
    214. 		//返回由nullptr构造得到的正向迭代器（不严谨）
    215. 		return iterator(nullptr);
    216. 	}
    217. 	//构造函数
    218. 	RBTree()
    219. 		:_root(nullptr)
    220. 	{}
    221.  
    222. 	//拷贝构造
    223. 	RBTree(const RBTree& t)
    224. 	{
    225. 		_root = _Copy(t._root, nullptr);
    226. 	}
    227.  
    228. 	//赋值运算符重载（现代写法）
    229. 	RBTree& operator=(RBTree t)
    230. 	{
    231. 		swap(_root, t._root);
    232. 		return *this; //支持连续赋值
    233. 	}
    234.  
    235. 	//析构函数
    236. 	~RBTree()
    237. 	{
    238. 		_Destroy(_root);
    239. 		_root = nullptr;
    240. 	}
    241.  
    242. 	//查找函数
    243. 	iterator Find(const K& key)
    244. 	{
    245. 		KeyOfT kot;
    246. 		Node* cur = _root;
    247. 		while (cur)
    248. 		{
    249. 			if (key < kot(cur->_data)) //key值小于该结点的值
    250. 			{
    251. 				cur = cur->_left; //在该结点的左子树当中查找
    252. 			}
    253. 			else if (key > kot(cur->_data)) //key值大于该结点的值
    254. 			{
    255. 				cur = cur->_right; //在该结点的右子树当中查找
    256. 			}
    257. 			else //找到了目标结点
    258. 			{
    259. 				return iterator(cur); //返回该结点
    260. 			}
    261. 		}
    262. 		return end(); //查找失败
    263. 	}
    264.  
    265. 	//插入函数
    266. 	pairbool> Insert(const T& data)
    267. 	{
    268. 		if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
    269. 		{
    270. 			_root = new Node(data);
    271. 			_root->_col = BLACK; //根结点必须是黑色
    272. 			return make_pair(iterator(_root), true); //插入成功
    273. 		}
    274. 		//1、按二叉搜索树的插入方法，找到待插入位置
    275. 		KeyOfT kot;
    276. 		Node* cur = _root;
    277. 		Node* parent = nullptr;
    278. 		while (cur)
    279. 		{
    280. 			if (kot(data) < kot(cur->_data)) //待插入结点的key值小于当前结点的key值
    281. 			{
    282. 				//往该结点的左子树走
    283. 				parent = cur;
    284. 				cur = cur->_left;
    285. 			}
    286. 			else if (kot(data) > kot(cur->_data)) //待插入结点的key值大于当前结点的key值
    287. 			{
    288. 				//往该结点的右子树走
    289. 				parent = cur;
    290. 				cur = cur->_right;
    291. 			}
    292. 			else //待插入结点的key值等于当前结点的key值
    293. 			{
    294. 				return make_pair(iterator(cur), false); //插入失败
    295. 			}
    296. 		}
    297.  
    298. 		//2、将待插入结点插入到树中
    299. 		cur = new Node(data); //根据所给值构造一个结点
    300. 		Node* newnode = cur; //记录新插入的结点（便于后序返回）
    301. 		if (kot(data) < kot(parent->_data)) //新结点的key值小于parent的key值
    302. 		{
    303. 			//插入到parent的左边
    304. 			parent->_left = cur;
    305. 			cur->_parent = parent;
    306. 		}
    307. 		else //新结点的key值大于parent的key值
    308. 		{
    309. 			//插入到parent的右边
    310. 			parent->_right = cur;
    311. 			cur->_parent = parent;
    312. 		}
    313.  
    314. 		//3、若插入结点的父结点是红色的，则需要对红黑树进行调整
    315. 		while (parent && parent->_col == RED)
    316. 		{
    317. 			Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在
    318. 			if (parent == grandfather->_left) //parent是grandfather的左孩子
    319. 			{
    320. 				Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
    321. 				if (uncle && uncle->_col == RED) //情况1：uncle存在且为红
    322. 				{
    323. 					//颜色调整
    324. 					parent->_col = uncle->_col = BLACK;
    325. 					grandfather->_col = RED;
    326.  
    327. 					//继续往上处理
    328. 					cur = grandfather;
    329. 					parent = cur->_parent;
    330. 				}
    331. 				else //情况2+情况3：uncle不存在 + uncle存在且为黑
    332. 				{
    333. 					if (cur == parent->_left)
    334. 					{
    335. 						RotateR(grandfather); //右单旋
    336.  
    337. 						//颜色调整
    338. 						grandfather->_col = RED;
    339. 						parent->_col = BLACK;
    340. 					}
    341. 					else //cur == parent->_right
    342. 					{
    343. 						RotateLR(grandfather); //左右双旋
    344.  
    345. 						//颜色调整
    346. 						grandfather->_col = RED;
    347. 						cur->_col = BLACK;
    348. 					}
    349. 					break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
    350. 				}
    351. 			}
    352. 			else //parent是grandfather的右孩子
    353. 			{
    354. 				Node* uncle = grandfather->_left; //uncle是grandfather的左孩子
    355. 				if (uncle && uncle->_col == RED) //情况1：uncle存在且为红
    356. 				{
    357. 					//颜色调整
    358. 					uncle->_col = parent->_col = BLACK;
    359. 					grandfather->_col = RED;
    360.  
    361. 					//继续往上处理
    362. 					cur = grandfather;
    363. 					parent = cur->_parent;
    364. 				}
    365. 				else //情况2+情况3：uncle不存在 + uncle存在且为黑
    366. 				{
    367. 					if (cur == parent->_left)
    368. 					{
    369. 						RotateRL(grandfather); //右左双旋
    370.  
    371. 						//颜色调整
    372. 						cur->_col = BLACK;
    373. 						grandfather->_col = RED;
    374. 					}
    375. 					else //cur == parent->_right
    376. 					{
    377. 						RotateL(grandfather); //左单旋
    378.  
    379. 						//颜色调整
    380. 						grandfather->_col = RED;
    381. 						parent->_col = BLACK;
    382. 					}
    383. 					break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
    384. 				}
    385. 			}
    386. 		}
    387. 		_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）
    388. 		return make_pair(iterator(newnode), true); //插入成功
    389. 	}
    390.  
    391. private:
    392. 	//拷贝树
    393. 	Node* _Copy(Node* root, Node* parent)
    394. 	{
    395. 		if (root == nullptr)
    396. 		{
    397. 			return nullptr;
    398. 		}
    399. 		Node* copyNode = new Node(root->_data);
    400. 		copyNode->_parent = parent;
    401. 		copyNode->_left = _Copy(root->_left, copyNode);
    402. 		copyNode->_right = _Copy(root->_right, copyNode);
    403. 		return copyNode;
    404. 	}
    405.  
    406. 	//析构函数子函数
    407. 	void _Destroy(Node* root)
    408. 	{
    409. 		if (root == nullptr)
    410. 		{
    411. 			return;
    412. 		}
    413. 		_Destroy(root->_left);
    414. 		_Destroy(root->_right);
    415. 		delete root;
    416. 	}
    417.  
    418. 	//左单旋
    419. 	void RotateL(Node* parent)
    420. 	{
    421. 		Node* subR = parent->_right;
    422. 		Node* subRL = subR->_left;
    423. 		Node* parentParent = parent->_parent;
    424.  
    425. 		//建立subRL与parent之间的联系
    426. 		parent->_right = subRL;
    427. 		if (subRL)
    428. 			subRL->_parent = parent;
    429.  
    430. 		//建立parent与subR之间的联系
    431. 		subR->_left = parent;
    432. 		parent->_parent = subR;
    433.  
    434. 		//建立subR与parentParent之间的联系
    435. 		if (parentParent == nullptr)
    436. 		{
    437. 			_root = subR;
    438. 			_root->_parent = nullptr;
    439. 		}
    440. 		else
    441. 		{
    442. 			if (parent == parentParent->_left)
    443. 			{
    444. 				parentParent->_left = subR;
    445. 			}
    446. 			else
    447. 			{
    448. 				parentParent->_right = subR;
    449. 			}
    450. 			subR->_parent = parentParent;
    451. 		}
    452. 	}
    453.  
    454. 	//右单旋
    455. 	void RotateR(Node* parent)
    456. 	{
    457. 		Node* subL = parent->_left;
    458. 		Node* subLR = subL->_right;
    459. 		Node* parentParent = parent->_parent;
    460.  
    461. 		//建立subLR与parent之间的联系
    462. 		parent->_left = subLR;
    463. 		if (subLR)
    464. 			subLR->_parent = parent;
    465.  
    466. 		//建立parent与subL之间的联系
    467. 		subL->_right = parent;
    468. 		parent->_parent = subL;
    469.  
    470. 		//建立subL与parentParent之间的联系
    471. 		if (parentParent == nullptr)
    472. 		{
    473. 			_root = subL;
    474. 			_root->_parent = nullptr;
    475. 		}
    476. 		else
    477. 		{
    478. 			if (parent == parentParent->_left)
    479. 			{
    480. 				parentParent->_left = subL;
    481. 			}
    482. 			else
    483. 			{
    484. 				parentParent->_right = subL;
    485. 			}
    486. 			subL->_parent = parentParent;
    487. 		}
    488. 	}
    489.  
    490. 	//左右双旋
    491. 	void RotateLR(Node* parent)
    492. 	{
    493. 		RotateL(parent->_left);
    494. 		RotateR(parent);
    495. 	}
    496.  
    497. 	//右左双旋
    498. 	void RotateRL(Node* parent)
    499. 	{
    500. 		RotateR(parent->_right);
    501. 		RotateL(parent);
    502. 	}
    503.  
    504. 	Node* _root=nullptr; //红黑树的根结点
    505. };

    MySet.h

    1. #pragma once
    2.  
    3. #include "RBTree.h"
    4.  
    5. namespace MySet
    6. {
    7. 	template<class K>
    8. 	class set
    9. 	{
    10. 		//仿函数
    11. 		struct SetKeyOfT
    12. 		{
    13. 			const K& operator()(const K& key) //返回键值Key
    14. 			{
    15. 				return key;
    16. 			}
    17. 		};
    18. 	public:
    19. 		typedef typename RBTreeconst K, SetKeyOfT>::iterator iterator; //正向迭代器
    20. 		typedef typename RBTreeconst K, SetKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器
    21.  
    22. 		iterator begin()
    23. 		{
    24. 			return _t.begin();
    25. 		}
    26. 		iterator end()
    27. 		{
    28. 			return _t.end();
    29. 		}
    30.  
    31. 		reverse_iterator rbegin()
    32. 		{
    33. 			return _t.rbegin();
    34. 		}
    35. 		reverse_iterator rend()
    36. 		{
    37. 			return _t.rend();
    38. 		}
    39.  
    40. 		//插入函数
    41. 		pairbool> insert(const K& key)
    42. 		{
    43. 			return _t.Insert(key);
    44. 		}
    45.  
    46. 		//查找函数
    47. 		iterator find(const K& key)
    48. 		{
    49. 			return _t.Find(key);
    50. 		}
    51. 	private:
    52. 		RBTreeconst K, SetKeyOfT> _t;
    53. 	};
    54.  
    55. 	void test_set1()
    56. 	{
    57. 		set<int> s;
    58. 		int a[] = { 4,2,6,1,3,5,15,7,16,14 };
    59.  
    60. 		for (auto e : a)
    61. 		{
    62. 			s.insert(e);
    63. 		}
    64.  
    65. 		set<int>::iterator it = s.begin();
    66. 		while (it != s.end())
    67. 		{
    68. 			cout << *it << " ";
    69. 			++it;
    70. 		}
    71. 		cout << endl;
    72. 	}
    73. }

    MyMap.h

    1. #pragma once
    2.  
    3. #include "RBTree.h"
    4.  
    5. namespace MyMap
    6. {
    7. 	template<class K, class V>
    8. 	class map
    9. 	{
    10. 		//仿函数
    11. 		struct MapKeyOfT
    12. 		{
    13. 			const K& operator()(const pair& kv) //返回键值对当中的键值Key
    14. 			{
    15. 				return kv.first;
    16. 			}
    17. 		};
    18. 	public:
    19. 		typedef typename RBTreeconst K, V>, MapKeyOfT>::iterator iterator; //正向迭代器
    20. 		typedef typename RBTreeconst K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //反向迭代器
    21.  
    22. 		iterator begin()
    23. 		{
    24. 			return _t.begin();
    25. 		}
    26. 		iterator end()
    27. 		{
    28. 			return _t.end();
    29. 		}
    30.  
    31. 		reverse_iterator rbegin()
    32. 		{
    33. 			return _t.rbegin();
    34. 		}
    35. 		reverse_iterator rend()
    36. 		{
    37. 			return _t.rend();
    38. 		}
    39.  
    40. 		//插入函数
    41. 		pairbool> insert(const pair<const K, V>& kv)
    42. 		{
    43. 			return _t.Insert(kv);
    44. 		}
    45. 		//[]运算符重载函数
    46. 		V& operator[](const K& key)
    47. 		{
    48. 			pairbool> ret = insert(make_pair(key, V()));
    49. 			iterator it = ret.first;
    50. 			return it->second;
    51. 		}
    52. 		//查找函数
    53. 		iterator find(const K& key)
    54. 		{
    55. 			return _t.Find(key);
    56. 		}
    57. 	private:
    58. 		RBTreeconst K, V>, MapKeyOfT> _t;
    59. 	};
    60.  
    61. 	void test_map1()
    62. 	{
    63. 		map<int, int> m;
    64. 		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
    65. 		for (auto e : a)
    66. 		{
    67. 			m.insert(make_pair(e, e));
    68. 		}
    69.  
    70. 		map<int, int>::iterator it = m.begin();
    71. 		while (it != m.end())
    72. 		{
    73. 			//it->first += 100;
    74. 			it->second += 100;
    75.  
    76. 			cout << it->first << ":" << it->second << endl;
    77. 			++it;
    78. 		}
    79. 		cout << endl;
    80. 	}
    81. }

    =========================================================================

    如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容

    🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎

    🌟~ 点赞收藏＋关注 ~🌟

    =========================================================================

  • 相关阅读:
    JS sort排序
    ENVI：如何自定义RPC文件？
    fplan-电源规划
    java计算机毕业设计旅游景点展示平台的设计与实现源程序+mysql+系统+lw文档+远程调试
    5.基于飞蛾扑火算法(MFO)优化的VMD参数（MFO-VMD）
    spring源码分析 - AnnotationConfigApplicationContext启动之refresh
    7.自定义凸多边形
    【触想智能】工控一体机与5G物联网技术结合是未来发展趋势
    武汉理工大学 Python程序设计第八章测验
    【Flutter】【package】auto_size_text 文字自动适配大小
  • 原文地址：https://blog.csdn.net/2301_77112634/article/details/136620252