• 红黑树封装 map/set 及其迭代器(C++)

    目录

    一、map/set 的封装

    1.1 封装思路

    1.2 红黑树节点调整

    1.3 map 和 set 的定义

    1.4 仿函数 KeyOfValue

    1.5 map/set 的插入

    二、map/set 迭代器实现

    2.1 迭代器的定义

    2.2 解引用运算符重载

    2.3 成员访问运算符重载

    2.4 (不)等于运算符重载

    2.5 begin() 与 end()

    2.6 ++ 运算符重载

    2.7 -- 运算符重载

    2.8 [ ]下标访问运算符重载

    三、源代码+测试用例

    3.1 map/set 

    3.2 迭代器

    3.3 测试用例

    3.4 红黑树

    一、map/set 的封装

    在实现了红黑树的部分功能后，我们可以便可以将红黑树作为底层结构来封装map 和 set ，其中map是 K-Value 模型 ，而 set 是 Key 模型。

    我们接下来将使用模板、仿函数用一棵红黑树实现 map和set。

    1.1 封装思路

    因为 map 存储的是 pair ，而 set 存储的是 Key ，所以其解决的根本方向就是：

    如果是 map，红黑树中就按照 pair 的 K 进行比较，从而插入；

    如果是 set，红黑树中就按照 Key 值进行比较，进而插入。

    让 map / set 主动传出待比较的数据，红黑树只用根据数据间关系进行插入即可，不用在乎待比较的数据是何种结构。

    1.2 红黑树节点调整

    上文我们实现的红黑树是按照键值对的方式进行存储的，而接下来我们要同时封装 map/set，故不能直接定死存储的结构，所以我们在此进行修改。

    将原来的 kv 模型改为 data 模型，data 即是比较的数据内容。

    注意，将 Kv模型改为 data后，插入与查找中比较的代码都要进行更新，稍后会讲解。

    1.3 map 和 set 的定义

    map 和 set 底层都使用的红黑树，所以我们 map/set的功能就是调用红黑树的成员函数即可。

    1. template<class K, class V>
    2. class Map
    3. {
    4. private:
    5. 	RBTree> _t;
    6. };
    7.  
    8. template<class K>
    9. class Set
    10. {
    11. private:
    12. 	RBTree _t;
    13. };

    因为 Map 有两个模板参数，而 Set 只有一个模板参数。所以当我们使用的一个红黑树实现时，要进行匹配处理。即使 Set 是一个模板参数，在调用红黑树时也要传入两个模板参数。因为第一个模板参数是匹配 Map 满足红黑树的两个模板参数，而第二个模板参数是为了让底层红黑树拿到比较的数据。

    为什么 Map 除了传入 pair 外，第一个参数直接传入 K，为什么不能省略？

    因为 Find 的存在，map中 Find 函数是直接按 pair 中的 K 进行查找的，所以要额外设置该参数。

    1.4 仿函数 KeyOfValue

    接下来我们就要将数据取出供红黑树比较了，如果是 map，就按 pair 中的 K去比较，如果是 set，就按 Key 比较。

    为此我们可以在 map 和 set 内部定义一个仿函数将其数据取出。

    1. template<class K, class V>
    2. class Map
    3. {
    4.     //Map-keyofvalue 仿函数
    5. 	struct MapKeyOfvalue
    6. 	{
    7. 		const K& operator()(const std::pair& kv)
    8. 		{
    9. 			return kv.first;
    10. 		}
    11. 	};
    12. private:
    13. 	RBTree> _t;
    14. };
    15.  
    16. template<class K>
    17. class Set
    18. {
    19.     //Set-keyofvalue 仿函数
    20.     struct SetKeyOfvalue
    21. 	{
    22. 		const K& operator()(const K& key)
    23. 		{
    24. 			return key;
    25. 		}
    26. 	};
    27. private:
    28. 	RBTree _t;
    29. };

    然后我们将其仿函数也作为模板，传入红黑树中，对应的，红黑树要添加一个模板参数来接收该仿函数。

    改动代码如下：

     改动这些之后，我们便要将红黑树中比较数据大小的地方进行修改

    用仿函数将数据取出，然后进行比较：

    1. //根据模板参数创建仿函数
    2. KeyOfvalue kovalue;
    3. if (!_root)
    4. {
    5. 	_root = new Node(data);
    6. 	_root->_col = BLACK;
    7. 	return true;
    8. }
    9. Node* parent = nullptr;
    10. Node* cur = _root;
    11. while (cur)
    12. {
    13.     //比较处————进行改动
    14. 	if (kovalue(cur->_data) > kovalue(data))
    15. 	{
    16. 		parent = cur;
    17. 		cur = cur->_left;
    18. 	}
    19.     //比较处————进行改动
    20. 	else if (kovalue(cur->_data) < kovalue(data))
    21. 	{
    22. 		parent = cur;
    23. 		cur = cur->_right;
    24. 	}
    25. 	else
    26. 	{
    27. 		return false;
    28. 	}
    29. }
    30. //创建新节点，使用data进行构造
    31. cur = new Node(data);
    32. //比较处————进行改动
    33. if (kovalue(parent->_data) > kovalue(data))
    34. {
    35. 	parent->_left = cur;
    36. }
    37. else
    38. {
    39. 	parent->_right = cur;
    40. }
    41. cur->_parent = parent;

    这样，红黑树便可以适配 map/set 的插入了。

    1.5 map/set 的插入

    接下来 map/set 的插入直接套用红黑树的即可。

    代码如下：

    1. //map的插入，插入pair
    2. bool insert(const pair& kv)
    3. {
    4. 	return _t.Insert(kv);
    5. }
    6.  
    7. //set的插入，插入key
    8. bool insert(const K& key)
    9. {
    10. 	return _t.Insert(key);
    11. }

    接下来进行测试，看我们map/set能否正常的插入数据。

    二、map/set 迭代器实现

    2.1 迭代器的定义

    1. //			 节点数据	引用/const引用  指针/const指针
    2. template <class T,class Ref,class Ptr>
    3. struct __RBTreeIterator
    4. {
    5. 	typedef RBTreeNode Node;
    6. 	typedef __RBTreeIterator self;
    7. 	Node* _node;
    8. public:
    9. 	__RBTreeIterator(Node* node)
    10. 		:_node(node)
    11. 	{}
    12. }

    首先，我们要明确，其实 map/set 只是一层套壳，其中的功能都是由红黑树实现后，再封装到map/set中供我们使用，迭代器也不例外。

    2.2 解引用运算符重载

    解引用即返回该节点的存储的数据，主要用于 set 中，返回该数据的引用。

    1. Ref operator*()
    2. {
    3. 	return _node->_data;
    4. }

    2.3 成员访问运算符重载

    成员访问操作符即返回该节点的地址，主要用于 map 中，方便访问 pair 中的first以及second。

    1. Ptr operator->()
    2. {
    3. 	return &(_node->_data);
    4. }

    2.4 (不)等于运算符重载

    1. bool operator==(const self& s) 
    2. {
    3. 	return _node == s._node;
    4. }
    5.  
    6.  
    7. bool operator!=(const self& s) 
    8. {
    9. 	return _node != s._node;
    10. }

    2.5 begin() 与 end()

    迭代器常用成员函数begin()与end()，其中begin()对应红黑树的最左节点，end()对应最后一个节点的下一个节点，即nullptr(为了简化，并未设置哨兵节点实现将其完美实现)

    1.  
    2. iterator begin()
    3. {
    4. 	Node* left = _root;
    5. 	while (left && left->_left)
    6. 	{
    7. 		left = left->_left;
    8. 	}
    9. 	return iterator(left);
    10. }
    11.  
    12. iterator end()
    13. {
    14. 	return iterator(nullptr);
    15. }

    如果 map/set 中想使用红黑树中的迭代器，我们需要在 map/set 中进行声明。

    声明如下：

    如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
    告诉编译器这是一个类型，并不是一个静态变量

    1. //如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
    2. //告诉编译器这是一个类型，并不是一个静态变量
    3. typedef typename RBTree, MapKeyOfvalue>::iterator iterator;

    注意：typename受限定符限制，尽量放在public下

    2.6 ++ 运算符重载

    首先我们需要明确，迭代器++是让当前迭代器指向红黑树中序遍历的下一个节点。

    以下图的35节点为例。

    • 当迭代器指向 35 时，进行 ++，指向右子树最左节点，即 40。
    • 当迭代器指向 40 时，进行 ++，右子树为空，指向父节点，即 45。
    • 当迭代器指向 45 时，进行 ++，指向右子树最左节点，即 48。
    • 当迭代器指向 48 时，进行 ++，指向未遍历的父节点，即 50。

    分析上面的情况，发现迭代器 ++ 始终围绕着右子树是否存在进行。

    现在我们将其抽象化，分析其规律。

    1. 右子树不为空，进行 ++ 则是指向右子树中序的第一个(最左节点)。
    2. 右子树为空，++ 找孩子不是父亲右节点的祖先。

    代码实现：

    1.  
    2. self& operator++()
    3. {
    4. 	//如果右子树存在
    5. 	if (_node->_right)
    6. 	{
    7. 		Node* left = _node->_right;
    8. 		//则寻找右子树的最左节点
    9. 		while (left->_left)
    10. 		{
    11. 			left = left->_left;
    12. 		}
    13. 		_node = left;
    14. 	}
    15. 	//如果右子树不存在
    16. 	else
    17. 	{
    18.         //找孩子不是父亲右节点的节点
    19. 		Node* parent = _node->_parent;
    20. 		Node* cur = _node;=
    21. 		while (cur == parent->_right)
    22. 		{
    23. 			cur = cur->_parent;
    24. 			parent = parent->_parent;
    25. 			//防止最后一个节点寻找祖先导致程序崩溃
    26. 			if (parent == nullptr)
    27. 			{
    28. 				break;
    29. 			}
    30. 		}
    31. 		_node = parent;
    32. 	}
    33. 	return *this;
    34. }

    需要注意，当 ++ 到最后一个节点的时候。有可能在寻找非父亲右节点的祖先时，父节点一路走到 nullptr 的情况，如图：

     

    所以在每次 parent 更新时都进行一次判断，即可。

    测试：

    这里顺序把后置 ++ 的代码实现一下，直接套用前置 ++ 即可。

    1. //迭代器后置++
    2. self operator++(int)
    3. {
    4. 	self it_temp(_node);
    5. 	++(*this);
    6. 	return it_temp;
    7. }

    2.7 -- 运算符重载

    有了前面++的模拟实现，实现 --就是反着遍历即可。

    1. 左子树不为空，进行 -- 则是指向左子树中序的最后一个(最右节点)。
    2. 左子树为空，-- 找孩子不是父亲左节点的祖先。

    代码如下:

    1. self& operator--()
    2. {
    3. 	//如果左子树存在
    4. 	if (_node->left)
    5. 	{
    6. 		//找左子树的最右节点
    7. 		Node* right = _node->_left;
    8. 		while (right->_right)
    9. 		{
    10. 			right = right->_right;
    11. 		}
    12. 		_node = rihgt;
    13. 	}
    14. 	//如果左子树不存在
    15. 	else
    16. 	{
    17. 		//找孩子不是父亲左节点的节点
    18. 		Node* parent = _node->parent;
    19. 		Node* cur = _node;
    20. 		while (parent->_left == cur)
    21. 		{
    22. 			cur = cur->_parent;
    23. 			parent = parent->_parent;
    24. 			if (parent == nullptr)
    25. 			{
    26. 				break;
    27. 			}
    28. 		}
    29. 		_node = parent;
    30. 	}
    31. 	return *this;
    32. }

    2.8 [ ]下标访问运算符重载

    我们来看 map 的 [ ] 下标访问操作符，其中 [ ]返回的是mapped_type(pair) 类型。

    我们便要对 map 中 insert 的返回值做出修改：

     注意，set 中的 insert 也是返回 pair，虽然很反常，但是官方库中确实是这样书写的。

    因为只有 set 没有 [ ] 运算符重载，所以我们 set 中不必提供该函数，只用在 map 中提供即可。

    首先，我们向 map 中 insert 数据 pair；pair的第一个参数为用户传入的 key 值，第二个参数则是用户声明的第二个模板参数的默认构造函数(如果是 int，则调用 int的构造函数，如果是 string ，则默认构造 string)。

    pairbool> result = insert(make_pair(key, V()));

    然后我们返回迭代器指向的 pair 数据中的second。

    1. //result.first取出迭代器，使用->运算符重载取出data地址，访问second并返回
    2. return result.first->second;

    完整的函数书写如下：

    1. V& operator[](const K& key)
    2. {
    3. 	pairbool> result = insert(make_pair(key, V()));
    4. 	//如果存在，则插入失败
    5. 	//如果不存在，则插入数据
    6. 	//无论是否存在,都返回 second;
    7. 	return result.first->second;
    8. }

    接下来我们要对红黑树的 Insert 的返回值处进行改动，进而契合 map 的 pair 数据类型。改动有三处，这里贴图大家观察即可。

    测试：

    三、源代码+测试用例

    3.1 map/set 

    1. namespace brant
    2. {
    3. 	template<class K,class V>
    4. 	class Map
    5. 	{
    6. 	public:
    7. 		struct MapKeyOfvalue
    8. 		{
    9. 			const K& operator()(const std::pair& kv)
    10. 			{
    11. 				return kv.first;
    12. 			}
    13. 		};
    14. 		//外层要想使用红黑树的iterator，
    15. 		typedef typename RBTree, MapKeyOfvalue>::iterator iterator;
    16. 		iterator begin()
    17. 		{
    18. 			return _t.begin();
    19. 		}
    20.  
    21. 		iterator end()
    22. 		{
    23. 			return _t.end();
    24. 		}
    25.  
    26. 		pairbool> insert(const pair& kv)
    27. 		{
    28. 			return _t.Insert(kv);
    29. 		}
    30. 		void InOrder()
    31. 		{
    32. 			_t.Inorder();
    33. 		}
    34. 		V& operator[](const K& key)
    35. 		{
    36. 			pairbool> result = insert(make_pair(key, V()));
    37. 			return result.first->second;
    38. 		}
    39. 	private:
    40. 		RBTree, MapKeyOfvalue> _t;
    41. 	};
    42.  
    43.     template<class K>
    44. 	class Set
    45. 	{
    46. 		struct SetKeyOfvalue
    47. 		{
    48. 			const K& operator()(const K& key)
    49. 			{
    50. 				return key;
    51. 			}
    52. 		};
    53. 	public:
    54. 		typedef typename RBTree::iterator iterator;
    55. 		iterator begin()
    56. 		{
    57. 			return _t.begin();
    58. 		}
    59.  
    60. 		iterator end()
    61. 		{
    62. 			return _t.end();
    63. 		}
    64. 		
    65. 		pairbool> insert(const K& key)
    66. 		{
    67. 			return _t.Insert(key);
    68. 		}
    69.  
    70. 		void InOrder()
    71. 		{
    72. 			_t.Inorder();
    73. 		}
    74. 	private:
    75. 		RBTree _t;
    76. 	};
    77. }

    3.2 迭代器

    1. enum Color { RED, BLACK };
    2. template <class T>
    3. struct RBTreeNode
    4. {
    5. 	RBTreeNode* _left;	
    6. 	RBTreeNode* _right;	
    7. 	RBTreeNode* _parent;	
    8. 	T _data;
    9. 	Color _col;					
    10.  
    11. 	RBTreeNode(const T& data)
    12. 		:_left(nullptr)
    13. 		, _right(nullptr)
    14. 		, _parent(nullptr)
    15. 		, _data(data)
    16. 		, _col(RED)              
    17. 	{}
    18. };
    19.  
    20. //			 节点数据	引用/const引用  指针/const指针
    21. template <class T,class Ref,class Ptr>
    22. struct __RBTreeIterator
    23. {
    24. 	typedef RBTreeNode Node;
    25. 	typedef __RBTreeIterator self;
    26. 	typedef __RBTreeIterator iterator;
    27. 	Node* _node;
    28. 	__RBTreeIterator(Node* node)
    29. 		:_node(node)
    30. 	{}
    31.  
    32. 	Ref operator*()
    33. 	{
    34. 		return _node->_data;
    35. 	}
    36. 	//map常使用operator ->  返回地址，然后通过——> 访问
    37. 	Ptr operator->()
    38. 	{
    39. 		return &(_node->_data);
    40. 	}
    41.  
    42. 	bool operator==(const self& s)  
    43. 	{
    44. 		return _node == s._node;
    45. 	}
    46.  
    47. 	bool operator!=(const self& s) 
    48. 	{
    49. 		return _node != s._node;
    50. 	}
    51.  
    52. 	iterator begin()
    53. 	{
    54. 		Node* left = _node;
    55. 		while (left && left->_left)
    56. 		{
    57. 			left = left->_left;
    58. 		}
    59. 		return iterator(left);
    60. 	}
    61.  
    62. 	iterator end()
    63. 	{
    64. 		return iterator(nullptr);
    65. 	}
    66.  
    67. 	self& operator++()
    68. 	{
    69. 		//如果右子树存在
    70. 		if (_node->_right)
    71. 		{
    72. 			Node* left = _node->_right;
    73. 			//则寻找右子树的最左节点
    74. 			while (left->_left)
    75. 			{
    76. 				left = left->_left;
    77. 			}
    78. 			_node = left;
    79. 		}
    80. 		//如果右子树不存在
    81. 		else
    82. 		{
    83. 			//找孩子不是父亲右的节点
    84. 			Node* parent = _node->_parent;
    85. 			Node* cur = _node;
    86. 			while (cur == parent->_right)
    87. 			{
    88. 				cur = cur->_parent;
    89. 				parent = parent->_parent;
    90. 				//防止最后一个节点寻找祖先导致程序崩溃
    91. 				if (parent == nullptr)
    92. 				{
    93. 					break;
    94. 				}
    95. 			}
    96. 			_node = parent;
    97. 		}
    98. 		return *this;
    99. 	}
    100. 	self operator++(int)
    101. 	{
    102. 		self it_temp(_node);
    103. 		++(*this);
    104. 		return it_temp;
    105. 	}
    106.  
    107. 	self& operator--()
    108. 	{
    109. 		if (_node->left)
    110. 		{
    111. 			Node* right = _node->_left;
    112. 			while (right->_right)
    113. 			{
    114. 				right = right->_right;
    115. 			}
    116. 			_node = right;
    117. 		}
    118. 		else
    119. 		{
    120. 			Node* parent = _node->parent;
    121. 			Node* cur = _node;
    122. 			while (parent->_left == cur)
    123. 			{
    124. 				cur = cur->_parent;
    125. 				parent = parent->_parent;
    126. 				if (parent == nullptr)
    127. 				{
    128. 					break;
    129. 				}
    130. 			}
    131. 			_node = parent;
    132. 		}
    133. 		return *this;
    134. 	}
    135. };

    3.3 测试用例

    1. void test_iterator()
    2. {
    3. 	brant::Set<int> s;
    4. 	s.insert(1);
    5. 	s.insert(2);
    6. 	s.insert(3);
    7. 	s.insert(4);
    8. 	s.insert(5);
    9. 	brant::Set<int>::iterator it_set = s.begin();
    10. 	cout << "set:" << endl;
    11. 	while (it_set != s.end())
    12. 	{
    13. 		cout << *it_set << " ";
    14. 		it_set++;
    15. 	}
    16. 	cout << endl;
    17.  
    18. 	brant::Map<int, int> m;
    19. 	m.insert(make_pair(1, 100));
    20. 	m.insert(make_pair(2, 200));
    21. 	m.insert(make_pair(3, 300));
    22. 	m.insert(make_pair(4, 400));
    23. 	m.insert(make_pair(5, 500));
    24. 	brant::Map<int, int>::iterator it_map = m.begin();
    25. 	cout << "map:" << endl;
    26.  
    27. 	while (it_map != m.end())
    28. 	{
    29. 		cout << (*it_map).first 
    30. 			<< "：" << (*it_map).second << endl;
    31. 		++it_map;
    32. 	}
    33. }
    34.  
    35. void test_map_()
    36. {
    37. 	string arr[] = { "苹果", "西瓜", "苹果", "西瓜",
    38. 		"苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    39.  
    40. 	brant::Mapint> countMap;
    41. 	for (auto& str : arr)
    42. 	{
    43. 		countMap[str]++;
    44. 	}
    45.  
    46. 	brant::Mapint>::iterator it = countMap.begin();
    47. 	while (it != countMap.end())
    48. 	{
    49. 		cout << it->first << ":" << it->second << endl;
    50. 		++it;
    51. 	}
    52. 	cout << endl; 
    53. 	for (auto& kv : countMap)
    54. 	{
    55. 		cout << kv.first << ":" << kv.second << endl;
    56. 	}
    57. }

    3.4 红黑树

    只截取了改动和增添的部分。原来的红黑树在这.

    1.  
    2. template <class K, class T,class KeyOfvalue>
    3. class RBTree
    4. {
    5. 	typedef RBTreeNode Node;
    6.  
    7. public:
    8. 	typedef __RBTreeIterator iterator;
    9. 	typedef __RBTreeIteratorconst T&, const T*> const_iteraotr;
    10. 	
    11. 	iterator begin()
    12. 	{
    13. 		//找最左节点
    14. 		Node* left = _root;
    15. 		while (left && left->_left)
    16. 		{
    17. 			left = left->_left;
    18. 		}
    19. 		//用一个节点构造迭代器
    20. 		return iterator(left);
    21. 	}
    22.  
    23. 	iterator end()
    24. 	{
    25. 		//因为没有哨兵节点，直接使用空进行返回
    26. 		return iterator(nullptr);
    27. 	}
    28. pairbool>  Insert(const T& data)
    29. {
    30. 	KeyOfvalue kovalue;
    31. 	if (!_root)
    32. 	{
    33. 		_root = new Node(data);
    34. 		_root->_col = BLACK;
    35. 		return make_pair(iterator(_root),true);
    36. 	}
    37. 	Node* parent = nullptr;
    38. 	Node* cur = _root;
    39. 	//找插入的位置
    40. 	while (cur)
    41. 	{
    42. 		if (kovalue(cur->_data) > kovalue(data))
    43. 		{
    44. 			parent = cur;
    45. 			cur = cur->_left;
    46. 		}
    47. 		else if (kovalue(cur->_data) < kovalue(data))
    48. 		{
    49. 			parent = cur;
    50. 			cur = cur->_right;
    51. 		}
    52. 		else
    53. 		{
    54. 			return make_pair(iterator(cur),false);
    55. 		}
    56. 	}
    57. 	cur = new Node(data);
    58. 	//插入成功，返回新增节点 
    59. 	//注意：cur 可能会改变(情况1变色处理,cur指向可能会改变)
    60. 	//使用newnode记录新创建节点的地址
    61. 	Node* newnode = cur;
    62.  
    63. 	if (kovalue(parent->_data) > kovalue(data))
    64. 	{
    65. 		parent->_left = cur;
    66. 	}
    67. 	else
    68. 	{
    69. 		parent->_right = cur;
    70. 	}
    71. 	cur->_parent = parent;
    72. 	while (parent && parent->_col == RED)
    73. 	{
    74. 		Node* grandfater = parent->_parent;
    75. 		assert(grandfater);
    76. 		assert(grandfater->_col == BLACK);
    77. 		if (grandfater->_left == parent)
    78. 		{
    79. 			Node* uncle = grandfater->_right;
    80. 			if (uncle && uncle->_col == RED)
    81. 			{
    82. 				parent->_col = uncle->_col = BLACK;
    83. 				grandfater->_col = RED;
    84. 				cur = grandfater;
    85. 				parent = cur->_parent;
    86. 			}
    87. 			else
    88. 			{
    89. 				if (cur == parent->_left)
    90. 				{
    91. 					RotateR(grandfater);
    92. 					parent->_col = BLACK;
    93. 					grandfater->_col = RED;
    94. 				}
    95. 				else
    96. 				{
    97. 					RotateL(parent);
    98. 					RotateR(grandfater);
    99. 					cur->_col = BLACK;
    100. 					grandfater->_col = RED;
    101. 				}
    102. 				break;
    103. 			}
    104. 		}
    105. 		else
    106. 		{
    107. 			Node* uncle = grandfater->_left;
    108. 			if (uncle && uncle->_col == RED)
    109. 			{
    110. 				parent->_col = uncle->_col = BLACK;
    111. 				grandfater->_col = RED;
    112. 				cur = grandfater;
    113. 				parent = cur->_parent;
    114. 			}
    115. 			else
    116. 			{
    117. 				if (cur == parent->_right)
    118. 				{
    119. 					RotateL(grandfater);
    120. 					parent->_col = BLACK;
    121. 					grandfater->_col = RED;
    122. 				}
    123. 				else
    124. 				{
    125. 					RotateR(parent);
    126. 					RotateL(grandfater);
    127. 					cur->_col = BLACK;
    128. 					grandfater->_col = RED;
    129. 				}
    130. 				break;
    131. 			}
    132. 		}
    133. 	}
    134. 	_root->_col = BLACK;
    135. 	return make_pair(iterator(newnode), true);
    136. }
    137. };

     

  • 相关阅读:
    buuctf crypto 【rsa2】解题记录
    十、为影院添加影片及座位安排《仿淘票票系统前后端完全制作（除支付外）》
    java8到java17的主要新增语法特性
    GDPU unity游戏开发 碰撞体与关节
    如何在Ubuntu上安装WordPress
    校招社招，职业性格测评已日渐成为主流
    DevOps 如何解决技术债务问题
    图解LeetCode——1773. 统计匹配检索规则的物品数量（难度：简单）
    重复控制器的性能优化
    【Mac】记录一次Mac配置Maven无效的经历：zsh: operation not permitted: mvn
  • 原文地址：https://blog.csdn.net/Brant_zero/article/details/128021366