红黑树模拟实现map与set

admin2024-05-15  1

目录

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 库里的做法

红黑树模拟实现map与set,第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的改造 

红黑树模拟实现map与set,第2张

节点的定义 

红黑树模拟实现map与set,第3张

2. 红黑树的迭代器 

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

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

库里的红黑树。

红黑树模拟实现map与set,第4张 迭代器中的方法

红黑树模拟实现map与set,第5张

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

迭代器的实现 

迭代器的定义

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

红黑树模拟实现map与set,第6张

迭代器的方法实现 

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

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

红黑树模拟实现map与set,第7张 代码展示 
红黑树迭代器实现 
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;
	//}
}
测试结果 

红黑树模拟实现map与set,第8张

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!