目录

map与set模拟实现

红黑树适配map与set

map与set都是树形结构的关联式容器，他们都使用平衡搜索树（红黑树）作为底层结构，元素有序。不同的是set是key模型的搜索树，而map是key-value模型的搜索树。使用红黑树，将其进行封装和改造就可以很好的适配出这两个容器。

set存储的数据是key，而map存储的数据是pair<key,value>这样的键值对，为了统一接口，我们可以使用key-value模型的红黑树，在实现set的时候通过RBTree<key, const key> 示例化出底层容器，在实现map的时候用RBTree<key, pair<const key, value>> 来示例化出底层容器。

map这里的key可不可以去掉呢？

选择 RBTree<key, pair<const key, value>> 而不是 RBTree<const key, value> 的核心原因在于语义完整性和接口一致性的问题。Map 的本质是键值对容器，其每个元素都应该是一个完整的键值对，而不仅仅是值部分。如果采用 RBTree<const key, value> 的设计，红黑树节点将键和值拆分开存储，这会导致迭代器解引用时只能返回值而丢失键信息，破坏了 Map 作为键值对容器的完整语义。使用第一种方法，在查找的时候都可以通过第一个元素key去查找，而返回则对应第二个元素，set依旧返回key，而map返回键值对。

请添加图片描述

代码示例如下：

这里只做适配器设计方面的解释，具体函数实现在后文

RBTree.h

#pragma once

#include<iostream>
#include<cassert>

namespace Tree {

	enum Color { RED, BLACK };
	template<class K, class V>
	struct RBTreeNode {
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;


		K _key;
		V _value;

		Color _color;

		RBTreeNode(const K& key = K(), const V& value = V())
			:_key(key), _value(value), _left(nullptr),
			_right(nullptr), _color(RED), _parent(nullptr) {
		}

	};

	
	using namespace std;

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

	public:


		RBTree() :_root(nullptr) {}

		
	private:
	
		Node* _root = nullptr;
		int _size = 0;
	};

}

map.h

#pragma once
#include"RBTree.h"

namespace Mymap {
	using namespace Tree;

	template<class K, class V>
	class map
	{
		struct keyOfvalue {
			const K& operator()(const pair<const K, V>& data)
			{
				return data.first;
			}
		};
		typedef pair<const K, V> T;
		typedef RBTree<K, T ,keyOfvalue> Tree; //使用RBTree<K, pair<const K, V>> 来适配
        
	public:
		
	private:
		Tree _tr;  
	};
}

set.h

#pragma once
#include"RBTree.h"

namespace Myset {
	using namespace Tree;

	template<class K>
	class set
	{
		struct keyOfvalue {
			 const K operator()(const K& data)
			 {
				 return data;
			 }
		};
		typedef RBTree< K, const K, keyOfvalue> Tree;//使用RBTree<K,const K> 来适配

	public:
	
	private:
		 Tree _tr;
	};
}

上述代码中keyOfvalue在后文讲解

红黑树改造

红黑树在我之前的博客有实现讲解，(点击即可跳转-红黑树实现）可以去学习了之后在看本篇文章，

但是这里的红黑树要与之前的红黑树稍作修改。

红黑树迭代器设计

在之前的红黑树讲解中我们没有涉及到迭代器的实现，因此在封装map与set之前要先设计一下红黑树的迭代器

与链表的类似，我们可以在迭代器中封装一个节点指针，在解引用的时候返回其内部数据，比较时比较指针即可。同时在模板参数上加入Ptr，Ref，来让编译器生成const和非const版本的迭代器，如果不太理解，可以参考文章stl之链表实现，点击即可跳转，有详细介绍

但是不同的是，这里的++，–操作与链表大不相同。

迭代器++操作

首先我们先回忆一下迭代器遍历的顺序，在搜索树类的容器中，一般正向遍历出来都是有序的，即按照中序遍历来增加迭代器。

在这里插入图片描述

中序遍历即按照
左子树，根，右子树的遍历顺序。如上图中的红色顺序那么走到一个节点时，他的中序遍历的下一个节点分两种情况：

1.右子树存在

如果右子树存在，那么按照左，根，右的顺序，下一个节点就应该是右子树的最左节点。

举例：

上图的2节点，右子树存在，他的下一个就是右子树的最左节点，即以3为根的子树的最左节点，即3节点。

上图的5节点，右子树存在，他的下一个就是右子树的最左节点，即以8为根的子树的最左节点，即6节点。

2.右子树不存在

如果右子树不存在，那就证明以该节点为最右节点的所有子树已经遍历完了，那么下一个节点就是以该节点为最右节点的子树中，不是某一个树的右子树的子树，即以该节点为最右节点，最大的那棵子树根节点的父节点。总结一下就是，第一个出现在右边的祖先（他的左子树为前面所说的最大子树）就是下一个节点

举例：

上图中的4节点，右树不存在，那么向上寻找第一个出现在右边的祖先，即2的父节点，5节点。4节点为2节点的最右节点，4节点遍历完意味着以2为根的子树都遍历完了。

上图中的7节点，右树不存在，那么向上寻找第一个出现在右边的祖先，即6的父节点，8节点。7节点为6节点的最右节点，7节点遍历完意味着以6为根的子树都遍历完了。

图中紫色路径就是寻找第一个出现在右边的祖先节点的路径

迭代器–操作

理解了++操作，那么理解–操作就相对容易，我们可以逆向分析。

1.左子树存在

还是以上图的5节点为例，他是4节点的下一个，因为4节点遍历完了意味着以2为根的子树遍历完了，换而言之，4节点是2为根的子树的中序遍历最后一个（最右）节点。那么，对于5而言，左子树存在，就应该去找左子树的最后一个，即最右节点。其他左子树存在的节点也同理。

总结一下，一个节点的左子树存在，他中序遍历的上一个节点就是左子树的最右节点

2.左子树不存在

一个节点没有左子树，那就意味着他是某一个子树的最左节点，即该子树中序遍历的第一个节点，那么他中序遍历的上一个节点就应为以该节点为最左节点的子树中，最大的那棵子树根节点的父节点。

而上图中以6为最左节点的子树为8节点，那么6的上一个节点即为8节点的父亲节点5节点。

end–特殊处理

在stl库中，红黑树的设计有一个头节点header。

在这里插入图片描述

对于最后一个节点9，他的下一个节点按照规则就可以定位到header节点，那么end()就可以返回该节点的迭代器，同时就可以实现end()–操作。

而我们的红黑树并没有header节点，我们的end()用nullptr去构造，这样可以省去维护header节点的成本，但同时也带来了end()–无法实现的问题。

因为end()中为nullptr，无法找到其父节点。

解决方案：

在迭代器中加入一个成员root，在构造迭代器的时候同时初始化root，将其设为红黑树的根节点如果在end()–操作中，遇到指针为nulllptr的情况，那就返回最右节点，即中序遍历最后一个节点所构造的迭代器，从而解决该问题。

唯一没有办法解决的是迭代器失效问题。如果构造了一个迭代器it = end(),此时在对红黑树进行操作（插入或者删除），如果根节点发生变化，那么–it中由于root不在是最新的根结点，可能会出现无法使用的问题。因此请避免该情况，在使用迭代器前不要进行插入删除操作。

迭代器设计代码：
template<class K, class V, class Ref, class Ptr >
	struct SetIterator {
		typedef RBTreeNode<K, V> Node;
		typedef SetIterator<K, V, Ref, Ptr> Self;

		Node* _it;
		SetIterator(Node* it = nullptr,Node* root = nullptr):_it(it),_root(root)
		{}

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

		Ref operator*() const 
		{
			return _it->_value;
		}
		Ptr operator->() const 
		{
			return &(_it->_value);
		}

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

			if (_it->_right != nullptr)
			{
				cur = cur->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return Self(ret);
		}

		Self& operator--()
		{
			Node* cur = _it;
			if (_it == nullptr)
			{
				Node* rightmost = _root;
				while (rightmost->_right)
				{
					rightmost = rightmost->_right;
				}
				_it = rightmost;
				return *this;
			}

			if (_it->_left != nullptr)
			{
				cur = cur->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return *this;
		}
		Self operator--(int)
		{
			Node* cur = _it;
			Node* ret = _it;
			if (_it == nullptr)
			{
				Node* rightmost = _root;
				while (rightmost->_right)
				{
					rightmost = rightmost->_right;
				}
				_it = rightmost;
			}
			else if (_it->_left != nullptr)
			{
				cur = cur->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return Self(ret);
		}
		private:
		 Node* _root = nullptr;

	};

反向迭代器

反向迭代器仍然采用适配器设计模式，将普通迭代器进行封装得到。可以参考文章反向迭代器设计

代码如下：

template <class Iterator, class Ref, class Ptr>
	class reverse_Iterator {

		typedef reverse_Iterator<Iterator, Ref, Ptr> Self;
		Iterator _reit;
	public:
		reverse_Iterator(const Iterator& it = Iterator()) :_reit(it)
		{
		}
		Self& operator++()
		{
			--_reit;
			return *this;
		}

		Self operator++(int)
		{
			return _reit--;
		}

		Self& operator--()
		{
			 ++_reit;
			 return *this;
		}

		Self operator--(int)
		{
			return _reit++;
		}

		Ref operator*()
		{
			Iterator tmp = _reit;
			return *(--tmp);
		}

		Ptr operator->()
		{
			Iterator tmp = _reit;
			tmp--;
			return tmp.operator->();
		}

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

红黑树插入改造

接口统一

我们之前的插入函数为

bool Insert(const K& key, const V& value)；

在stl库中红黑树的插入是

pair<Iterator,bool> Insert(const V& data) ；

因为在接口设计上map与set要进行统一。在map与set各自的插入操作中，我们希望实现的是

//pair<iterator,bool> insert(const T& data) //map的数据为T类型，即pair<const key, value>

pair<iterator,bool> insert(const V& data) //set的数据为V，即value

{

​ return _tr.Insert(data);

}

两个容器都是这样的调用，唯独data的类型不同那么我们在红黑树里面插入的时候就会存在问题：

bool Insert(const K& key, const V& value) {

​ Node* newNode = new Node(key, value);

//……

}

之前我们这样申请节点，那么现在进行封装后，对于接口pair<Iterator,bool> Insert(const V& data) ；，我们只传入一个参数，对于同一份代码，我们要怎么样区分map和set，或者说要怎么样区分这里data的类型

pair<Iterator,bool> Insert(const V& data) {

​ Node* newNode = new Node(data, data); //对于set是这样

​ Node* newNode = new Node(data.first, data); //对于map是这样,

}

那么我们可以通过一个仿函数来统一控制这里的逻辑，既然红黑树这层不能区分类型，那就从上层map与set区分，在map与set中定一个仿函数keyOfvalue，

set中返回data, map中返回data.first。通过模板参数传入到红黑树中，这样就可以实现我们所要的效果，当set进行实例化的时候为Node* newNode = new Node(data, data)， 当map进行实例化的时候为Node* newNode = new Node(data.first, data);，进行统一接口。

pair<Iterator,bool> Insert(const V& data) {

Node* newNode = new Node(keyOfvalue()(data), data);

}

对于返回值我们模仿库中的返回值，若树中存在该键值，那么插入失败，返回该位置的迭代器和false组成的键值对，若树中不存在数据，插入成功后，返回插入成功后的位置的迭代器与true组成的键值对。

map与set实现代码

map.h与set.h接口除了operator[]之外，其他都一致。operator[]在map与set使用中有详解解释，可以参考文章map与set使用详解，点击即可跳转

RBTree.h

#pragma once

#include<iostream>
#include<cassert>

namespace Tree {


	enum Color { RED, BLACK };

	template<class K, class V>
	struct RBTreeNode {
		RBTreeNode<K, V>* _left;
		RBTreeNode<K, V>* _right;
		RBTreeNode<K, V>* _parent;


		K _key;
		V _value;

		Color _color;

		RBTreeNode(const K& key = K(), const V& value = V())
			:_key(key), _value(value), _left(nullptr),
			_right(nullptr), _color(RED), _parent(nullptr) {
		}

	};

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

		Node* _it;
		SetIterator(Node* it = nullptr,Node* root = nullptr):_it(it),_root(root)
		{}

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

		Ref operator*() const 
		{
			return _it->_value;
		}
		Ptr operator->() const 
		{
			return &(_it->_value);
		}

		Self& operator++() 
		{
			Node* cur = _it;
			if (_it->_right != nullptr)
			{
				cur = cur->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				_it = cur;

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

			if (_it->_right != nullptr)
			{
				cur = cur->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_right == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return Self(ret);
		}

		Self& operator--()
		{
			Node* cur = _it;
			if (_it == nullptr)
			{
				Node* rightmost = _root;
				while (rightmost->_right)
				{
					rightmost = rightmost->_right;
				}
				_it = rightmost;
				return *this;
			}

			if (_it->_left != nullptr)
			{
				cur = cur->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return *this;
		}
		Self operator--(int)
		{
			Node* cur = _it;
			Node* ret = _it;
			if (_it == nullptr)
			{
				Node* rightmost = _root;
				while (rightmost->_right)
				{
					rightmost = rightmost->_right;
				}
				_it = rightmost;
			}
			else if (_it->_left != nullptr)
			{
				cur = cur->_left;
				while (cur->_right)
				{
					cur = cur->_right;
				}
				_it = cur;

			}
			else
			{
				Node* parent = cur->_parent;
				while (parent && parent->_left == cur)
				{
					cur = parent;
					parent = parent->_parent;
				}
				_it = parent;
			}
			return Self(ret);
		}
		private:
		 Node* _root = nullptr;

	};

	template <class Iterator, class Ref, class Ptr>
	class reverse_Iterator {

		typedef reverse_Iterator<Iterator, Ref, Ptr> Self;
		Iterator _reit;
	public:
		reverse_Iterator(const Iterator& it = Iterator()) :_reit(it)
		{
		}
		Self& operator++()
		{
			--_reit;
			return *this;
		}

		Self operator++(int)
		{
			return _reit--;
		}

		Self& operator--()
		{
			 ++_reit;
			 return *this;
		}

		Self operator--(int)
		{
			return _reit++;
		}

		Ref operator*()
		{
			Iterator tmp = _reit;
			return *(--tmp);
		}

		Ptr operator->()
		{
			Iterator tmp = _reit;
			tmp--;
			return tmp.operator->();
		}

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

	};
	using namespace std;

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

	public:
		typedef SetIterator<K, V, V&, V*> Iterator;
		typedef SetIterator<K, V, const V&, const V*> const_Iterator;
		typedef reverse_Iterator<Iterator, V&, V*> reverseIterator;
		typedef reverse_Iterator<const_Iterator, const V&, const V*> const_reverse_Iterator;


		RBTree() :_root(nullptr) {}
		RBTree(const RBTree& tree)
		{
			_root = Copy(tree._root);
		}

		RBTree& operator=(const RBTree& tree)
		{
			return BSTree(tree);
		}
		~RBTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

		Iterator Begin()
		{
			Node* leftmost = _root;
			while (leftmost->_left)
			{
				leftmost = leftmost->_left;
			}
			return Iterator(leftmost, _root);
		}

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

		const_Iterator cBegin()
		{
			Node* leftmost = _root;
			while (leftmost->_left)
			{
				leftmost = leftmost->_left;
			}
			return const_Iterator(leftmost, _root);
		}

		const_Iterator cEnd()
		{
			return const_Iterator(nullptr, _root);
		}

		reverseIterator rBegin()
		{
			return reverseIterator(End());
		}

		reverseIterator rEnd()
		{
			return reverseIterator(Begin());
		}
		
		const_reverse_Iterator crBegin()
		{
	
			return const_reverse_Iterator(cEnd());
		}

		const_reverse_Iterator crEnd()
		{
			return const_reverse_Iterator(cBegin());
		}



		pair<Iterator,bool> Insert(const V& data) {
			Node* newNode = new Node(keyOfvalue()(data), data);
			K key = keyOfvalue()(data);
			if (_root == nullptr) {
				_root = newNode;
			}
			else {
				Node* parent = _root;
				Node* cur = _root;

				while (cur) {
					parent = cur;
					if (key < cur->_key) cur = cur->_left;
					else if (key > cur->_key) cur = cur->_right;
					else return make_pair<Iterator, bool>(Iterator(newNode), false);
				}

				if (key < parent->_key) {
					parent->_left = newNode;
				}
				else {
					parent->_right = newNode;
				}
				newNode->_parent = parent;
				cur = newNode;

				while (parent != nullptr && parent != _root && parent->_color == RED) {
					Node* grandFather = parent->_parent;
					Node* uncle = (parent == grandFather->_left ? grandFather->_right : grandFather->_left);

					if (uncle != nullptr && uncle->_color == RED) {
						parent->_color = uncle->_color = BLACK;
						grandFather->_color = RED;

						cur = grandFather;
						parent = grandFather->_parent;
					}
					else {//(uncle == nullptr || uncle->_color == BLACK)

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

								parent->_color = BLACK;
								grandFather->_color = RED;
							}
							//     g
							//   p   u
							//     c
							else {
								RotateLR(grandFather);
								grandFather->_color = RED;
								cur->_color = BLACK;
							}

						}
						else {
							//     g
							//   u   p
							//         c
							if (cur == parent->_right) {
								RotateL(grandFather);
								parent->_color = BLACK;
								grandFather->_color = RED;
							}
							//     g
							//   u   p
							//     c
							else {
								RotateRL(grandFather);
								grandFather->_color = RED;
								cur->_color = BLACK;
							}
						}
						break;
					}
				}

			}

			_root->_color = BLACK;
			_size++;
			return make_pair<Iterator, bool>(Iterator(newNode), true);
		}

		Iterator Find(const K& key)
		{

			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key) cur = cur->_left;
				else if (key > cur->_key) cur = cur->_right;
				else return Iterator(cur);
			}
			return End();
		}
		const_Iterator Find(const K& key) const
		{

			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key) cur = cur->_left;
				else if (key > cur->_key) cur = cur->_right;
				else return const_Iterator(cur);
			}
			return cEnd();
		}
		bool Erase(const K& key)
		{
			if (_root == nullptr) return false;
			Node* parent = _root;
			Node* cur = _root;

			while (cur && cur->_key != key) {
				parent = cur;
				if (key < cur->_key) cur = cur->_left;
				else  cur = cur->_right;
			}
			if (cur == nullptr) return false;

			if (cur->_right == nullptr) {
				if (cur == parent->_left) {
					parent->_left = cur->_left;
				}
				else if (cur == parent->_right) {
					parent->_right = cur->_left;
				}
				else if (cur == _root)
				{
					_root = cur->_left;
				}
				else
				{
					assert(false);
				}
				delete cur;
			}
			else if (cur->_left == nullptr) {
				if (cur == parent->_left) {
					parent->_left = cur->_right;
				}
				else if (cur == parent->_right) {
					parent->_right = cur->_right;
				}
				else if (cur == _root)
				{
					_root = cur->_right;
				}
				else
				{
					assert(false);
				}

				delete cur;
			}
			else {
				Node* leftMaxParent = cur;
				Node* leftMax = cur->_left;
				while (leftMax->_right) {
					leftMaxParent = leftMax;
					leftMax = leftMax->_right;
				}
				swap(cur->_key, leftMax->_key);
				swap(cur->_value, leftMax->_value);

				if (leftMax == leftMaxParent->_left) {
					leftMaxParent->_left = leftMax->_left;
				}
				else {
					leftMaxParent->_right = leftMax->_left;
				}

				delete leftMax;
			}


			_size--;
			return true;
		}
		void Clear()
		{
			Destroy(_root);
			_root = nullptr;
		}
		void InOrder()
		{
			_InOrder(_root);
		}
		bool Empty()
		{
			return _root == nullptr;
		}

		bool IsBalance()
		{

			int blackNum = 0;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_color == BLACK)blackNum++;
				cur = cur->_right;
			}
			return _IsBalance(_root, blackNum, 0);
		}
		void swap( RBTree& t)
		{
			std::swap(_root, t._root);
		}
		int size()
		{
			return _size;
		}
	private:
		void Destroy(Node* root)
		{
			if (root == nullptr) return;

			Destroy(root->_left);
			Destroy(root->_right);

			delete root;
			root = nullptr;
		}
		Node* Copy(Node* root)
		{
			if (root == nullptr) return root;

			Node* newnode = new Node(root->_key, root->_value);

			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);

			return newnode;
		}
		bool _IsBalance(Node* root, int blackNum, int selfBlackNum)
		{
			if (root == nullptr)
			{
				if (blackNum != selfBlackNum)
				{
					cout << "Black number error, blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
					return false;
				}
				else
				{
					//cout << "blackNum: " << blackNum << " , selfBlackNum: " << selfBlackNum << endl;
					return true;
				}
			}

			if (root->_color == RED && root->_parent->_color == RED)
			{
				cout << "parent and cur is RED, key:" << root->_key << endl;
				return false;
			}

			if (root->_color == BLACK) selfBlackNum++;
			return _IsBalance(root->_left, blackNum, selfBlackNum) && _IsBalance(root->_right, blackNum, selfBlackNum);
		}

		void RotateR(Node* cur)
		{
			Node* parentOfcur = cur->_parent;
			Node* left = cur->_left;


			cur->_left = left->_right;
			if (left->_right)
				left->_right->_parent = cur;
			left->_right = cur;
			cur->_parent = left;
			if (parentOfcur == nullptr)
			{
				_root = left;
				left->_parent = nullptr;
			}
			else
			{

				if (parentOfcur->_left == cur)
				{
					parentOfcur->_left = left;
					left->_parent = parentOfcur;
				}
				else
				{
					parentOfcur->_right = left;
					left->_parent = parentOfcur;
				}
			}


		}

		void RotateL(Node* cur)
		{
			Node* parentOfcur = cur->_parent;
			Node* right = cur->_right;

			cur->_right = right->_left;
			if (right->_left)
				right->_left->_parent = cur;
			right->_left = cur;
			cur->_parent = right;


			if (parentOfcur == nullptr)
			{
				_root = right;
				right->_parent = nullptr;
			}
			else
			{
				if (parentOfcur->_right == cur)
				{
					parentOfcur->_right = right;
					right->_parent = parentOfcur;
				}
				else
				{
					parentOfcur->_left = right;
					right->_parent = parentOfcur;
				}
			}


		}

		void RotateRL(Node* cur)
		{

			Node* parentOfcur = cur->_parent;

			Node* right = cur->_right;
			Node* leftOfright = right->_left;

			RotateR(right);
			RotateL(cur);

		}

		void RotateLR(Node* cur)
		{
			Node* parentOfcur = cur->_parent;

			Node* left = cur->_left;
			Node* rightOfleft = left->_right;

			RotateL(left);
			RotateR(cur);

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

			_InOrder(root->_left);

			cout << root->_key << ":" << root->_value << endl;

			_InOrder(root->_right);

		}
		Node* _root = nullptr;
		int _size = 0;
	};

}

map.h

#pragma once
#include"RBTree.h"

namespace Mymap {
	using namespace Tree;

	template<class K, class V>
	class map
	{

		struct keyOfvalue {
			const K& operator()(const pair<const K, V>& data)
			{
				return data.first;
			}
		};
		typedef pair<const K, V> T;

		typedef RBTree<K, T ,keyOfvalue> Tree;
	public:
		typedef typename Tree::Iterator iterator;
		typedef typename Tree::const_Iterator const_iterator;
		typedef typename Tree::reverseIterator reverse_iterator;
		typedef typename Tree::const_reverseIterator const_reverse_iterator;

		pair<iterator,bool> insert(const T& data)
		{
			return 	_tr.Insert(data);
		}
		V& operator[](const K& key)
		{
			return (insert(make_pair(key, V())).first)->second;
		}
		void swap( map& t)
		{
			_tr.swap(t._tr);
		}
		iterator begin()
		{
			return _tr.Begin();
		}

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

		const_iterator cbegin()
		{
			return _tr.cBegin();
		}
		const_iterator cend()
		{
			return _tr.cEnd();
		}
		reverse_iterator rbegin()
		{
			return _tr.rBegin();
		}

		reverse_iterator rend()
		{
			return _tr.rEnd();
		}
		
		const_reverse_iterator crbegin()
		{
			return _tr.crBegin();
		}
		const_reverse_iterator crend()
		{
			return _tr.crEnd();
		}
		void clear()
		{
			_tr.Clear();
		}
		bool empty()
		{
			return _tr.Empty();
		}
		int size()
		{
			return _tr.size();
		}
	private:
		Tree _tr;
	};
}

set.h

#pragma once
#include"RBTree.h"

namespace Myset {
	using namespace Tree;

	template<class K>
	class set
	{

		struct keyOfvalue {
			 const K operator()(const K& key)
			 {
				 return key;
			 }
		};
		typedef RBTree<const K, const K, keyOfvalue> Tree;

	public:
		typedef typename Tree::Iterator iterator;
		typedef typename Tree::const_Iterator const_iterator;
		typedef typename Tree::reverseIterator reverse_iterator;
		typedef typename Tree::const_reverse_Iterator const_reverse_iterator;

		pair<iterator,bool> insert(const K& data)
		{
			return _tr.Insert(data);
			
		}
		void swap( set& t)
		{
			_tr.swap(t._tr);
		}
		iterator begin()
		{
			return _tr.Begin();
		}

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

		const_iterator cbegin()
		{
			return _tr.cBegin();
		}
		const_iterator cend()
		{
			return _tr.cEnd();
		}
		reverse_iterator rbegin()
		{
			return _tr.rBegin();
		}

		reverse_iterator rend()
		{
			return _tr.rEnd();
		}
		
		const_reverse_iterator crbegin()
		{
			return _tr.crBegin();
		}
		const_reverse_iterator crend()
		{
			return _tr.crEnd();
		}
		iterator find(const K& key)
		{
			return _tr.Find(key);
		}

		const_iterator find(const K& key) const
		{
			return _tr.Find(key);
		}
		int size()
		{
			return _tr.size();
		}
		void clear()
		{
			_tr.Clear();
		}
		bool empty()
		{
			return _tr.Empty();
		}
	private:
		 Tree _tr;
	};
}
# c++ # 开发语言 # linux # 数据结构
Logo
AI Agent技术社区

Agent 垂直技术社区，欢迎活跃、内容共建。

更多推荐

cover

【安心陪诊 Agent】老年陪诊需求分析：家属、老人、医生三方到底缺什么

avatar AI Agent技术社区
cover

生产级AI Agent系统架构实战，从模块拆解到代码落地与K8s部署

avatar AI Agent技术社区
cover

深度解耦的 AI 新生态：大模型上下文协议（MCP）全栈落地实战

avatar AI Agent技术社区