C++ map/set的模拟实现（基于红黑树）

目录

前言

封装前的红黑树源码

红黑树模板参数的控制

红黑树结点当中存储的数据

模板参数中仿函数的增加

迭代器的实现

set的模拟实现

map的模拟实现

---

前言

map/set是基于红黑树的关联式容器，在stl源码中的红黑树实现，用了header节点，使header节点的parent指向红黑树的根，这样实现了迭代器的end()可以自减到红黑树的最右节点，但本文的红黑树未用header节点封装，所以迭代器部分有缺陷，仅供学习stl复用的思想

---

封装前的红黑树源码

如下红黑树源码也可以封装出map和set，但是会要用到两颗红黑树，为了体现复用的思想，我们显然要用某种方法封装

	enum class Colour
	{
		RED, BLACK
	};
	template<class K ,class V>
	struct RBTreeNode
	{

		RBTreeNode(const pair<K, V>& kv) :
			_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv) , _col(Colour::RED)
		{}
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;
		pair<K, V> _kv;

		Colour _col;
	};

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



	public:
		RBTree():_root(nullptr)
		{}

		RBTree(const RBTree<K, V>& t)
		{
			_root = _copy(t._root, nullptr);
		}

		RBTree<K, V>& operator=(RBTree<K, V> t)
		{
			swap(_root, t._root);
			return *this;
		}

		bool erase(const K& k)
		{
			Node* cur = _root;
			Node* parent = nullptr;

			Node* delPos = nullptr;
			Node* delParentPos = nullptr;

			while (cur)
			{
				if (k > cur->_kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (k < cur->_kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if(cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
							if (_root)
							{
								_root->_parent = nullptr;
								_root->_col = Colour::BLACK;
							}
							delete cur;
							return true;
						}
						else
						{
							delParentPos = parent;
							delPos = cur;
						}
						break;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
							if (_root)
							{
								_root->_parent = nullptr;
								_root->_col = Colour::BLACK;
							}
							delete cur;
							return true;
						}
						else
						{
							delParentPos = parent;
							delPos = cur;
						}
						break;
					}
					else 
					{
						Node* RightMin = cur->_right;
						Node* minParent = cur;

						while (RightMin->_left)
						{
							minParent = RightMin;
							RightMin = RightMin->_left;
						}

						cur->_kv = RightMin->_kv;
						delParentPos = minParent;
						delPos = RightMin;
						break;
					}
				}
			}

			if (delPos == nullptr)//没有找到待删除节点
			{
				return false;
			}

			Node* del = delPos;
			Node* delP = delParentPos;

			if (delPos->_col == Colour::BLACK)
			{
				//delPos最多只有一个孩子
				if (delPos->_left)
				{
					delPos->_left->_col = Colour::BLACK;
				}
				else if (delPos->_right)
				{
					delPos->_right->_col = Colour::BLACK;
				}
				else
				{
					//brother 一定存在,不然无法满足各路径黑色数量相同的性质
					while (delPos != _root)
					{
						if (delPos == delParentPos->_left)
						{
							Node* brother = delParentPos->_right;

							//case 1

							if (brother->_col == Colour::RED)
							{
								delParentPos->_col = Colour::RED;
								brother->_col = Colour::BLACK;
								RotateL(delParentPos);
								brother = delParentPos->_right;
							}

							//case 2

							if ((brother->_left == nullptr || brother->_left->_col == Colour::BLACK)
								&& (brother->_right == nullptr || brother->_right->_col == Colour::BLACK))
							{
								brother->_col = Colour::RED;
								if (delParentPos->_col == Colour::RED)
								{
									delParentPos->_col = Colour::BLACK;
									break;
								}
								else
								{
									delPos = delParentPos;
									delParentPos = delParentPos->_parent;
								}
							}

							//case 3
							else
							{
								if (brother->_right == nullptr || brother->_right->_col == Colour::BLACK)
								{
									brother->_col = Colour::RED;
									brother->_left->_col = Colour::BLACK;
									RotateR(brother);
									brother = delParentPos->_right;
								}
								//case 4
								brother->_col = delParentPos->_col;
								brother->_right->_col = Colour::BLACK;
								delParentPos->_col = Colour::BLACK;
								RotateL(delParentPos);
								break;
							}
						}
						else
						{
							Node* brother = delParentPos->_left;
							
							//case 1
							if (brother->_col == Colour::RED)
							{
								delParentPos->_col = Colour::RED;
								brother->_col = Colour::BLACK;
								RotateR(delParentPos);
								brother = delParentPos->_left;
							}

							//case 2
							if ((brother->_left == nullptr || brother->_left->_col == Colour::BLACK)
								&& (brother->_right == nullptr || brother->_right->_col == Colour::BLACK))
							{
								brother->_col = Colour::RED;
								if (delParentPos->_col == Colour::RED)
								{
									delParentPos->_col = Colour::BLACK;
									break;
								}
								else
								{
									delPos = delParentPos;
									delParentPos = delParentPos->_parent;
								}
							}

							else
							{
								//case 3
								if (brother->_left == nullptr || brother->_left->_col == Colour::BLACK)
								{
									brother->_right->_col = Colour::BLACK;
									brother->_col = Colour::RED;
									RotateL(brother);
									brother = delParentPos->_left;
								}
								//case 4
								brother->_col = delParentPos->_col;
								delParentPos->_col = Colour::RED;
								brother->_left->_col = Colour::BLACK;
								RotateR(delParentPos);
								break;
							}
						}
					}
				}
			}

			//删除操作
			if (del->_left == nullptr)
			{
				if (delP->_left == del)
				{
					delP->_left = del->_right;
				}
				else
				{
					delP->_right = del->_right;
				}
				if (del->_right)
					del->_right->_parent = delP;
			}
			else
			{
				if (delP->_left == del)
				{
					delP->_left = del->_left;
				}
				else
				{
					delP->_right = del->_left;
				}
				if (del->_right)
					del->_right->_parent = delP;
			}

			return true;
		}


		bool insert(const pair<K, V>& kv)
		{
			if (!_root)
			{
				_root = new Node(kv);
				_root->_col = Colour::BLACK;
				return true;
			}

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				parent = cur;

				if (cur->_kv.first > kv.first)
				{
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					cur = cur->_right;
				}
				else
				{
					return false;
				}
			}

			cur = new Node(kv);
			if (parent ->_kv.first > cur->_kv.first)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;



			while (parent && parent->_col == Colour::RED)
			{
				Node* grandfather = parent->_parent;
				if (grandfather->_left == parent)
				{
					Node* uncle = grandfather->_right;
					//case 1  uncle存在且为红

					if (uncle && uncle->_col == Colour::RED)
					{
						uncle->_col = parent->_col = Colour::BLACK;
						grandfather->_col = Colour::RED;

						//adjustup
						cur = grandfather;
						parent = cur->_parent;
					}
                    //case 2  uncle存在且为黑
					//case 3  uncle不存在
					else
					{
						if (parent->_right == cur)
						{
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = Colour::BLACK;
							grandfather->_col = Colour::RED;
						}
						else
						{
							RotateR(grandfather);
							grandfather->_col = Colour::RED;
							parent->_col = Colour::BLACK;
						}
						break;
					}
				}
				else
				{
					Node* uncle = grandfather->_left;


					if (uncle && uncle->_col == Colour::RED)
					{
						uncle->_col = parent->_col = Colour::BLACK;
						grandfather->_col = Colour::RED;

						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						if (parent->_left == cur)
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = Colour::BLACK;
							grandfather->_col = Colour::RED;
						}
						else
						{
							RotateL(grandfather);
							grandfather->_col = Colour::RED;
							parent->_col = Colour::BLACK;
						}
						break;
					}
				}



			}

			_root->_col = Colour::BLACK;
			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
		}
		//判断是否为红黑树
		bool ISRBTree()
		{
			if (_root == nullptr) //空树是红黑树
			{
				return true;
			}
			if (_root->_col == Colour::RED)
			{
				cout << "error：根结点为红色" << endl;
				return false;
			}

			//找最左路径作为黑色结点数目的参考值
			Node* cur = _root;
			int BlackCount = 0;
			while (cur)
			{
				if (cur->_col == Colour::BLACK)
					BlackCount++;
				cur = cur->_left;
			}

			int count = 0;
			return _ISRBTree(_root, count, BlackCount);
		}
		~RBTree()
		{
			_Destroy(_root);
			_root = nullptr;
		}

	private:

		RBTree<K, V>& _copy(Node* root , Node* parent)
		{
			if (!root)
				return nullptr;

			Node* newNode = new Node(root->_kv);
			newNode->_parent = parent;
			newNode->_left = _copy(root->_left, newNode);
			newNode->_left = _copy(root->_right, newNode);

			return newNode;
		}

		void _Destroy(Node* root)
		{
			if (!root)
				return;
			_Destroy(root->_left);
			_Destroy(root->_right);

			delete root;
		}



		//判断是否为红黑树的子函数
		bool _ISRBTree(Node* root, int count, int BlackCount)
		{
			if (root == nullptr) //该路径已经走完了
			{
				if (count != BlackCount)
				{
					cout << "error：黑色结点的数目不相等" << endl;
					return false;
				}
				return true;
			}

			if (root->_col == Colour::RED && root->_parent->_col == Colour::RED)
			{
				cout << "error：存在连续的红色结点" << endl;
				return false;
			}
			if (root->_col == Colour::BLACK)
			{
				count++;
			}
			return _ISRBTree(root->_left, count, BlackCount) && _ISRBTree(root->_right, count, BlackCount);
		}
		void _InOrder(Node* root)
		{
			if (!root)
				return;
			_InOrder(root->_left);
			cout << root->_kv.first << " " << root->_kv.second << endl;
			_InOrder(root->_right);
		}
		void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;
			Node* ppNode = parent->_parent;

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

			SubR->_left = parent;
			parent->_parent = SubR;

			if (_root == parent)// _root == parent
			{
				_root = SubR;
			}
			else
			{
				if (ppNode->_left == parent)
					ppNode->_left = SubR;
				else
					ppNode->_right = SubR;
			}
			SubR->_parent = ppNode;

		}
		void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;
			Node* ppNode = parent->_parent;

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

			SubL->_right = parent;
			parent->_parent = SubL;


			if (_root == parent)// _root == parent
			{
				_root = SubL;
			}
			else
			{
				if (ppNode->_left == parent)
					ppNode->_left = SubL;
				else
					ppNode->_right = SubL;
			}
			SubL->_parent = ppNode;
		}
		Node* _root = nullptr;
	};

红黑树模板参数的控制

我们都知道，set是K模型的容器，而map是KV模型的容器，那我们如何用一棵KV模型的红黑树同时实现map和set呢？

这里我们就需要控制map和set传入底层红黑树的模板参数，为了与原红黑树的模板参数进行区分，我们将红黑树第二个模板参数的名字改为T。

template<class K, class T>
	class RBTree

T模板参数可能只是键值Key，也可能是由Key和Value共同构成的键值对。如果是set容器，那么它传入底层红黑树的模板参数就是Key和Key：

template<class K>
class set
{
public:
	//...
private:
	RBTree<K, K> _t;
};

但如果是map容器，那么它传入底层红黑树的模板参数就是Key以及Key和Value构成的键值对：

template<class K, class V>
class map
{
public:
	//...
private:
	RBTree<K, pair<K, V>> _t;
};

红黑树结点当中存储的数据

原先红黑树中存储的是键值对kv，现在对于set的T是key，map的T是键值对，那么我们只要把数据域改为T _data即可

 而且这样一来，节点的模板参数也只需要一个class T

代码如下：

	template<class T>
	struct RBTreeNode
	{

		RBTreeNode(const T& data) :
			_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(Colour::RED)
		{}
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent;
		T _data;
		Colour _col;
	};

模板参数中仿函数的增加

我们的目的是要用一颗红黑树封装出map和set，可是二者节点存储的数据类型不同，如何在一颗树种完成不同数据类型的key比较呢？

如果我们的map和set在构建红黑树时告诉我们的红黑树如何获取他们各自的数据的key，我们似乎就可以实现复用了，这个时候我们就可以增加红黑树的模板参数，这个模板参数可以拿出T中的key，而拿出key的方法我们让map和set来提供

我们在学习优先级队列时提到过Compare这样一个模板参数，默认是Less，它其实就是一个类，只不过实现了operator()的重载，从而有了类似函数的行为

红黑树的模板参数改为：    

template<class K, class T , class KOfT>
class RBTree

	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
    //....
    private:
	RBTree<K, pair<K, K>, SetKeyOfT> _t;
    }
	template<class K ,class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
    //....
    private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
    }

这样一来，当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较

例如我们find()的实现

iterator find(const K& key)
		{
			KOfT koft;
			Node* cur = _root;
			while (cur)
			{
				if (key < koft(cur->_data))
				{
					cur = cur->_left;
				}
				else if (key > koft(cur->_data))
				{
					cur = cur->_right; 
				}
				else 
				{
					return iterator(cur); 
				}
			}
			return end(); 
		}

注意： 所有进行结点键值比较的地方，均需要通过仿函数获取对应结点的键值后再进行键值的比较。

迭代器的实现

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

而为了体现复用，我们传入Ref和Ptr两个模板参数，就可以复用出const迭代器

对于基本的解引用，->访问 ， ==  , !=就不再赘述 ，难处在于++，--的实现

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


	public:
		_TreeIterator(Node* node):_node(node)
		{}

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

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

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

		bool operator!=(const Self& it)
		{
			return it._node != _node;
		}
	private:
		Node* _node;
	};

无论红黑树还是AVL树其本质都是二叉排序树的一种，既然叫做排序树，自然迭代器的移动要保持有序的状态，--，++都与大小挂钩

对于++，我们的下一个节点自然是比当前大，即中序遍历的后继节点

具体逻辑如下：

1. 如果当前结点的右子树不为空，则++操作后应该找到其右子树当中的最左结点。
2. 如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。

代码如下：

        Self& operator--()
		{
			
			if (_node->_left)
			{
				Node* LeftMax = _node->_left;
				while (LeftMax->_right)
					LeftMax = LeftMax->_right;
				_node = LeftMax;
			}
			else
			{
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && cur == parent->_left)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}
		Self operator++(int)
		{
			iterator ret(*this);
			++(*this);
			return ret;
		}

同理，对于--，我们的上一个节点即中序遍历的前驱节点

代码如下：

		Self& operator--()
		{
			
			if (_node->_left)
			{
				Node* LeftMax = _node->_left;
				while (LeftMax->_right)
					LeftMax = LeftMax->_right;
				_node = LeftMax;
			}
			else
			{
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && cur == parent->_left)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}

		Self operator--(int)
		{
			Self ret(*this);
			--(*this);
			return ret;
		}

实现迭代器基本功能后，我们就可以在红黑树中引入迭代器

	public:
		typedef _TreeIterator<T, T&, T*> iterator;
		typedef _TreeIterator<T, const T&, const T*> const_iterator;

接着再实现begin,end接口

• begin函数返回中序序列当中第一个结点的正向迭代器，即最左结点。
• end函数返回中序序列当中最后一个结点下一个位置的正向迭代器，这里直接用空指针构造一个正向迭代器。（但这是不完善的，无法令end--，如果要实现完善的迭代器需要用一个header节点的parent指向root对root进行封装）

const_iterator cend()
		{
			Node* cur = _root;
			while (cur && cur->_right)
				cur = cur->_right;
			return const_iterator(cur);
		}

		const_iterator cbegin()
		{
			Node* cur = _root;
			while (cur && cur->_left)
				cur = cur->_left;
			return const_iterator(cur);
		}

		iterator begin()
		{
			Node* cur = _root;
			while (cur && cur->_left)
				cur = cur->_left;
			return iterator(cur);
		}

		iterator end()
		{
			Node* cur = _root;
			while (cur && cur->_right)
				cur = cur->_right;
			return iterator(cur);
		}

下面介绍以下STL源码里迭代器的正确实现

C++STL库当中实现红黑树时，在红黑树的根结点处增加了一个头结点，该头结点的左指针指向红黑树当中的最左结点，右指针指向红黑树当中的最右结点，父指针指向红黑树的根结点。

在该结构下，实现begin()时，直接用头结点的左孩子构造一个正向迭代器即可，实现rbegin()时，直接用头结点的右孩子构造一个反向迭代器即可（实际是先用该结点构造一个正向迭代器，再用正向迭代器构造出反向迭代器），而实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。此后，通过对逻辑的控制，就可以实现end()进行--操作后得到最后一个结点的正向迭代器。

但实现该结构需要更改当前很多函数的逻辑，例如插入结点时，若插入到了红黑树最左结点的左边，或最右结点的右边，此时需要更新头结点左右指针的指向，这里就不进行实际实现了。

反向迭代器

红黑树的反向迭代器实际上就是正向迭代器的一个封装，因此红黑树的反向迭代器就是一个迭代器适配器。也不再进行实现了

封装后的红黑树源码

#ifndef RBTREE_H
#define RBTREE_H
namespace Simulate
{
	enum class Colour
	{
		RED, BLACK
	};
	template<class T>
	struct RBTreeNode
	{

		RBTreeNode(const T& data) :
			_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(Colour::RED)
		{}
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent;
		T _data;
		Colour _col;
	};

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


	public:
		_TreeIterator(Node* node):_node(node)
		{}

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

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

		Self& operator++()
		{
			if (_node->_right)
			{
				Node* RightMin = _node->_right;
				while (RightMin->_left)
					RightMin = RightMin->_left;
				_node = RightMin;
			}
			else
			{
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && cur == parent->_right)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}

		Self operator++(int)
		{
			iterator ret(*this);
			++(*this);
			return ret;
		}

		Self& operator--()
		{
			
			if (_node->_left)
			{
				Node* LeftMax = _node->_left;
				while (LeftMax->_right)
					LeftMax = LeftMax->_right;
				_node = LeftMax;
			}
			else
			{
				Node* parent = _node->_parent;
				Node* cur = _node;
				while (parent && cur == parent->_left)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_node = parent;
			}
			return *this;
		}

		Self operator--(int)
		{
			Self ret(*this);
			--(*this);
			return ret;
		}

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

		bool operator!=(const Self& it)
		{
			return it._node != _node;
		}
	private:
		Node* _node;
	};


	template<class K, class T , class KOfT>
	class RBTree
	{
		typedef RBTreeNode<T> Node;
	public:
		typedef _TreeIterator<T, T&, T*> iterator;
		typedef _TreeIterator<T, const T&, const T*> const_iterator;

		RBTree():_root(nullptr)
		{}

		RBTree(const RBTree<K, T , KOfT>& t)
		{
			_root = _Copy(t._root, nullptr);
		}

		RBTree<K, T, KOfT>& operator=(RBTree<K, T, KOfT> t)
		{
			swap(_root, t._root);
			return *this;
		}

		~RBTree()
		{
			_Destroy(_root);
			_root = nullptr;
		}

		iterator find(const K& key)
		{
			KOfT koft;
			Node* cur = _root;
			while (cur)
			{
				if (key < koft(cur->_data))
				{
					cur = cur->_left;
				}
				else if (key > koft(cur->_data))
				{
					cur = cur->_right; 
				}
				else 
				{
					return iterator(cur); 
				}
			}
			return end(); 
		}


		const_iterator cend()
		{
			Node* cur = _root;
			while (cur && cur->_right)
				cur = cur->_right;
			return const_iterator(cur);
		}

		const_iterator cbegin()
		{
			Node* cur = _root;
			while (cur && cur->_left)
				cur = cur->_left;
			return const_iterator(cur);
		}

		iterator begin()
		{
			Node* cur = _root;
			while (cur && cur->_left)
				cur = cur->_left;
			return iterator(cur);
		}

		iterator end()
		{
			Node* cur = _root;
			while (cur && cur->_right)
				cur = cur->_right;
			return iterator(cur);
		}
		bool erase(const K& k)
		{
			KOfT koft;
			Node* cur = _root;
			Node* parent = nullptr;

			Node* delPos = nullptr;
			Node* delParentPos = nullptr;

			while (cur)
			{
				if (k > koft(cur->_data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (k < koft(cur->_data))
				{
					parent = cur;
					cur = cur->_left;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_right;
							if (_root)
							{
								_root->_parent = nullptr;
								_root->_col = Colour::BLACK;
							}
							delete cur;
							return true;
						}
						else
						{
							delParentPos = parent;
							delPos = cur;
						}
						break;
					}
					else if (cur->_right == nullptr)
					{
						if (cur == _root)
						{
							_root = cur->_left;
							if (_root)
							{
								_root->_parent = nullptr;
								_root->_col = Colour::BLACK;
							}
							delete cur;
							return true;
						}
						else
						{
							delParentPos = parent;
							delPos = cur;
						}
						break;
					}
					else
					{
						Node* RightMin = cur->_right;
						Node* minParent = cur;

						while (RightMin->_left)
						{
							minParent = RightMin;
							RightMin = RightMin->_left;
						}

						cur->_data = RightMin->_data;
						delParentPos = minParent;
						delPos = RightMin;
						break;
					}
				}
			}

			if (delPos == nullptr)//没有找到待删除节点
			{
				return false;
			}

			Node* del = delPos;
			Node* delP = delParentPos;

			if (delPos->_col == Colour::BLACK)
			{
				//delPos最多只有一个孩子
				if (delPos->_left)
				{
					delPos->_left->_col = Colour::BLACK;
				}
				else if (delPos->_right)
				{
					delPos->_right->_col = Colour::BLACK;
				}
				else
				{
					//brother 一定存在,不然无法满足各路径黑色数量相同的性质
					while (delPos != _root)
					{
						if (delPos == delParentPos->_left)
						{
							Node* brother = delParentPos->_right;

							//case 1

							if (brother->_col == Colour::RED)
							{
								delParentPos->_col = Colour::RED;
								brother->_col = Colour::BLACK;
								RotateL(delParentPos);
								brother = delParentPos->_right;
							}

							//case 2

							if ((brother->_left == nullptr || brother->_left->_col == Colour::BLACK)
								&& (brother->_right == nullptr || brother->_right->_col == Colour::BLACK))
							{
								brother->_col = Colour::RED;
								if (delParentPos->_col == Colour::RED)
								{
									delParentPos->_col = Colour::BLACK;
									break;
								}
								else
								{
									delPos = delParentPos;
									delParentPos = delParentPos->_parent;
								}
							}

							//case 3
							else
							{
								if (brother->_right == nullptr || brother->_right->_col == Colour::BLACK)
								{
									brother->_col = Colour::RED;
									brother->_left->_col = Colour::BLACK;
									RotateR(brother);
									brother = delParentPos->_right;
								}
								//case 4
								brother->_col = delParentPos->_col;
								brother->_right->_col = Colour::BLACK;
								delParentPos->_col = Colour::BLACK;
								RotateL(delParentPos);
								break;
							}
						}
						else
						{
							Node* brother = delParentPos->_left;

							//case 1
							if (brother->_col == Colour::RED)
							{
								delParentPos->_col = Colour::RED;
								brother->_col = Colour::BLACK;
								RotateR(delParentPos);
								brother = delParentPos->_left;
							}

							//case 2
							if ((brother->_left == nullptr || brother->_left->_col == Colour::BLACK)
								&& (brother->_right == nullptr || brother->_right->_col == Colour::BLACK))
							{
								brother->_col = Colour::RED;
								if (delParentPos->_col == Colour::RED)
								{
									delParentPos->_col = Colour::BLACK;
									break;
								}
								else
								{
									delPos = delParentPos;
									delParentPos = delParentPos->_parent;
								}
							}

							else
							{
								//case 3
								if (brother->_left == nullptr || brother->_left->_col == Colour::BLACK)
								{
									brother->_right->_col = Colour::BLACK;
									brother->_col = Colour::RED;
									RotateL(brother);
									brother = delParentPos->_left;
								}
								//case 4
								brother->_col = delParentPos->_col;
								delParentPos->_col = Colour::RED;
								brother->_left->_col = Colour::BLACK;
								RotateR(delParentPos);
								break;
							}
						}
					}
				}
			}

			//删除操作
			if (del->_left == nullptr)
			{
				if (delP->_left == del)
				{
					delP->_left = del->_right;
				}
				else
				{
					delP->_right = del->_right;
				}
				if (del->_right)
					del->_right->_parent = delP;
			}
			else
			{
				if (delP->_left == del)
				{
					delP->_left = del->_left;
				}
				else
				{
					delP->_right = del->_left;
				}
				if (del->_right)
					del->_right->_parent = delP;
			}

			return true;
		}


		pair<iterator, bool> insert(const T& data)
		{
			if (!_root)
			{
				_root = new Node(data);
				_root->_col = Colour::BLACK;
				return make_pair(iterator(_root), true);
			}

			KOfT koft;

			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				parent = cur;

				if (koft(cur->_data) > koft(data))
				{
					cur = cur->_left;
				}
				else if (koft(cur->_data) < koft(data))
				{
					cur = cur->_right;
				}
				else
				{
					return make_pair(iterator(cur), false);
				}
			}

			cur = new Node(data);
			if (koft(parent->_data) > koft(cur->_data))
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			cur->_parent = parent;



			while (parent && parent->_col == Colour::RED)
			{
				Node* grandfather = parent->_parent;
				if (grandfather->_left == parent)
				{
					Node* uncle = grandfather->_right;
					//case 1  uncle存在且为红

					if (uncle && uncle->_col == Colour::RED)
					{
						uncle->_col = parent->_col = Colour::BLACK;
						grandfather->_col = Colour::RED;

						//adjustup
						cur = grandfather;
						parent = cur->_parent;
					}
					//case 2  uncle存在且为黑
					//case 3  uncle不存在
					else
					{
						if (parent->_right == cur)
						{
							RotateL(parent);
							RotateR(grandfather);
							cur->_col = Colour::BLACK;
							grandfather->_col = Colour::RED;
						}
						else
						{
							RotateR(grandfather);
							grandfather->_col = Colour::RED;
							parent->_col = Colour::BLACK;
						}
						break;
					}
				}
				else
				{
					Node* uncle = grandfather->_left;


					if (uncle && uncle->_col == Colour::RED)
					{
						uncle->_col = parent->_col = Colour::BLACK;
						grandfather->_col = Colour::RED;

						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
						if (parent->_left == cur)
						{
							RotateR(parent);
							RotateL(grandfather);
							cur->_col = Colour::BLACK;
							grandfather->_col = Colour::RED;
						}
						else
						{
							RotateL(grandfather);
							grandfather->_col = Colour::RED;
							parent->_col = Colour::BLACK;
						}
						break;
					}
				}



			}

			_root->_col = Colour::BLACK;
			return make_pair(iterator(cur), true);
		}

		void InOrder()
		{
			KOfT koft;
			_InOrder(_root, koft);
		}
		//判断是否为红黑树
		bool ISRBTree()
		{
			if (_root == nullptr) //空树是红黑树
			{
				return true;
			}
			if (_root->_col == Colour::RED)
			{
				cout << "error：根结点为红色" << endl;
				return false;
			}

			//找最左路径作为黑色结点数目的参考值
			Node* cur = _root;
			int BlackCount = 0;
			while (cur)
			{
				if (cur->_col == Colour::BLACK)
					BlackCount++;
				cur = cur->_left;
			}

			int count = 0;
			return _ISRBTree(_root, count, BlackCount);
		}


	private:

		Node* _Copy(Node* root, Node* parent)
		{
			if (root == nullptr)
			{
				return nullptr;
			}
			Node* copyNode = new Node(root->_data);
			copyNode->_parent = parent;
			copyNode->_left = _Copy(root->_left, copyNode);
			copyNode->_right = _Copy(root->_right, copyNode);
			return copyNode;
		}

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

		//判断是否为红黑树的子函数
		bool _ISRBTree(Node* root, int count, int BlackCount)
		{
			if (root == nullptr) //该路径已经走完了
			{
				if (count != BlackCount)
				{
					cout << "error：黑色结点的数目不相等" << endl;
					return false;
				}
				return true;
			}

			if (root->_col == Colour::RED && root->_parent->_col == Colour::RED)
			{
				cout << "error：存在连续的红色结点" << endl;
				return false;
			}
			if (root->_col == Colour::BLACK)
			{
				count++;
			}
			return _ISRBTree(root->_left, count, BlackCount) && _ISRBTree(root->_right, count, BlackCount);
		}
		void _InOrder(Node* root , KOfT& koft)
		{
			if (!root)
				return;
			_InOrder(root->_left, koft);
			cout << koft(root->_data) << endl;
			_InOrder(root->_right, koft);
		}
		void RotateL(Node* parent)
		{
			Node* SubR = parent->_right;
			Node* SubRL = SubR->_left;
			Node* ppNode = parent->_parent;

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

			SubR->_left = parent;
			parent->_parent = SubR;

			if (_root == parent)// _root == parent
			{
				_root = SubR;
			}
			else
			{
				if (ppNode->_left == parent)
					ppNode->_left = SubR;
				else
					ppNode->_right = SubR;
			}
			SubR->_parent = ppNode;

		}
		void RotateR(Node* parent)
		{
			Node* SubL = parent->_left;
			Node* SubLR = SubL->_right;
			Node* ppNode = parent->_parent;

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

			SubL->_right = parent;
			parent->_parent = SubL;


			if (_root == parent)// _root == parent
			{
				_root = SubL;
			}
			else
			{
				if (ppNode->_left == parent)
					ppNode->_left = SubL;
				else
					ppNode->_right = SubL;
			}
			SubL->_parent = ppNode;
		}
		Node* _root = nullptr;
	};

}

#endif // !RBTREE_H

set的模拟实现

完成上述操作后，set的模拟实现也就很简单了，其中的成员函数都是调用底层红黑树的对应接口就行了，只不过需要注意将插入函数和查找函数返回值当中的结点指针改为迭代器即可。

代码如下：

	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& k)
			{
				return k;
			}
		};
		typedef typename Simulate::RBTree<K, K, SetKeyOfT>::iterator iterator;

	public:

		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return iterator(nullptr);
		}
		pair<iterator, bool> insert(const K& k)
		{
			return _t.insert(k);
		}
		bool erase(const K& k)
		{
			return _t.erase(k);
		}
		void InOrder()
		{
			_t.InOrder();
		}
	private:

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

map的模拟实现

map的模拟实现也是相同的道理，其成员函数也是调用底层红黑树的对应接口，但对于map来说，除了将插入函数和查找函数返回值当中的结点指针改为迭代器之外，还需要实现[]运算符的重载函数。

代码如下：

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


	public:

		typedef typename Simulate::RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
		typedef typename Simulate::RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_iterator;
		
		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = insert(make_pair(key, V()));
			iterator it = ret.first;
			return it->second;
		}

		const_iterator cbegin()
		{
			return _t.cbegin();
		}
		const_iterator cend()
		{
			return const_iterator(nullptr);
		}

		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return iterator(nullptr);
		}
		
		pair<iterator,bool> insert(const pair<K, V>& kv)
		{
			return _t.insert(kv);
		}
		bool erase(const K& k)
		{
			return _t.erase(k);
		}
		void InOrder()
		{
			_t.InOrder();
		}
	private:

		Simulate::RBTree<K, pair<K, V>, MapKeyOfT> _t;

	};