【高阶数据结构】红黑树模拟实现map、set

红黑树模拟实现map、set

1.源码及框架分析
2.模拟实现map和set
- 1.支持 insert 的实现
- 2.支持 iterator 的实现
- 3.map支持 operator [] 的实现
3.总代码
- 1.RBTree.h
- 2.Myset.h
- 3.Mymap.h
- 4.Test.cpp

1.源码及框架分析

SGI-STL30版本源代码，map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等几个头文件中。map和set的实现结构框架核心部分截取出来如下：

// set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_set.h>
#include <stl_multiset.h>

// map
#ifndef __SGI_STL_INTERNAL_TREE_H
#include <stl_tree.h>
#endif
#include <stl_map.h>
#include <stl_multimap.h>

// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
	// typedefs:
	typedef Key key_type;
	typedef Key value_type;
private:
	typedef rb_tree<key_type, value_type,
		identity<value_type>, key_compare, Alloc> rep_type;
	rep_type t; // red-black tree representing set
};

// stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
	// typedefs:
	typedef Key key_type;
	typedef T mapped_type;
	typedef pair<const Key, T> value_type;
private:
	typedef rb_tree<key_type, value_type,
		select1st<value_type>, key_compare, Alloc> rep_type;
	rep_type t; // red-black tree representing map
};

// stl_tree.h
struct __rb_tree_node_base
{
	typedef __rb_tree_color_type color_type;
	typedef __rb_tree_node_base* base_ptr;
	color_type color;
	base_ptr parent;
	base_ptr left;
	base_ptr right;
};

// stl_tree.h
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc
	= alloc>
class rb_tree {
protected:
	typedef void* void_pointer;
	typedef __rb_tree_node_base* base_ptr;
	typedef __rb_tree_node<Value> rb_tree_node;
	typedef rb_tree_node* link_type;
	typedef Key key_type;
	typedef Value value_type;
public:
	// insert⽤的是第⼆个模板参数左形参 
	pair<iterator, bool> insert_unique(const value_type& x);

	// erase和find⽤第⼀个模板参数做形参 
	size_type erase(const key_type& x);
	iterator find(const key_type& x);
protected:
	size_type node_count; // keeps track of size of tree
	link_type header;
};

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
	typedef __rb_tree_node<Value>* link_type;
	Value value_field;
};

通过下图对框架的分析，我们可以看到源码中rb_tree用了一个巧妙的泛型思想实现，rb_tree是实现key的搜索场景，还是key/value的搜索场景不是直接写死的，而是由第⼆个模板参数Value决定_rb_tree_node中存储的数据类型。
set实例化rb_tree时第二个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是 pair<const key，T>，这样一颗红黑树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。
要注意⼀下，源码里面模板参数是用T代表value，而内部写的value_type不是我们我们日常key/value场景中说的value，源码中的value_type反而是红黑树结点中存储的真实的数据的类型。
rb_tree第⼆个模板参数Value已经控制了红黑树结点中存储的数据类型，为什么还要传第一个模板参数Key呢？尤其是set，两个模板参数是一样的。要注意的是对于map和set，find/erase时的函数参数都是Key，所以第一个模板参数是传给find/erase等函数做形参的类型的。对于set而言两个参数是一样的，但是对于map而言就完全不一样了，map insert的是pair对象，但是find和ease的是Key对象。
吐槽一下，这里源码命名风格比较乱，set模板参数用的Key命名，map用的是Key和T命名，而rb_tree用的又是Key和Value，可见大佬有时写代码也不规范。

在这里插入图片描述

2.模拟实现map和set

1.支持 insert 的实现

参考源码框架，map和set复用之前实现的红黑树。
这里相比源码调整一下，key参数就用K，value参数就用V，红黑树中的数据类型使用T。
其次因为RBTree实现了泛型不知道T参数，导致是K，还是pair<K，V>，那么insert内部进行插入逻辑比较时，就没办法进行比较，因为pair的默认支持的是key和value一起参与比较，我们需要时的任何时候只比较key，所以我们在map和set层分别实现一个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进行比较，具体细节参考如下代码实现。

//RBTree.h
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)
	{}
};

//KeyOfT：获取T中的Key，其中T是红黑树存储的数据
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK; //空树插入的节点必须是黑色

			return true;
		}

		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) < kot(data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (kot(cur->_data) > kot(data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(data);
		cur->_col = RED; //非空树插入的节点必须是红色
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		//链接父亲
		cur->_parent = parent;
	
		//变色、旋转逻辑...
		
		return true;
	}

	void RotateR(Node* parent)
	{
		//...
	}

	void RotateL(Node* parent)
	{
		//...
	}

private:
	Node* _root = nullptr;
};

//Myset.h
namespace xzy
{
	template<class K>
	class set
	{
		//仿函数用于插入时比较Key的大小
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}

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

//Mymap.h
namespace xzy
{
	template<class K, class V>
	class map
	{
		//仿函数用于插入时比较Key的大小
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

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

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

2.支持 iterator 的实现

源代码核心部分如下：

struct __rb_tree_base_iterator
{
	typedef __rb_tree_node_base::base_ptr base_ptr;
	base_ptr node;
	void increment()
	{
		if (node->right != 0) {
			node = node->right;
			while (node->left != 0)
				node = node->left;
		}
		else {
			base_ptr y = node->parent;
			while (node == y->right) {
				node = y;
				y = y->parent;
			}
			if (node->right != y)
				node = y;
		}
	}
	void decrement()
	{
		if (node->color == __rb_tree_red &&
			node->parent->parent == node)
			node = node->right;
		else if (node->left != 0) {
			base_ptr y = node->left;
			while (y->right != 0)
				y = y->right;
			node = y;
		}
		else {
			base_ptr y = node->parent;
			while (node == y->left) {
				node = y;
				y = y->parent;
			}
			node = y;
		}
	}
};

template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
	typedef Value value_type;
	typedef Ref reference;
	typedef Ptr pointer;
	typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
	__rb_tree_iterator() {}
	__rb_tree_iterator(link_type x) { node = x; }
	__rb_tree_iterator(const iterator& it) { node = it.node; }
	reference operator*() const { return link_type(node)->value_field; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
	pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
	self& operator++() { increment(); return *this; }
	self& operator--() { decrement(); return *this; }

	inline bool operator==(const __rb_tree_base_iterator& x,
		const __rb_tree_base_iterator& y) {
		return x.node == y.node;
	}
	inline bool operator!=(const __rb_tree_base_iterator& x,
		const __rb_tree_base_iterator& y) {
		return x.node != y.node;
	}
};

iterator实现思路分析：

iterator实现的大框架跟list的iterator思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为。
这里的难点是operator++和operator–的实现。map和set的迭代器走的是中序遍历，左子树->根->右子树，那么begin()会返回中序第一个结点的iterator也就是10所在结点的迭代器。
迭代器++的核心逻辑是不看全局，而是只看局部的，只考虑当前中序局部要访问的下一个结点。
迭代器++时，如果it指向的结点的右子树不为空，代表当前结点已经访问完了，要访问下⼀个结点是右子树的中序第一个，一棵树中序第一个是最左结点，所以直接找右子树的最左结点即可。如下图：it指向30，30右子树的最左结点是35，那么下一个访问的结点就是35。

在这里插入图片描述

迭代器++时，如果it指向的结点的右子树空，代表当前结点已经访问完了且当前结点所在的子树也
访问完了，要访问的下一个结点在当前结点的祖先里面，所以要沿着当前结点到根的祖先路径向上找。
如果当前结点是父亲的左，根据中序左子树->根->右子树，那么下一个访问的结点就是当前结点的父亲。如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。

在这里插入图片描述

如果当前结点是父亲的右，根据中序左子树->根->右子树，当前当前结点所在的子树访问完了，当前结点所在父亲的子树也访问完了，那么下一个访问的需要继续往根的祖先中去找，直到找到孩子是父亲左的那个祖先就是中序要问题的下一个结点。如下图：it指向15，15右为空，15是10的右，15所在子树话访问完了，10所在子树也访问完了，继续往上找，10是18的左，那么下一个访问的结点就是18。

在这里插入图片描述

end()如何表示呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有父亲，没有找到孩子是父亲左的那个祖先，这时父亲为空了，那我们就把it中的结点指针置为nullptr，我们用nullptr去充当end。需要注意的是stl源码中，红黑树增加了一个哨兵位头结点做为end()，这哨兵位头结点和根互为父亲，左指向最左结点，也就是begin()，右指向最右结点，也就是begin()。相比我们用nullptr作为end()，差别不大，哨兵位头结点能实现的，nullptr也能实现。只是–end()判断到结点时空，特殊处理一下，让迭代器结点指向最右结点。

在这里插入图片描述

迭代器–的实现跟++的思路完全类似，逻辑正好反过来即可，因为它访问顺序是右子树->根->左子树。
set的iterator不支持修改key，我们把set的第⼆个模板参数改成const K即可， RBTree<K, const K, SetKeyOfT> _t;
map的iterator不支持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第一个参数改成const K即可， RBTree<K, pair<const K, V>, MapKeyOfT> _t;
支持完整的迭代器还有很多细节需要修改，具体参考下面题的代码。

//RBTree.h
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>
class RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

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

	Self& operator++()
	{
		if (_node->_right)
		{
			//右不为空，中序下一个访问的节点是右子树的最左（最小）结点
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			_node = min;
		}
		else
		{
			//右为空，祖先里面孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		if (_node == nullptr)  // --end()
		{
			// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else if (_node->_left)
		{
			// 左子树不为空，中序左子树最后一个
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else
		{
			// 孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				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;
	}
	
private:
	Node* _node;
	Node* _root;
};

template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

	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);
	}
	
private:
	Node* _root = nullptr;
};

//Myset.h
namespace xzy
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		//取类中的类型需要加上typename，为了区分静态成员变量
		typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, const K, SetKeyOfT>::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();
		}

		bool insert(const K& key)
		{
			return _t.Insert(key);
		}

	private:
		RBTree<K, const K, SetKeyOfT> _t;
	};
}

//Mymap.h
namespace xzy
{
	template<class K, class V>
	class map
	{
		//仿函数用于插入时比较Key的大小
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		//取类中的类型需要加上typename，为了区分静态成员变量
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::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();
		}

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

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

3.map支持 operator [] 的实现

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

//RBTree.h
pair<Iterator, bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK; //空树插入的节点必须是黑色

		//return pair<Iterator, bool>(Iterator(_root, _root), true);
		return { Iterator(_root, _root), true };
	}

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

	cur = new Node(data);
	Node* newnode = cur;
	cur->_col = RED; //非空树插入的节点必须是红色
	if (kot(parent->_data) < kot(data))
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	//链接父亲
	cur->_parent = parent;

	//变色、旋转逻辑...

	return { Iterator(newnode, _root), true };
}

//Mymap.h
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;
}

3.总代码

1.RBTree.h

#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>
class RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

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

	Self& operator++()
	{
		if (_node->_right)
		{
			//右不为空，中序下一个访问的节点是右子树的最左（最小）结点
			Node* min = _node->_right;
			while (min->_left)
			{
				min = min->_left;
			}
			_node = min;
		}
		else
		{
			//右为空，祖先里面孩子是父亲左的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		if (_node == nullptr)  // --end()
		{
			// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
			Node* rightMost = _root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else if (_node->_left)
		{
			// 左子树不为空，中序左子树最后一个
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			}
			_node = rightMost;
		}
		else
		{
			// 孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				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;
	}
	
private:
	Node* _node;
	Node* _root;
};

//KeyOfT：获取T中的Key，其中T是红黑树存储的数据
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

	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);
	}

	pair<Iterator, bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK; //空树插入的节点必须是黑色

			//return pair<Iterator, bool>(Iterator(_root, _root), true);
			return { Iterator(_root, _root), true };
		}

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

		cur = new Node(data);
		Node* newnode = cur;
		cur->_col = RED; //非空树插入的节点必须是红色
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		//链接父亲
		cur->_parent = parent;

		//当父亲非空且是红色时：开始循环
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent; //该节点一定是黑色
			if (grandfather->_left == parent)
			{
				//   g
				// p   u
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED) //叔叔存在且为红
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else //叔叔不存在或者叔叔存在且为黑
				{
					if (parent->_left == cur) //g右单旋
					{
						//     g
						//   p   u
						// c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else //p左单旋、g右单旋
					{
						//    g
						//  p    u
						//    c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				//   g
				// u   p
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					//继续往上处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (parent->_right == cur)
					{
						//   g
						// u   p
						//       c
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//    g
						// u    p
						//    c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK; //根节点必须是黑色

		return { Iterator(newnode, _root), true };
	}

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

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		//记录parent的父节点
		Node* pParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		//当parent是根节点时
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else //当parent不是根节点时
		{
			subL->_parent = pParent;
			if (pParent->_left == parent)
				pParent->_left = subL;
			else
				pParent->_right = subL;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		//记录parent的父节点
		Node* pParent = parent->_parent;

		subR->_left = parent;
		parent->_parent = subR;

		//当parent是根节点时
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else //当parent不是根节点时
		{
			subR->_parent = pParent;
			if (pParent->_left == parent)
				pParent->_left = subR;
			else
				pParent->_right = subR;
		}
	}

private:
	Node* _root = nullptr;
};

2.Myset.h

#pragma once

#include"RBTree.h"

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

	public:
		//取类中的类型需要加上typename，为了区分静态成员变量
		typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, const K, SetKeyOfT>::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);
		}

	private:
		RBTree<K, const K, SetKeyOfT> _t;
	};
}

3.Mymap.h

#pragma once

#include"RBTree.h"

namespace xzy
{
	template<class K, class V>
	class map
	{
		//仿函数用于插入时比较Key的大小
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};

	public:
		//取类中的类型需要加上typename，为了区分静态成员变量
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::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;
		}

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

4.Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include"Myset.h"
#include"Mymap.h"

void TestSet()
{
	xzy::set<int> s;
	s.insert(1);
	s.insert(3);
	s.insert(5);
	s.insert(4);
	s.insert(2);

	xzy::set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		//*sit += 10; set中的Key不能被修改
		cout << *sit << " ";
		++sit;
	}
	cout << endl;

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

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

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

	xzy::map<string, string>::iterator mit = dict.begin();
	while (mit != dict.end())
	{
		//mit->first += "1";   map中的Key不能被修改
		//mit->second += "1";  map中的Value能被修改
	
		//cout << mit.operator->()->first << ":" << mit.operator->()->second << endl;
		cout << mit->first << ":" << mit->second << endl;
		++mit;
	}
	cout << endl;

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

void TestReverse()
{
	xzy::set<int> s;
	s.insert(1);
	s.insert(3);
	s.insert(5);
	s.insert(4);
	s.insert(2);

	//模拟反向迭代器
	xzy::set<int>::const_iterator it = s.end();
	while (it != s.begin())
	{
		--it;
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	TestSet();
	TestMap();
	TestReverse();

	return 0;
}