红黑树模拟实现map与set

目录

1.红黑树的泛型

1.1 库里的做法

1.2 我们的模拟实现 

map部分实现

红黑树部分区域的改造

insert与find的改造 

节点的定义 

2. 红黑树的迭代器 

库里的红黑树。

​编辑 迭代器中的方法

迭代器的实现 

迭代器的定义

迭代器的方法实现 

​编辑 代码展示 

红黑树迭代器实现 

树内实现begin，end 

map与set封装 

测试代码 

测试结果 

---

我们都知道map与set的顶层结构是红黑树，那么究竟是怎样实现的呢？

map内存储的是键值对，而set存储的是key，红黑树只有一份，那么是怎么做到既可以存储键值对，又可以存储key的呢？

map与set都需要迭代器，那么他们的迭代器又是如何形成的？

1.红黑树的泛型

将红黑树实现为泛型编程，在map与set内对其进行封装，传入不同的数据类型。

1.1 库里的做法

看完了上面的分析图，我们会发现RBTree模板参数的第一个好像没有什么作用，还留着它干嘛？

不要忘了诸如find方法的存在，他们是依据关键值进行索引的，直接传入key会很方便。当然要在调用find的时候，把map键值对中的key取出来也未尝不可。

1.2 我们的模拟实现 

map部分实现

#include"RBTree.h"

template<class K,class V>
class mymap
{
	struct MapKeyOfT//传入红黑树的取关键值的仿函数
	{
		const K& operator()(const pair<K,V>& kv)
		{
			return kv.first;
		}
	};
	typedef RBTree < K,  pair<K,V>, MapKeyOfT > RBTree;
public:
	//这里的代码完全复用红黑树
	bool insert(const pair<K, V>& kv)
	{
		return _t.insert(kv);
	}
	bool find(const K& kv)
	{
		return _t.Find(kv);
	}
	size_t size()
	{
		return _t.size();
	}
	size_t Hight()
	{
		return _t.Height();
	}
	void Inorder()
	{
		 _t.InOrder();
	}
private:
	RBTree _t;//封装红黑树
};

void TestMap()//测试代码
{
	int arr[] = { 1,6,2,7,9,1,2,531,5,3,47,3,8,8365,9 };
	mymap<int, int> ma;
	for (auto e : arr)
	{
		ma.insert(make_pair(e, e));
	}
	if (ma.find(9))
		cout << "FIND TRUE" << endl;
	else
		cout << "FIND FALSE!" << endl;
	ma.Inorder();
	cout << "Height: " << ma.Hight() << endl;
	cout << "size: " << ma.size() << endl;;
}

set部分实现 

#include"RBTree.h"

template<class K>
class myset
{
	struct SetKeyOfT
	{
		const K& operator()(const K& k) 
		{
			return k;
		}
	};
	typedef RBTree<K, K, SetKeyOfT> RBTree;
public:
	bool insert(const K& kv)
	{
		return _t.insert(kv);
	}
	bool find(const K& kv)
	{
		return _t.Find(kv);
	}
	size_t size()
	{
		return _t.size();
	}
	size_t Hight()
	{
		return _t.Height();
	}
	void Inorder()
	{
		_t.InOrder();
	}
private:
	RBTree _t;
};

void TestSet()
{
	int arr[] = { 1,6,2,7,9,1,2,531,5,3,47,3,8,8365,9 };
	myset<int> se;
	for (auto e : arr)
	{
		se.insert(e);
	}
	if (se.find(9))
		cout << "FIND TRUE" << endl;
	else
		cout << "FIND FALSE!" << endl;
	se.Inorder();
	cout << "Height: " << se.Hight() << endl;
	cout << "size: " << se.size() << endl;;
}

红黑树部分区域的改造

我们在红黑树区域的改造主要是红黑树存储的数据类型改为模板，在insert与find中需要取存储类型的关键值key。

insert与find的改造 

节点的定义 

2. 红黑树的迭代器 

我们知道，c++的容器都是支持迭代器的，并且迭代器无论底层是怎样的，对于我们而言所有的迭代器用法相同，这就需要在底层对迭代器进行处理。

我们之前学习的string，其迭代器就是原生指针，链表的迭代器是对节点的指针进行封装，然后赋予其行为。这里红黑树的迭代器也不外乎如此。 

库里的红黑树。

 迭代器中的方法

我们来试试实现红黑树的迭代器，让map与set也支持迭代器吧！ 

迭代器的实现 

迭代器的定义

迭代器是对节点进行直接操作，因此这里的迭代器只需要封装节点的指针就可以了。

迭代器的方法实现 

方法实现中唯一需要探究的就是++，那么红黑树到底是如何实现++的呢？

这里理所当然是以中序遍历为基础，我们看看中序遍历是如何++，--的。

 代码展示 

红黑树迭代器实现 

template<class T, class REF, class PTR>
class RBTree_iterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTree_iterator<T, REF, PTR> self;
public:
	RBTree_iterator() {}
	RBTree_iterator(T& x)
	{
		_node(x);
	}
	RBTree_iterator(Node* node)
		:_node(node)
	{}
	REF operator*()
	{
		return _node->_kv;
	}
	PTR operator->()
	{
		return &_node->_kv;
	}
	self& operator++()//后置
	{
		increment();//增加的方法
		return *this;
	}
	self operator++(int)
	{
		self tmp = *this;
		increment();
		return tmp;
	}
	self& operator--()//后置
	{
		decrement();
		return *this;
	}
	self operator--(int)
	{
		self tmp = *this;
		decrement();
		return tmp;
	}
	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	bool operator==(const self& s)//直接以指针比较
	{
		return _node == s._node;
	}
private:
	void increment()//向前走
	{
		Node* cur = _node;
		if (cur->_right)
		{
			cur = cur->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			Node* parent = cur->_parent;
			while (parent && cur != parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		
	}
	void decrement()//向后退
	{
		Node* cur = _node;
		if (cur->_left)
		{
			cur = cur->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur;
		}
		else
		{
			Node* parent = cur->_parent;
			while (parent && cur != parent->right)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
	}
private:
	Node* _node;
};

树内实现begin，end 

typedef RBTree_iterator<T, T&, T*> iterator;
typedef RBTree_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
	Node* cur = GetLeft();
	return iterator(cur);
}
iterator end()
{
	return iterator(nullptr);
}
const_iterator begin() const
{
	Node* cur = GetLeft();
	return iterator(cur);
}
const_iterator end() const
{
	return iterator(nullptr);
}

map与set封装 

typedef typename RBTree::iterator iterator;//typename声明后面是一个类型，与class的唯一区别
typedef typename RBTree::const_iterator 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();
}

typedef typename RBTree::iterator iterator;//typename声明后面是一个类型，与class的唯一区别
typedef typename RBTree::const_iterator 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();
}

同时这里要对insert与find的返回值改造，使其与库中相似。 

测试代码 

void Test_Set_Iterator()
{
	int arr[] = { 34,123,6,431,46,4,7,246,54,7,8,234,65,48,57,9,2,46,5,8756,254,67,95,2 };
	myset<int> se;
	for (auto e : arr)
	{
		auto ret=se.insert(e);
		if (ret.second)
			cout << "插入成功" << " ";
		else
			cout << " 插入失败" << " ";
	}
	cout << endl;
	auto re = se.find(9);
	cout << "找到了\t" << *re << endl;
	myset<int>::iterator it = se.begin();
	while (it != se.end())
	{
		cout << *it << endl;
		it++;
	}
	//cout << endl;
	//for (auto e : se)
	//{
	//	cout << e << endl;
	//}
}

测试结果 

写代码的时候一定要思路清晰，一部分一部分实现，先实现框架，再慢慢填充细节。