当前位置: 首页 > article >正文

封装红黑树实现mymap和myset

前面我们已经了解过红黑树如何实现,和map与set的基本用法;要继续深入了解map,set中的库函数的用法,与细节那么我们就可以试着简单用语言封装模拟实现一下map与set; 这里就分享一下我的思路;

若没了解过红黑树如何实现,和map与set的基本用法建议先去了解一下哦;我之前的文章中就有。

源码及框架分析

这里参考的是SGI-STL30版本源代码,map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个个头文件中

通过看SGI的源代码我们可以发现,map和set是利用的同一个红黑树stl_tree.h,但它们的value参数根本不同,如何实现呢?

  1. 通过下图对框架的分析,我们可以看到源码中rb_tree用了⼀个巧妙的泛型思想实现,rb_tree无论是实现key的搜索场景,还是key/value的搜索场景不是直接写死的,二是由第二个模板参数Value决定_rb_tree_node中存储的数据类型。
  2. set实例化rb_tree时第二个模板参数给的是key,map实例化rb_tree时第二个模板参数给的是pair<const key, T>,这样一颗红黑树既可以实现key搜索场景的set,也可以实现key/value搜索场景的map。
  • 这样写,解释了为什么set map利用的红黑树的value 根部不同但是却能使用同一个红黑树的原因

简化的源代码展示:

  1. 要注意⼀下,源码里面模板参数是用T代表value,而内部写的value_type不是我们我们日常key/value场景中说的value(不是关键字,内部值的意思),源码中的value_type反而是红黑树结点中存储的真实的数据的类型(参考上图 __rb_tree_node 参数和map的 模板参数T)
  2. rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型,为什么还要传第一个模板参数Key呢?尤其是set,两个模板参数是一样的,这是很多同学这时的一个疑问。要注意的是对于map和set,find/erase时的函数参数都是Key(所以,也不能说加上这个key是冗余的),所以第一个模板参数是传给find/erase等函数做形参的类型的。对于set而言两个参数是⼀样的,但是对于map而言就完全不一样了,map insert的是pair对象,但是find和ease的是Key对象。

也可以这样说,set加模板参数key,是多余的;但是为了代码可读性,与map同用一个红黑树,set才加上了模板参数key

吐槽⼀下,这里源码命名风格比较乱,set模板参数用的Key命名,map用的是Key和T命名,而rb_tree用的又是Key和Value,可见⼤佬有时写代码也不规范。

模拟实现map和set

实现步骤大致如下:

  1. 实现红黑树
  2. 封装map和set框架,解决KeyOfT
  3. iterator
  4. const_iterator
  5. key不支持修改的问题
  6. operator[]

 实现出复用红黑树的框架,并支持insert

  1. 参考源码框架,map和set复用之前我们实现的红黑树(忘记的的可以看完之前红黑树文章复习一下哦~)
  2. 这里相比源码调整⼀下,key参数就用K,value参数就用V,红黑树中的数据类型,我们使用T。
  3. 其次因为RBTree实现了泛型不知道T参数导致是K,还是pair<K, V>,那么insert内部进行插入逻辑比较时,就没办法进行比较,因为pair的默认支持的是key和value一起参与比较,我们需要时的任何时候只比较key,

所以我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT,然后RBTree中通过KeyOfT仿函数取出T类型对象中的key,再进行比较。

自己实现的:

  1. 具体细节参考如下代码实现
     
//MYset.H

#include"RBTree.h"

namespace xryq {
	template<class K>
	class set
	{

		struct KeyofV
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		/*typedef RBTreeNode<K, K> rbt;*/

		pair<iterator, bool> Insert(const K& k)
		{
			return _t.Insert(k);
		}


	private:
		RBTree<K, K, KeyofV> _t;
	};

}
MYmap.h
#include"RBTree.h"

namespace xryq 
{
	template<class K, class V>
	class map
	{
		struct KeyofV 
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		  
	public:
		//typedef RBTree<K, pair<K, V>, KeyOfV> rbt;

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

	private:
		RBTree<K, pair<const K, V>, KeyofV> _t;
	};

}
#pragma once

using namespace std;
// 枚举值表⽰颜⾊
enum Color {
	Red,
	Black
};

// 这⾥我们默认按key/value结构实现
template<class V>
struct RBTreeNode {

	// 这⾥更新控制平衡也要加⼊parent指针
	Color _col;
	V _kv;
	RBTreeNode<V>* _right;
	RBTreeNode<V>* _left;
	RBTreeNode<V>* _parent;

	RBTreeNode(V kv)
		:_kv(kv)
		, _right(nullptr)
		, _left(nullptr)
		, _parent(nullptr)
	{}
};


template<class K, class V, class KeyOfValue>
class RBTree {
	typedef RBTreeNode<V> Node;
public:


	bool Insert(V value)
	{
		if (_root == nullptr)
		{
			_root = new Node(value);
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfValue kot;

		while (cur)
		{
			if (kot(cur->_kv) > kot(value))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_kv) < kot(value))
			{
				parent = cur;
				cur = cur->_right;
			}
			else {
				return false;
			}
		}


		cur = new Node(value);
		//需要记录,要返回插入的迭代器;cur在之后会变
		Node* newnode = cur;
		cur->_col = Red;
		if (kot(cur->_kv) > kot(parent->_kv))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		// 父亲是红色,出现连续的红色节点,需要处理
		while (parent && parent->_col == Red)
		{
			Node* grandfather = parent->_parent;
			//   g
			// p   u
			if (grandfather->_left == parent)
			{
				//   g
				// p   u
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == Red)
				{
					//改色
					parent->_col = Black;
					uncle->_col = Black;
					grandfather->_col = Red;

					//循环
					cur = grandfather;
					parent = cur->_parent;

				}
				else
				{
					if (cur == parent->_left)
					{
						//     g
						//   p    u
						// c
						RotateR(grandfather);

						parent->_col = Black;
						grandfather->_col = Red;
					}
					else if (cur == parent->_right)
					{
						//      g
						//   p    u
						//     c
						RotateL(parent);
						RotateR(grandfather);

						parent->_col = Black;
						grandfather->_col = Red;
					}

					//这种情况 p 是直接是黑 肯定是已经满足要求了
					break;
				}
			}
			else if (grandfather->_right == cur->_parent)
			{
				//   g
				// u   p
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == Red)
				{
					//改色
					parent->_col = Black;
					uncle->_col = Black;
					grandfather->_col = Red;

					//循环
					cur = grandfather;
					parent = cur->_parent;

				}
				else
				{
					if (cur == parent->_right)
					{
						//     g
						//   u    p
						//          c
						RotateL(grandfather);

						parent->_col = Black;
						grandfather->_col = Red;
					}
					else if (cur == parent->_left)
					{
						//      g
						//   u     p
						//       c
						RotateR(parent);
						RotateL(grandfather);

						cur->_col = Black;
						grandfather->_col = Red;
					}

					//_root->_col = Black;
					//这种情况 p 是直接是黑 肯定是已经满足要求了
					break;
				}
			}

		}
		_root->_col = Black;
		return true;
	}

	void RotateL(Node* grand)
	{
		Node* subR = grand->_right;
		Node* subRL = subR->_left;
		Node* pparent = grand->_parent;

		if (grand == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else {
			//subR节点
			if (pparent->_left == grand)
			{
				pparent->_left = subR;
			}
			else {
				pparent->_right = subR;
			}
			subR->_parent = pparent;
		}


		//parent 节点
		subR->_left = grand;
		if (subRL)
			subRL->_parent = grand;
		grand->_right = subRL;
		grand->_parent = subR;
		//subR->_col = Black;
		//grand->_col = Red;
	}

	void RotateR(Node* grand)
	{
		Node* subL = grand->_left;
		Node* subLR = subL->_right;
		Node* pparent = grand->_parent;

		grand->_left = subLR;
		if (subLR)
			subLR->_parent = grand;

		//parent 节点
		subL->_right = grand;
		grand->_parent = subL;

		if (grand == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else {
			//subR节点
			if (pparent->_left == grand)
			{
				pparent->_left = subL;
			}
			else {
				pparent->_right = subL;
			}
			subL->_parent = pparent;
		}






		//subL->_col = Black;
		//grand->_col = Red;
	}


	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else {
				return cur;
			}
		}

		return nullptr;

	}
	//bool Check(Node* root, int blackNum, const int refNum)
	//{
	//	if (root == nullptr)
	//	{
	//		if (blackNum == refNum)
	//			return true;
	//		else
	//		{
	//			cout << "存在黑色结点的数量不相等的路径" << endl;
	//			return false;
	//		}

	//	}


	//	// 检查孩⼦不太⽅便,因为孩⼦有两个,且不⼀定存在,反过来检查⽗亲就⽅便多了
	//	if (root->_col == Red && root->_parent->_col == Red)
	//	{
	//		return false;
	//	}

	//	if (root->_col == Black)
	//	{
	//		blackNum++;
	//	}

	//	return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
	//}

	//bool IsBalance()
	//{
	//	//特殊情况不要忘记
	//	if (_root == nullptr)
	//	{
	//		return true;
	//	}

	//	if (_root->_col == Red)
	//	{
	//		return false;
	//	}

	//	// 参考值
	//	int refNum = 0;
	//	Node* cur = _root;
	//	while (cur)
	//	{
	//		if (cur->_col == Black)
	//		{
	//			refNum++;
	//		}
	//		cur = cur->_left;
	//	}

	//	return Check(_root, 0, refNum);
	//}

	//void InOrder()
	//{
	//	return _InOrder(_root);
	//	cout << endl;
	//}

	//int Height()
	//{
	//	return _Height(_root);
	//}
private:
	//void _InOrder(Node* root)
	//{
	//	if (root == nullptr)
	//	{
	//		return;
	//	}

	//	_InOrder(root->_left);
	//	cout << root->_kv.first << ":" << root->_kv.second << endl;
	//	_InOrder(root->_right);
	//}

	//int _Height(Node* root)
	//{
	//	if (root == nullptr)
	//		return 0;

	//	int HeightL = _Height(root->_left);
	//	int HeightR = _Height(root->_right);

	//	return HeightL > HeightR ? HeightL + 1 : HeightR + 1;
	//}

	Node* _root = nullptr;
};

支持iterator的实现

  • 在模拟实现map,set的iterator的时候,我建议大家可以回想,复习一下list的iterator是怎么实现的;如果一点都想不起来的话,我建议还是复习一下为好,因为这次实现的和list的模拟十分相似,而且我也不会在这多说细节~
  •  基本的方法都是:模板会自动实现所传的值;也就是模板会传自己所映射的值;

如果想复习的话可以参考我之前关于list模拟的文章哦! 

首先,大致看看源代码是如何实现的;

基本框架已经了解,那么这些重定义是怎么实现的?

iterator实现思路分析
 

  • iterator实现的大框架跟list的iterator思路是⼀致的,用一个类型封装结点的指针(iterator),再通过重载运算符实现,迭代器像指针一样访问的行为。
  • 这里的难点是operator++和operator--的实现。之前使用部分,我们分析了,map和set的迭代器走的是中序遍历,左子树->根结点->右子树,那么begin()会返回中序第一个结点的iterator也就是10所在结点的迭代器。

以这个图为例子分析:

  •  迭代器++的核新逻辑就是不看全局,只看局部,只考虑当前中序局部要访问的下⼀个结点
  • 迭代器++时,如果it指向的结点的右子树不为空,代表当前结点已经访问完了,要访问下⼀个结点是右子树的中序第一个,⼀棵树中序第一个是最左结点,所以直接找右子树的最左结点即可。
  • 迭代器++时,如果it指向的结点的右子树空,代表当前结点已经访问完了且当前结点所在的子树也访问完了,要访问的下一个结点在当前结点的祖先里面,所以要沿着当前结点到根的祖先路径向上找。

如果当前结点是父亲的左,根据中序左子树->根结点->右子树,那么下一个访问的结点就是当前结点的父亲;

如图:it指向25,25右为空,25是30的左,所以下⼀个访问的结点就是30。 

        

如果当前结点是父亲的右,根据中序左子树->根结点->右子树,当前当前结点所在的子树访问完了,当前结点所在父亲的子树也访问完了,那么下一个访问的需要继续往根的祖先中去找,直到找到孩子是父亲左的那个祖先就是中序要问题的下一个结点。也就是循环思想(也可以递归,不过太麻烦),直到找到合适的关系为止。

如图:it指向15,15右为空,15是10的右,15所在⼦树话访问完了,10所在⼦树也访问完了,继续往上找,10是18的左,那么下⼀个访问的结点就是18

  • 总结的来说就是,++是找比他正好大的值;所以先看右子树是不是为空;

若右子树不为空:找右子树的最左节点,也就是右子树的最小值;

若右子树为空:从cur当前节点找parent节点,若找到parent->left == cur (也就是当前节点是父节点的左节点)那么 ++结果就是parent;若没有找到parent->left == cur,继续cur = parent寻找合适的节点满足这个关系;

  • end()如何表示呢?

当it指向50时,++it时,50是40的右,40是30的右,30是18的右,18到根没有父亲,没有找到孩子是父亲左的那个祖先,这是父亲为空了,那我们就把it中的结点指针置为nullptr,我们用nullptr去充当end。

需要注意的是stl源码空,红黑树增加了⼀个哨兵位头结点做为end(),这哨兵位头结点和根互为父亲,左指向最左结点,右指向最右结点。

解释:

这段代码就是stl源码中实现的哨兵位;和头节点同为父子关系;虽然看着能解决节点为end --和 ++ 成为end的问题;但是你要想,这个node哨兵位的实现,虽然实现了node->right为begin,node为end;但是如何维护呢?当我删除和添加节点时需要维护这层关系,所以为了简便,我们这里还是用nullptr作为end()。

相比我们用nullptr作为end(),差别不大,他能实现的,我们也能实现。只是--end()判断到结点时空,特殊处理⼀下,让迭代器结点指向最右结点。具体参考下面代码的迭代器--实现部分。

  • 迭代器--的实现跟++的思路完全类似,逻辑正好反过来即可,因为他访问顺序是右子树->根结点->左子树,具体参考下面代码实现。
  • 总结的来说就是,--是找比他正好大的值;所以先看左子树是不是为空;

若左子树不为空:找左子树的最右节点,也就是右子树的最大值;

若左子树为空:从cur当前节点找parent节点,若找到parent->right == cur (也就是当前节点是父节点的右节点)那么 --结果就是parent;若没有找到parent->right == cur,继续cur = parent寻找合适的节点满足这个关系; 

  • 实现的相关细节 
  • set的iterator也不支持修改,我们把set的第二个模板参数改成const K即可, RBTree<K,const K, SetKeyOfT> _t;

(要注意 在重定义iterator时,会用到 RBTree<K,const K, SetKeyOfT> 这个类型模板,不要忘记加const 例如:typedef typename RBTree<K,const K, KeyofV>::Iterator iterator;)

否则会报错

  • map的iterator不支持修改key但是可以修改value,我们把map的第二个模板参数pair的第一个参数改成const K即可, RBTree<K, pair<const K, V>, MapKeyOfT> _t;
  • 支持完整的迭代器还有很多细节需要修改,具体参考下面的代码。
  • typename类型

map支持 [ ]

参考map的【】

  • map要支持[ ]主要需要修改insert返回值支持,修改RBtree中的insert返回值为pair<Iterator, bool> Insert(const T& data)
  • 有了insert⽀持[]实现就很简单了,具体参考下面代码实现
     


 

xyrq::map和xryq::set代码实现

Mymap.h

//Mymap.h

#pragma once
#include"RBTree.h"


namespace xryq 
{
	template<class K, class V>
	class map
	{
		struct KeyofV 
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		  
	public:
		//typedef RBTree<K, pair<K, V>, KeyOfV> rbt;
		typedef typename RBTree<K, pair<const K, V>, KeyofV>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, KeyofV>::ConstIterator const_iterator;

		pair<iterator, bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}

		iterator begin()
		{
			return _t.Begin();
		}

		iterator end()
		{
			return _t.End();
		}

		const_iterator begin() const
		{
			return _t.Begin();
		}

		const_iterator end() const
		{
			return _t.End();
		}

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert({ key, V() });
			return ret.first->second;
		}
	private:
		RBTree<K, pair<const K, V>, KeyofV> _t;
	};

}

Myset.h 

//Myset.h
#pragma once

#include"RBTree.h"

namespace xryq {
	template<class K>
	class set
	{

		struct KeyofV
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		/*typedef RBTreeNode<K, K> rbt;*/

		/*typedef typename RBTree<K, K, KeyofV>::Iterator iterator;*/
		typedef typename RBTree<K, K, KeyofV>::Iterator iterator;
		typedef typename RBTree<K,const K, KeyofV>::ConstIterator const_iterator;

		pair<iterator, bool> Insert(const K& k)
		{
			return _t.Insert(k);
		}

		iterator begin()
		{
			return _t.Begin();
		}

		iterator end()
		{
			return _t.End();
		}

		const_iterator begin() const
		{
			return _t.Begin();
		}

		const_iterator end() const
		{
			return _t.End();
		}
	private:
		RBTree<K,const K, KeyofV> _t;
	};

}

RBTree.h 

#pragma once

using namespace std;
// 枚举值表⽰颜⾊
enum Color {
	Red,
	Black
};

// 这⾥我们默认按key/value结构实现
template<class V>
struct RBTreeNode {

	// 这⾥更新控制平衡也要加⼊parent指针
	Color _col;
	V _kv;
	RBTreeNode<V>* _right;
	RBTreeNode<V>* _left;
	RBTreeNode<V>* _parent;

	RBTreeNode(V kv)
		:_kv(kv)
		, _right(nullptr)
		, _left(nullptr)
		, _parent(nullptr)
	{}
};

template<class V, class Ref, class Ptr>
struct RBTreeIterator {
	typedef RBTreeNode<V> Node;
	typedef RBTreeIterator<V, Ref, Ptr> Self;

	Node* _node;
	Node* _root;

	RBTreeIterator(Node* node, Node* root)
		:_node(node)
		, _root(root)
	{}

	Ref operator*()
	{
		return _node->_kv;
	}

	Ptr operator->()
	{
		return &(_node->_kv);
	}

	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}

	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}

	Self operator++()
	{

		if (_node->_right != nullptr)
		{

			// 右不为空,中序下一个访问的节点是右子树的最左(最小)节点
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			//返回self 级 *this ++ 是自身也要改变的;
			//self* ret = new self(cur);
			//return ret;

			_node = cur;
		}
		else
		{
			// 右为空,祖先里面孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_left != cur)
			{
				cur = cur->_parent;
				parent = cur->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	Self operator--()
	{
		// end() 的值;
		if (_node == nullptr)
		{
			//必须增加一个 root值,不如无法对 末迭代器 --
			Node* cur = _root;

			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
			return *this;
		}
		//左不为空  找左树的最大值, 左树的最右边
		if (_node->_left)
		{
			Node* cur = _node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			//左为空 找当前节点 是 父亲的右节点 的 父节点
			Node* cur = _node;
			Node* parent = cur._parent;

			while (parent->_right = cur)
			{
				cur = cur->_parent;
				parent = cur->_right;
			}

			_node = parent;
		}

		return *this;
	}

};

template<class K, class V, class KeyOfValue>
class RBTree {
	typedef RBTreeNode<V> Node;
public:
	typedef RBTreeIterator<V, V&, V*> Iterator;
	typedef RBTreeIterator<V, const V&, const V*> ConstIterator;

	Iterator Begin()
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}

		//Iterator it(cur, root);
		//return it;

		return Iterator(cur, _root);
	}

	Iterator End()
	{
		return Iterator(nullptr, _root);
	}

	ConstIterator Begin() const
	{
		Node* cur = _root;
		while (cur->_left)
		{
			cur = cur->_left;
		}

		//Iterator it(cur, root);
		//return it;

		return ConstIterator(cur, _root);
	}

	ConstIterator End() const
	{
		return ConstIterator(nullptr, _root);
	}

	pair<Iterator, bool> Insert(V value)
	{
		if (_root == nullptr)
		{
			_root = new Node(value);
			return { Iterator(_root, _root) ,true };
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfValue kot;

		while (cur)
		{
			if (kot(cur->_kv) > kot(value))
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(cur->_kv) < kot(value))
			{
				parent = cur;
				cur = cur->_right;
			}
			else {
				return { Iterator(cur,_root), false };
			}
		}


		cur = new Node(value);
		//需要记录,要返回插入的迭代器;cur在之后会变
		Node* newnode = cur;
		cur->_col = Red;
		if (kot(cur->_kv) > kot(parent->_kv))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		// 父亲是红色,出现连续的红色节点,需要处理
		while (parent && parent->_col == Red)
		{
			Node* grandfather = parent->_parent;
			//   g
			// p   u
			if (grandfather->_left == parent)
			{
				//   g
				// p   u
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == Red)
				{
					//改色
					parent->_col = Black;
					uncle->_col = Black;
					grandfather->_col = Red;

					//循环
					cur = grandfather;
					parent = cur->_parent;

				}
				else
				{
					if (cur == parent->_left)
					{
						//     g
						//   p    u
						// c
						RotateR(grandfather);

						parent->_col = Black;
						grandfather->_col = Red;
					}
					else if (cur == parent->_right)
					{
						//      g
						//   p    u
						//     c
						RotateL(parent);
						RotateR(grandfather);

						parent->_col = Black;
						grandfather->_col = Red;
					}

					//这种情况 p 是直接是黑 肯定是已经满足要求了
					break;
				}
			}
			else if (grandfather->_right == cur->_parent)
			{
				//   g
				// u   p
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == Red)
				{
					//改色
					parent->_col = Black;
					uncle->_col = Black;
					grandfather->_col = Red;

					//循环
					cur = grandfather;
					parent = cur->_parent;

				}
				else
				{
					if (cur == parent->_right)
					{
						//     g
						//   u    p
						//          c
						RotateL(grandfather);

						parent->_col = Black;
						grandfather->_col = Red;
					}
					else if (cur == parent->_left)
					{
						//      g
						//   u     p
						//       c
						RotateR(parent);
						RotateL(grandfather);

						cur->_col = Black;
						grandfather->_col = Red;
					}

					//_root->_col = Black;
					//这种情况 p 是直接是黑 肯定是已经满足要求了
					break;
				}
			}

		}
		_root->_col = Black;
		return make_pair(Iterator(newnode, _root), true );
	}

	void RotateL(Node* grand)
	{
		Node* subR = grand->_right;
		Node* subRL = subR->_left;
		Node* pparent = grand->_parent;

		if (grand == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else {
			//subR节点
			if (pparent->_left == grand)
			{
				pparent->_left = subR;
			}
			else {
				pparent->_right = subR;
			}
			subR->_parent = pparent;
		}


		//parent 节点
		subR->_left = grand;
		if (subRL)
			subRL->_parent = grand;
		grand->_right = subRL;
		grand->_parent = subR;
		//subR->_col = Black;
		//grand->_col = Red;
	}

	void RotateR(Node* grand)
	{
		Node* subL = grand->_left;
		Node* subLR = subL->_right;
		Node* pparent = grand->_parent;

		grand->_left = subLR;
		if (subLR)
			subLR->_parent = grand;

		//parent 节点
		subL->_right = grand;
		grand->_parent = subL;

		if (grand == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else {
			//subR节点
			if (pparent->_left == grand)
			{
				pparent->_left = subL;
			}
			else {
				pparent->_right = subL;
			}
			subL->_parent = pparent;
		}






		//subL->_col = Black;
		//grand->_col = Red;
	}


	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else {
				return cur;
			}
		}

		return nullptr;

	}
	//bool Check(Node* root, int blackNum, const int refNum)
	//{
	//	if (root == nullptr)
	//	{
	//		if (blackNum == refNum)
	//			return true;
	//		else
	//		{
	//			cout << "存在黑色结点的数量不相等的路径" << endl;
	//			return false;
	//		}

	//	}


	//	// 检查孩⼦不太⽅便,因为孩⼦有两个,且不⼀定存在,反过来检查⽗亲就⽅便多了
	//	if (root->_col == Red && root->_parent->_col == Red)
	//	{
	//		return false;
	//	}

	//	if (root->_col == Black)
	//	{
	//		blackNum++;
	//	}

	//	return Check(root->_left, blackNum, refNum) && Check(root->_right, blackNum, refNum);
	//}

	//bool IsBalance()
	//{
	//	//特殊情况不要忘记
	//	if (_root == nullptr)
	//	{
	//		return true;
	//	}

	//	if (_root->_col == Red)
	//	{
	//		return false;
	//	}

	//	// 参考值
	//	int refNum = 0;
	//	Node* cur = _root;
	//	while (cur)
	//	{
	//		if (cur->_col == Black)
	//		{
	//			refNum++;
	//		}
	//		cur = cur->_left;
	//	}

	//	return Check(_root, 0, refNum);
	//}

	//void InOrder()
	//{
	//	return _InOrder(_root);
	//	cout << endl;
	//}

	//int Height()
	//{
	//	return _Height(_root);
	//}
private:
	//void _InOrder(Node* root)
	//{
	//	if (root == nullptr)
	//	{
	//		return;
	//	}

	//	_InOrder(root->_left);
	//	cout << root->_kv.first << ":" << root->_kv.second << endl;
	//	_InOrder(root->_right);
	//}

	//int _Height(Node* root)
	//{
	//	if (root == nullptr)
	//		return 0;

	//	int HeightL = _Height(root->_left);
	//	int HeightR = _Height(root->_right);

	//	return HeightL > HeightR ? HeightL + 1 : HeightR + 1;
	//}

	Node* _root = nullptr;
};

 参考测试用例

void test1()
{
	xryq::set<int> s;
	s.Insert(5);
	s.Insert(1);
	s.Insert(3);
	s.Insert(2);
	s.Insert(6);

	xryq::set<int>::iterator sit = s.begin();
	*sit += 10;
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;

	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;
}

void test2()
{
	xryq::map<string, string> dict;
	dict.insert({ "sort", "排序" });
	dict.insert({ "left", "左边" });
	dict.insert({ "right", "右边" });

	dict["left"] = "左边,剩余";
	dict["insert"] = "插入";
	dict["string"];

	xryq::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		// 不能修改first,可以修改second
		//it->first += 'x';
		it->second += 'x';

		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;

	for (auto& kv : dict)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}

原文地址:https://blog.csdn.net/2302_80253411/article/details/143257161
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/373304.html

相关文章:

  • MySQL中的读锁与写锁:概念与作用深度剖析
  • 关于el-table翻页后序号列递增的组件封装
  • C语言练习(29)
  • FreeRTOS从入门到精通 第十四章(队列集)
  • 机器人基础深度学习基础
  • 51单片机开发:定时器中断
  • 大型语言模型的运行成本分析
  • Kubernetes:(四)kubectl命令
  • nmcli、ip、ifcfg配置网络区分方法
  • 完整了解asp.net core MVC中的数据传递
  • Android——静态注册广播
  • 【面试宝典】Java中创建线程池的几种方式以及区别
  • Vue前端开发:事件绑定方式
  • 一些CSS的基础知识点
  • 软件测试学习笔记丨Selenium学习笔记:css定位
  • 027_UIImage_in_Matlab图形界面开发中的图片
  • linux之网络子系统- 内核发送数据包流程以及相关实际问题
  • SpringBoot篇(监控)
  • HTML基本类型
  • 程序员转项目经理,我们必须掌握的3大核心要素
  • 一款专业获取 iOS 设备的 UDID 工具|一键获取iPhone iPad设备的 UDID
  • src漏洞挖掘#信息收集#网络安全
  • 前端性能优化全攻略:提升用户体验,加速页面加载
  • ArcGIS Pro SDK (十九)场景图层
  • Java已死,大模型才是未来?
  • 数据安全-接口数据混合加密笔记