红黑树模拟封装map和set

                               

         杀马特主页：羑悻的小杀马特.-CSDN博客         

 ------ ->欢迎阅读             欢迎阅读                       欢迎阅读                   欢迎阅读 <-------         

目录

前言：

一·红黑树的修改：

1.1iterator的实现：

1.1.1operator前置++的实现：

1.1.2operator前置--的实现： 

 1.1.3有关重载前置++和前置--技巧总结：

1.2BRtree的修改实现：

1.2.1RBtree类内begin()和end()构建：

1.2.2RBtree类内insert和find的修改：

二·封装RBtree： 

2.1封装成set：

2.1.1基本框架：

 2.1.2成员函数：

2.1.3测试接口函数： 

2.2封装成map：

2.2.1基本框架：

2.2.2成员函数：

2.2.3测试接口函数： 

 三.源码：

3.1 RBT.h：

3.2  my_set.h：

3.3 my_map.h：

3.4 test.cpp：

前言：

由于map和set的底层是红黑树实现的，只不过是放入的数据一个是pair类型一个是Key类型，故这里我们利用红黑树这个模版给它简略实例化出map和set。

一·红黑树的修改：

先透露一下这里我们的修改操作其实和hash的封装那里相类似，只不过这里相当于hash的封装相当于更简单一些，比如没有那些细节问题的处理，总的来说就是迭代器这里的操作处理好，然后根据传递的类型对之前写的红黑树的插入查找的数据类型更改一下（比如把data转化成key比较等），相当于我们接下来的重点就放在了iterator的实现了，也就是它的++和--了（然后就是库里面实现的用了一个哨兵位分别指向树的最左和最右来充当end()，我们这里直接用nullptr充当）。

1.1iterator的实现：

下面先把iterator这个类的总体框架创建出：

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

	Node *_node;
	Node* _root;//这里也可=以传红黑树类的对象指针，但是这里面就一个节点的指针，倒不如直接创建这个Node*的指针，然后传递的时候就是
	              //rbtree的_root就行。

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

1.1.1operator前置++的实现：

首先我们知道对于map和set它是去重+有序的，故当这两个容器调用这个封装的红黑树肯定走的是它的中序遍历，然后我们就把当前位置的节点指针去找它走中序的下一个，先假设是当前局部子树的根节点，然后它就是要访问它的右子树：分两种情况：

1.右子树存在，那么迭代器就去右子树的最左边的那个节点处。

2.右子树不存在，这里我们如果假设当前这个节点被连的属于树的右端树，那么我们要知道此时根节点已经访问完了，然后往上去找如果还是右树就一直这样，故当我们发现它是左子树的话，相当于访问完了左子树往上找根节点继续访问，故此时成立的就是孩子是父亲左的祖先。

然后最后我们到了50这个位置处的节点后再++，就相当于找不到下一个了，也就是总数根节点的parent指针就是nullptr，因此后面我们把end()设计成nullptr。 

	Self operator++()//前置++
	{
		if (_node->_right) {
			//右支的最左边:
			Node* most_left_node = _node->_right;
			while (most_left_node->_left) {
				most_left_node = most_left_node->_left;
			}
			_node = most_left_node;
		}



	
		else {
			//找孩子是父亲左的祖先;
			Node* parent = _node->_parent;
			Node* cur= _node;
			while (parent && parent->_right==cur) {
				cur = parent;
				parent =cur->_parent;
			}
			_node = parent;

		}
		return *this;
}

1.1.2operator前置--的实现： 

这里我们还是分情况，只是比上面多了一种也就是如果我们的 当前迭代器是end()位置（里面的_node也就相当于是nullptr），那么此时我们只需要让迭代器跳到树的最右叶子即可，也许会说如果当前位置是树的最左叶子呢？这里不用考虑后面左为空的情况包含了。

下面分为两种情况（因为我们一开始是把当前节点当成根看待，如果--就相当于把它变成当前节点的上一个节点也就是左子树的最后一个节点，如果左子树不存在也就是向上找它为右子树的那个根节点）：

1·当前_node是空，那么就去从整颗树的root遍历找到最右叶子进行赋值即可。

2.当前不是空：2.1左子树不为空：就去访问它左子树的最右叶子进行赋值即可。

                         2.2左子树为空：就去找孩子的父亲的右的那个祖先（这里根上面++一样只不过做一下调整，就不解释原因了）。

Self operator--()//前置--
{
	if (_node == nullptr) {//也就是end（）:这里我们假设end()是空指针来构建；但是库里面搞了个头指针
		//分别指向mostleft和mostright
		Node* tree_most_rightnode= _root;
		while (tree_most_rightnode && tree_most_rightnode->_right)
		{
			tree_most_rightnode = tree_most_rightnode->_right;
		}
		_node = tree_most_rightnode;
	}
	else {

		if (_node->_left) {
			//左支的最右边:
			Node* most_right_node = _node->_left;
			while (most_right_node->_right) {
				most_right_node = most_right_node->_right;
			}
			_node = most_right_node;
		}

		else {
			//找孩子是父亲右的祖先;
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && parent->_left == cur) {
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;

		}
	}
	return *this;
}

后面就是一些简单的重载了，这里我们就不做解释了：

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

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

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

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

 1.1.3有关重载前置++和前置--技巧总结：

首先就是把当前节点当初此处的根看待：

前置++：要访问此前根的右子树，右子树存在找最左，不存在把当前树当成左子树去找其根：孩子是父亲左的那个祖先。

前置--：要访问当前的左子树，左子树存在找最右，不存在把当前树当成右子树去找根：孩子是父亲右的那个祖先。

1.2BRtree的修改实现：

下面是大致的框架，外加实现了拷贝构造析构等。

这里我们写了拷贝构造就相当于写了构造，编译器就不会自己生成了，此时我们就需要写构造了，

但是我们这个构造只是要完成一个初始化就可以，因此内容和初始化列表可以不写，直接让它走缺省值即可，这里可以后面=default或者直接加{}正常空就行，为了让编译器知道我们有构造，它就会根据缺省值完成初始化。

否则报错信息：

RBtree框架： 

template<class K,class T,class getkoft>//这里的k是经过getkoft从T中得到的k
class RBTree {
	using Node = RBTreeNode<T>;
public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
RBTree() = default;//这里是由于拷贝构造写了，编译器不会再次生成默认构造函数，无构造报错，这里default一下相当于告诉编译器有构造了
//（这里因为缺省参数，这个构造其实没用的）
RBTree(const RBTree& t)
{
	_root = Copy(t._root);
}
RBTree& operator=(RBTree t)
{
	swap(_root, t._root);//被赋值后原对象变空了
	return *this;
}
~RBTree()
{
	Destroy(_root);
	_root = nullptr;
}
	Node* _root = nullptr;

};

1.2.1RBtree类内begin()和end()构建：

把begin（）初始化封装成树的最左节点，而end（）封装的是nullptr；最后套用下const和非const的迭代器实例化即可。

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

	return Iterator(cur, _root);
}

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

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

	return ConstIterator(cur, _root);
}

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

1.2.2RBtree类内insert和find的修改：

修改原则：对于T可能是pair也可能是Key，故需要仿函数去取出它真实的Key，来进行相关比较操作，其次就是返回类型，对应修改成pair以及迭代器类型，适做修改。

//修改：把相关kv的first按规则替换：
pair < Iterator, bool > insert(const T& data) {//先按照avl树插入节点，然后最后判断是否旋转来修改颜色
	//第一次插入要保证根节点为黑色：
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;

		 return { Iterator(nullptr, _root), true };;
	}
	Node* parent = nullptr;
	Node* cur = _root;
	getkoft gkot;
	while (cur)
	{
		if (gkot(cur->_data) < gkot(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (gkot(cur->_data) > gkot(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return { Iterator(cur, _root), false };
		}
	}

	cur = new Node(data);
	cur->_col = RED;
	if (gkot(cur->_data) >gkot(parent->_data))
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}

	cur->_parent = parent;

	//调整颜色等：(关键看叔叔)：
	while (parent && parent->_col == RED) {//父亲为黑色则不用再次向上调整
		Node* grandfather = parent->_parent;//爷爷节点一定存在（当父亲节点为红）一定为黑：要么继续调整要么为根节点最后改黑
		//下面分两种大情况分别是父亲为爷爷的left和right：
		if (parent == grandfather->_left) {//孩子插入后左高
			///关键看叔叔节点的情况：
			//叔叔存在且为红：
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED) {
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理:
				cur = grandfather;
				parent = cur->_parent;
			}
			//叔叔不存在或者为黑;
			else {
				//又分两种情况：孩子插入的是左还是右：
				if (cur == parent->_left) {
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else {
					RotateLR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
			}
		}
		else {//孩子插入后右高
			//叔叔存在且为红：
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED) {
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				// 继续往上处理:
				cur = grandfather;
				parent = cur->_parent;
			}
			//叔叔不存在或者为黑;
			else {
				//又分两种情况：孩子插入的是左还是右：
				if (cur == parent->_right) {
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else {
					RotateRL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
			}
		}
	}
	_root->_col = BLACK;//如果到头爷爷原来是黑的被改成了红且是根节点故改回黑
	return { Iterator(cur, _root), true };

}

Iterator Find(const K& key)
{
	getkoft gkot;
	Node* cur = _root;
	while (cur)
	{
		if (gkot(cur->_data) < key)
		{
			cur = cur->_right;
		}
		else if (gkot(cur->_data) >key)
		{
			cur = cur->_left;
		}
		else
		{
			return  Iterator(cur, _root);
		}
	}

	return End();
}

其他的就跟之前创建的RBtree大致相同，故直接cv即可。

二·封装RBtree： 

主要完成容器对应的迭代器操作和基本的插入查找操作，后面的封装类似哈希封装成的unordered_map,set类似（本质区别就在于map和set利用红黑树完成的有序操作），

2.1封装成set：

2.1.1基本框架：

template<class K>
class set
{
	struct set_getkoft
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};

public:
	typedef typename RBTree<K, const K, set_getkoft>::Iterator iterator;
	typedef typename RBTree<K, const K, set_getkoft >::ConstIterator const_iterator;
private:
	RBTree<K, const K, set_getkoft> _t;
};

 2.1.2成员函数：

这里成员函数直接调用RBtree中的即可，这里就不再进行解析了。

直接展示：

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

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

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

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

pair<iterator, bool> insert(const K& key)
{
	return _t.insert(key);
}
iterator Find(const K& key) {
	return _t.Find(key);
}

2.1.3测试接口函数： 

2.2封装成map：

2.2.1基本框架：

template<class K, class V>
class map
{
	struct  map_getkoft
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};

public:
	typedef typename RBTree<K, pair<const K, V>, map_getkoft>::Iterator iterator;
	typedef typename RBTree<K, pair<const K, V>, map_getkoft>::ConstIterator const_iterator;
private:
	RBTree<K, pair<const K, V>, map_getkoft> _t;
};

2.2.2成员函数：

map这里的成员函数只不过比set多了一个operator[ ];其他都一样就是调用红黑树的成员函数就可。

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

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

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

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

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

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

2.2.3测试接口函数： 

 三.源码：

下面展示一下相关原码：

3.1 RBT.h：

#pragma once
#pragma once
#include<iostream>
using namespace std;
enum Colour
{
	RED,
	BLACK
};

template<class T>
struct RBTreeNode
{
	T _data;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Colour _col;

	RBTreeNode(const T& data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
	{}
};

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

	Node *_node;
	Node* _root;//这里也可=以传红黑树类的对象指针，但是这里面就一个节点的指针，倒不如直接创建这个Node*的指针，然后传递的时候就是
	              //rbtree的_root就行。

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

	Self operator++()//前置++
	{
		if (_node->_right) {
			//右支的最左边:
			Node* most_left_node = _node->_right;
			while (most_left_node->_left) {
				most_left_node = most_left_node->_left;
			}
			_node = most_left_node;
		}



	
		else {
			//找孩子是父亲左的祖先;
			Node* parent = _node->_parent;
			Node* cur= _node;
			while (parent && parent->_right==cur) {
				cur = parent;
				parent =cur->_parent;
			}
			_node = parent;

		}
		return *this;
}

	Self operator--()//前置--
	{
		if (_node == nullptr) {//也就是end（）:这里我们假设end()是空指针来构建；但是库里面搞了个头指针
			//分别指向mostleft和mostright
			Node* tree_most_rightnode= _root;
			while (tree_most_rightnode && tree_most_rightnode->_right)
			{
				tree_most_rightnode = tree_most_rightnode->_right;
			}
			_node = tree_most_rightnode;
		}
		else {

			if (_node->_left) {
				//左支的最右边:
				Node* most_right_node = _node->_left;
				while (most_right_node->_right) {
					most_right_node = most_right_node->_right;
				}
				_node = most_right_node;
			}

			else {
				//找孩子是父亲右的祖先;
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && parent->_left == cur) {
					cur = parent;
					parent = cur->_parent;
				}
				_node = parent;

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

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

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

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

};
template<class K,class T,class getkoft>//这里的k是经过getkoft从T中得到的k
class RBTree {
	using Node = RBTreeNode<T>;
public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
	//构造拷贝构造析构：

	RBTree() = default;//这里是由于拷贝构造写了，编译器不会再次生成默认构造函数，无构造报错，这里default一下相当于告诉编译器有构造了
	//（这里因为缺省参数，这个构造其实没用的）
	RBTree(const RBTree& t)
	{
		_root = Copy(t._root);
	}
	RBTree& operator=(RBTree t)
	{
		swap(_root, t._root);//被赋值后原对象变空了
		return *this;
	}
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}


	//begin和end的创建：

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

		return Iterator(cur, _root);
	}

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

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

		return ConstIterator(cur, _root);
	}

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


	//修改：把相关kv的first按规则替换：
	pair < Iterator, bool > insert(const T& data) {//先按照avl树插入节点，然后最后判断是否旋转来修改颜色
		//第一次插入要保证根节点为黑色：
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;

			 return { Iterator(nullptr, _root), true };;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		getkoft gkot;
		while (cur)
		{
			if (gkot(cur->_data) < gkot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (gkot(cur->_data) > gkot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return { Iterator(cur, _root), false };
			}
		}

		cur = new Node(data);
		cur->_col = RED;
		if (gkot(cur->_data) >gkot(parent->_data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		//调整颜色等：(关键看叔叔)：
		while (parent && parent->_col == RED) {//父亲为黑色则不用再次向上调整
			Node* grandfather = parent->_parent;//爷爷节点一定存在（当父亲节点为红）一定为黑：要么继续调整要么为根节点最后改黑
			//下面分两种大情况分别是父亲为爷爷的left和right：
			if (parent == grandfather->_left) {//孩子插入后左高
				///关键看叔叔节点的情况：
				//叔叔存在且为红：
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED) {
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理:
					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔不存在或者为黑;
				else {
					//又分两种情况：孩子插入的是左还是右：
					if (cur == parent->_left) {
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else {
						RotateLR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
				}
			}
			else {//孩子插入后右高
				//叔叔存在且为红：
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED) {
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					// 继续往上处理:
					cur = grandfather;
					parent = cur->_parent;
				}
				//叔叔不存在或者为黑;
				else {
					//又分两种情况：孩子插入的是左还是右：
					if (cur == parent->_right) {
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else {
						RotateRL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
				}
			}
		}
		_root->_col = BLACK;//如果到头爷爷原来是黑的被改成了红且是根节点故改回黑
		return { Iterator(cur, _root), true };

	}

	Iterator Find(const K& key)
	{
		getkoft gkot;
		Node* cur = _root;
		while (cur)
		{
			if (gkot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (gkot(cur->_data) >key)
			{
				cur = cur->_left;
			}
			else
			{
				return  Iterator(cur, _root);
			}
		}

		return End();
	}

	bool is_rbtree() {
		int count = 0;
		if (_root == nullptr) return true;
		if (_root->_col == RED) return false;//根节点存在就为黑
		Node* cur = _root;
		while (cur) {
			if (cur->_col == BLACK) count++;
			cur = cur->_left;
		}
		return check(_root, count, 0);
	}

	int treeheight() {
		return _treeheight(_root);
	}
	int size() {
		return _size(_root);
	}
	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

private:


	void RotateL(Node* parent) {//左旋
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		//处理sublr：
		parent->_right = subrl;
		if (subrl) subrl->_parent = parent;//sublr为空不能访问

		Node* pp = parent->_parent;//保存parent的父节点指针
		//调节新旧“parent”位置：
		subr->_left = parent;
		parent->_parent = subr;

		if (pp == nullptr) {
			_root = subr;
			subr->_parent = nullptr;
		}
		else {
			if (parent == pp->_left) pp->_left = subr;
			else pp->_right = subr;
			subr->_parent = pp;
		}


	}


	void RotateR(Node* parent) {//右旋
		Node* subl = parent->_left;
		Node* sublr = subl->_right;

		parent->_left = sublr;
		if (sublr) sublr->_parent = parent;

		Node* pp = parent->_parent;
		subl->_right = parent;
		parent->_parent = subl;
		if (pp == nullptr) {
			_root = subl;
			subl->_parent = nullptr;
		}
		else {
			if (parent == pp->_left) pp->_left = subl;
			else pp->_right = subl;
			subl->_parent = pp;
		}

	}

	void	RotateLR(Node* parent) {//左右双旋
		Node* subl = parent->_left;
		Node* sublr = subl->_right;
		RotateL(subl);
		RotateR(parent);

	}

	void RotateRL(Node* parent) {//右左双旋
		Node* subr = parent->_right;
		Node* subrl = subr->_left;
		RotateR(subr);
		RotateL(parent);

	}
	bool check(Node* root, int reference, int blackcount) {//查找树中要满足黑色相同以及红的节点只能连两个黑的（转化成红的节点父亲不能是红的）：这里只有都满足才返回true，故可以判断错就返false

		if (root == nullptr) {//检查每条支路黑色节点数量相同
			if (blackcount != reference) {
				cout << "发现黑色节点不等的支路" << endl;
				return false;
			}
			else return true;

		}
		if (root->_col == RED && root->_parent->_col == RED) {
			cout << "发现连续的红色节点" << endl;//不能有连续的红色节点
			return false;
		}

		if (root->_col == BLACK) blackcount++;
		return check(root->_left, reference, blackcount) && check(root->_right, reference, blackcount);
	}


	int _treeheight(Node* root) {
		if (root == nullptr)  return 0;
		int leftheight = _treeheight(root->_left);
		int rightheight = _treeheight(root->_right);
		return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
	}
	int _size(Node* root) {
		if (root == nullptr) return 0;
		return _size(root->_left) + _size(root->_right) + 1;
	}

	//前序插入中序遍历后序销毁：
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newRoot = new Node(root->_kv);
		newRoot->_left = Copy(root->_left);
		newRoot->_right = Copy(root->_right);
		return newRoot;
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
	Node* _root = nullptr;

};

3.2  my_set.h：

#pragma once
#include"RBT.h"
namespace set_map {
	template<class K>
	class set
	{
		struct set_getkoft
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		typedef typename RBTree<K, const K, set_getkoft>::Iterator iterator;
		typedef typename RBTree<K, const K, set_getkoft >::ConstIterator const_iterator;


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

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

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

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

		pair<iterator, bool> insert(const K& key)
		{
			return _t.insert(key);
		}
		iterator Find(const K& key) {
			return _t.Find(key);
		}
	private:
		RBTree<K, const K, set_getkoft> _t;
	};
}

3.3 my_map.h：

#pragma once
#include"RBT.h"
namespace set_map {
	template<class K, class V>
	class map
	{
		struct  map_getkoft
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		typedef typename RBTree<K, pair<const K, V>, map_getkoft>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, map_getkoft>::ConstIterator const_iterator;

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

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

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

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

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

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

3.4 test.cpp：

#include"my_map.h"
#include"my_set.h"//这里由于我们在这两个头文件前面加了#pragma once，这样就不会重复包含了
using namespace set_map;
void Print(const  set_map::set<int>& s)
{
	set_map ::set<int>::const_iterator it = s.end();
	while (it != s.begin())
	{
		--it;
		cout << *it << " ";
	}
	cout  << endl;
	
	set_map::set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;

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

void set_test() {
	cout << "set相关测试用例：" << endl ;
	set_map:: set<int> s;
	s.insert(5);
	s.insert(2);
	s.insert(3);
	s.insert(1);
	s.insert(6);
	Print(s);
	cout << "查找结果:" << *(s.Find(3))<< endl;
}

void map_test() {
	cout << "map相关测试用例：" << endl ;
	map<string, string> dict;
	dict.insert({ "sort", "排序" });
	dict.insert({ "字符串", "string" });

	dict.insert({ "sort", "排序" });
	dict.insert({ "left", "左边" });
	dict.insert({ "right", "右边" });

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

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

	map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		// 不能修改first，可以修改second
		it->second += " + second";
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << "查找结果:"<<(dict.Find("left")->second) << endl;
	cout << endl;
}
int main() {
	//set_test();
	map_test();
	return 0;
}

结言：此篇讲述封装红黑树过程，其中有大部分处理和哈希的封装相似，上篇已经讲述过了，此篇就不在多言，到此望有助。