【C++】用红黑树封装set和map

9 阅读 0 评论 0 点赞

在C++标准库中，set容器和map容器的底层都是红黑树，它们的各种接口都是基于红黑树来实现的，我们在这篇文章中已经模拟实现了红黑树 ->【C++】红黑树，接下来我们在此红黑树的基础上来看看如何封装set和map。

一、共用一颗红黑树

我们在这篇文章中 ->【C++】set容器和map容器的基本使用，清楚set是key搜索场景的结构，map是key/value搜索场景的结构。所以要用红黑树封装它们两个就需要2棵红黑树，这两颗红黑树整体逻辑差不多一样，只是结点中的元素数据类型不一样，一个是K类型，一个是pair<K,V>类型。两棵极为相似的树，只是一点不同，如果实现两个会显得冗余，那么我们就可以考虑使用模板来将结点中的数据类型泛型化，使set和map底层共用一个红黑树。

我在先前的文章中已经实现了红黑树，它是解决key/value搜索场景的，我将那篇文章的源代码裁剪了一些重要的部分，大家这里只需看懂这部分的功能：

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;	
	Colour _col;

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

template<class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
				parent = cur,cur = cur->_right;
			else if (cur->_kv.first > kv.first)
				parent = cur,cur = cur->_left;
			else
				return false;
		}

		cur = new Node(kv);
		cur->_col = RED; 
		if (parent->_kv.first < kv.first)
			parent->_right = cur;
		else
			parent->_left = cur;
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;

			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK; 
						grandfather->_col = RED;
					}
					else 
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;  
						grandfather->_col = RED;
					}
					break; 
				}
			}
			else  
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else 
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
private:
	Node* _root = nullptr; 
};

此时，结点中数据类型是pair，这样我们就把这个结点的数据类型写"死"了，set容器底层就不能用这个红黑树，我们要实现set和map共用一棵红黑树，所以就需要把结点的数据类型泛型化(根据传来的类型来确定具体的类型)：

template<class T>  //如果是set就传K，如果是map就传pair<K,V>
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)
	{}
};

那么，RBTree也要跟着改：

template<class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	bool Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return true;
		}

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

		cur = new Node(data);
		cur->_col = RED; 
		if (parent->_data.first < data.first)
			parent->_right = cur;
		else
			parent->_left = cur;
		cur->_parent = parent;

		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;

			if (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK; 
						grandfather->_col = RED;
					}
					else 
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;  
						grandfather->_col = RED;
					}
					break; 
				}
			}
			else  
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else 
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return true;
	}
private:
	Node* _root = nullptr; 
};

封装set：

//MySet.h
#include "RBTree.h"
namespace blue
{
	template<class K>
	class set
	{
	public:
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K> _t;
	};
}

封装map：

//MyMap.h
#include "RBTree.h"
namespace blue
{
	template<class K,class V>
	class map
	{
	public:
		bool insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RBTree<pair<K, V>> _t;
	};
}

这样我们就可以通过模板参数T来控制set和map共用一棵红黑树了！

二、红黑树中Insert带来的问题

通过观察上面红黑中Insert中的代码，其实会有问题：

我们的data可能是K类型，也可能是pair<K,V>类型。如果是后者，那么这样比较当然没问题，那如果是前者，就不能这样比较，所以我们要对这个部分进行修改。

怎么修改呢？去掉.first吗？

我们如果去掉.first，那么不管是K还是pair<K,V>都可以进行比较，以pair<K,V>类型为例，两个pair类型进行比较时先比较K，如果K相同则比较V，这与我们的本意相违背，我们的要求是只比较K的值，不能让V的值参与比较！所以我们要解决问题，不能仅仅是去掉.first。

我们可以在set和map类中写一个仿函数，通过仿函数来获取K，具体做法如下：

#include "RBTree.h"
namespace blue
{
	template<class K>
	class set
	{
		struct KeyOfSet
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};

	public:
		bool insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K,KeyOfSet> _t;
	};
}

#include "RBTree.h"
namespace blue
{
	template<class K,class V>
	class map
	{
		struct KeyOfMap
		{
			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<pair<K, V>,KeyOfMap> _t;
	};
}

这时我们就需要在红黑树中加一个模板参数：

我们明确知道map是需要这个仿函数来获取K值的，但是在set中也写一个仿函数来获取K值，有人开始会觉得这是多余的，因为set中的元素类型本身就是K类型，但是不要忽略一点，set和map是共用同一份模板的，map需要这个仿函数，那么set也必须有这个仿函数，set这里的仿函数就是为了兼容map，这时，红黑树的第二个模板参数KeyOfT就出现了。

三、erase和find带的来问题

我们知道set容器和map容器都有erase和find接口，这两个接口都是根据K值来进行的，如果我们要在红黑树中实现这两个接口那么必须知道K的值，我们根据K的值来进行删除和查找。但是现在，我们自己实现的这个红黑树中并没有办法拿到K的值，也就是说在我们目前这棵红黑树中若要实现erase和find是做不到的！

为了获取K的值，我们可以在RBTree中再添加一个模板参数K，专门用来获取K的值：

在set中：

在map中：

其实，这里的set中传了两个K，第一个K就是兼容map的。因为map需要这个K，那么在TRBTree中就必须增加一个模板参数，所以set就必须传一个K。

那么在RBTree中erase和find接口就可以这样写：

bool find(const K& key)
{
	//...
}

bool erase(const K& key)
{
	//...
}

四、迭代器

红黑树的迭代器和我们在模拟实现list时思路是一样的，因为红黑树的底层空间是不连续的，所以我们不能直接"typedef Node* iterator"，我们要单独用一个类型封装结点的指针，再通过重载运算
符实现，让迭代器具有像指针一样访问的行为：

//Ref和Ptr是为了兼容普通迭代器和const迭代器
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node; //当前结点指针
	RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &(_node->_data);
	}
	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

因为set和map都是双向迭代器，所以它们的迭代器应该要支持++和--操作，由于它们的迭代器是复用红黑树的，所以红黑树中的迭代器也要实现++和--操作，list迭代器的++或--操作实现起来非常简单，只需利用next指针就好；反观红黑树，它的++/--操作要求必须满足中序遍历规则，红黑树的中序遍历是有序的，假设某棵红黑树的中序遍历是"1 3 5 6 7 9" ，如果迭代器在3这个位置，那么++后就必须到5，--后就必须到1。迭代器++的核心逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。

那么如何实现++操作呢？(分为以下几种情况)

假设当前迭代器"指向"cur位置，cur的父结点为parent。

1、cur的右子树存在

++后，只需找到右子树的最左结点即可。

2、cur的右子树为空

(1)cur是parent的左孩子

直接返回parent。(此时parent就是我们需要找的结点)

(2)cur是parent的右孩子

说明以parent为根的子树已经遍历完了，接下来让cur=parent，parent=cur->_parent，然后在做判断。最坏情况下，cur = _root，parent=nullptr，这时直接返回parent即可，我们这里让结束位置为nullptr。

代码实现：

Self& operator++()
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_right)  //右子树不为空，找右子树的最左结点
		{
			cur = cur->_right;
			while (cur->_left)
				cur = cur->_left;
			_node = cur;
		}
		else
		{
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
            //直到cur是parent的左，那么parent就是我们的目标   
            //极端情况下，parent走到nullptr，这说明整棵树已经访问完了，直接返回nullptr(parent)
			_node = parent;
		}
		return  *this;

	}

那么如何实现--操作呢？(分为以下几种情况)

迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为它访问顺序是右子树->根结点->
左子树。

假设当前迭代器"指向"cur位置，cur的父结点为parent。

1、cur的左子树存在

--后，只需找到左子树的最右结点即可。

2、cur的左子树为空

(1)cur是parent的右孩子

直接返回parent。(此时parent就是我们需要找的结点)

(2)cur是parent的左孩子

说明以parent为根的子树已经遍历完了，接下来让cur=parent，parent=cur->_parent，然后在做判断。

代码实现：

Self& operator--()
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_left) //左子树不为空，找左子树的最右结点
		{
			cur = cur->_left;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
		}
		else
		{
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的右，那么parent就是我们的目标   
			_node = parent;
		}
		return *this;
	}

完成这一步，我们迭代器的封装任务差不多已经完成了，接下来我们需要在红黑树中实现Begin和End：

public:
    typedef RBTreeIterator<T, T&, T*> Iterator;  //普通迭代器
    typedef RBTreeIterator<T, const T&,const T*> ConstIterator; //const迭代器

    Iterator Begin()
    {
	    Node* cur = _root;
	    while (cur->_left)
	    	cur = cur->_left;
    	return Iterator(cur);
    }
    Iterator End()
    {
    	return Iterator(nullptr);  //我们这里让nullptr当最终结点
    }

    ConstIterator Begin() const
    {
	    Node* cur = _root;
	    while (cur->_left)
		    cur = cur->_left;
	    return ConstIterator(cur);
    }
    ConstIterator End() const
    {
	    return ConstIterator(nullptr);
    }

在set中：

public:
	typedef typename RBTree<K, K, KeyOfSet>::Iterator iterator;
	typedef typename RBTree<K, K, KeyOfSet>::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();
	}

在map中：

public:
	typedef typename RBTree<K, pair<K, V>, KeyOfMap>::Iterator iterator;
	typedef typename RBTree<K, pair<K, V>, KeyOfMap>::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();
	}

我们大致的任务已经完成了，接下来我们来写一段代码验证一下(看看是否会出现错误)：

//Test.cpp
#include "MyMap.h"
#include "MySet.h"

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

	blue::set<int>::iterator sit = s.begin();
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;
}

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

	blue::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

int main()
{
	TestSet();
	cout << "-----------------------" << endl;
	TestMap();
	return 0;
}

运行结果：

运行结果暂时没有什么问题。

这里有一个bug，看下面测试代码：

void Print(const blue::set<int>& s)
{
	bit::set<int>::const_iterator it = s.end();
	while (it != s.begin())
	{
		--it;
		cout << *it << " ";
	}
	cout << endl;
}

我们上面将end()指向nullptr，那么如果逆向遍历，--it就会出现错误，所以我们在--it时先判断一下，如果指向空，那么就修改_node为红黑树的最后一个结点，那么，问题又来了，怎么获得最后一个结点呢？所以我们需要知道红黑树的头结点，所以，我们在RBTreeIterator这个类中还需要一个成员变量来记录根节点：

修改operator--如下：

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

		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_left) //左子树不为空，找左子树的最右结点
		{
			cur = cur->_left;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
		}
		else
		{
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的右，那么parent就是我们的目标   
			_node = parent;
		}
		return *this;
	}

解决完上述问题，还有一个问题，set和map中的K的值是不允许修改的，因为若修改就可能会破坏红黑树的结构，但我们写的代码中通过普通迭代器是能够修改的，如果要解决可以这样修改：

在set中：

在map中：

五、[]

好了，好了，到这里我们将上面的坑都踩完了，接下来最后最后一个功能，也是比较重要的，就是处理map中[]的实现逻辑：

map中的[]的逻辑其实就是利用了insert接口。

我们在红黑树中实现Insert的返回值是bool，接下来我们将它改为pair<Iterator,bool>类型：

pair<Iterator,bool> Insert(const T& data)
{
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		//return true;
		return { Iterator(_root, _root),true };
	}
	Node* parent = nullptr;
	Node* cur = _root;
	KeyOfT kot;
	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;
			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 (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_left)
				{
					RotateR(grandfather);
					parent->_col = BLACK; 
					grandfather->_col = RED;
				}
				else 
				{
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;  
					grandfather->_col = RED;
				}
				break; 
			}
		}
		else  
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else 
				{
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	//return true;
	return { Iterator(newnode, _root),true };
}

完成对Insert的调整后，在set和map的insert也要跟着调：

在set中：

在map中：

接下来，我们就着手实现[]，在map中：

V& operator[](const K& key)
{
	pair<iterator, bool> ret = _t.Insert({ key,V() });
	return (ret.first)->second;
}

是不是非常简单！

六、其他问题

1、构造函数

RBTree() = default;

2、拷贝构造

RBTree(const RBTree<K, T, KeyOfT>& t)
{
	_root = Copy(t._root);
}

Node* Copy(Node* root)
{
	if (root == nullptr)
		return nullptr;
	Node* newnode = new Node(root->_data);
	newnode->_left = Copy(root->_left);
	newnode->_right = Copy(root->_right);

	return newnode;
}

3、赋值重载

RBTree& operator=(RBTree tmp)
{
	swap(tmp._root);
	return *this;
}

4、析构函数

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

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

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

七、源码

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


//Ref和Ptr是为了兼容普通迭代器和const迭代器
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node; //当前结点指针
	Node* _root; //记录红黑树的根结点
	RBTreeIterator(Node* node,Node* root)
		:_node(node)
		,_root(root)
	{}

	Self& operator++() 
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_right)   //右子树不为空，找右子树的最左结点
		{
			cur = cur->_right;
			while (cur->_left)
				cur = cur->_left;
			_node = cur;
		}
		else
		{
			while (parent && parent->_right == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的左，那么parent就是我们的目标   
			//极端情况下，parent走到nullptr，这说明整棵树已经访问完了，直接返回nullptr(parent) 
			_node = parent;
		}
		return  *this;
	}

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

		Node* cur = _node;
		Node* parent = cur->_parent;
		if (cur->_left) //左子树不为空，找左子树的最右结点
		{
			cur = cur->_left;
			while (cur->_right)
				cur = cur->_right;
			_node = cur;
		}
		else
		{
			while (parent && parent->_left == cur)
			{
				cur = parent;
				parent = cur->_parent;
			}
			//直到cur是parent的右，那么parent就是我们的目标   
			_node = parent;
		}
		return *this;
	}

	Ref operator*() const
	{
		return _node->_data;
	}
	Ptr operator->() const
	{
		return &(_node->_data);
	}
	bool operator==(const Self& s) const
	{
		return _node == s._node;
	}
	bool operator!=(const Self& s) const
	{
		return _node != s._node;
	}
};



template<class K,class T,class KeyOfT>
class RBTree
{
public:
	RBTree() = default;
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}
	RBTree& operator=(RBTree tmp)
	{
		swap(tmp._root);
		return *this;
	}
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
	
public:
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, T&, T*> Iterator;
	typedef RBTreeIterator<T, const T&,const T*> ConstIterator;

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

	ConstIterator Begin() const
	{
		Node* cur = _root;
		while (cur->_left)
			cur = cur->_left;
		return ConstIterator(cur,_root);
	}
	ConstIterator End() const
	{
		return ConstIterator(nullptr,_root);
	}

public:
	pair<Iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			//return true;
			return { Iterator(_root,_root),true };
		}
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfT kot;
		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;
				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 (parent == grandfather->_left)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK; 
						grandfather->_col = RED;
					}
					else 
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;  
						grandfather->_col = RED;
					}
					break; 
				}
			}
			else  
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else 
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		//return true;
		return { Iterator(newnode,_root),true };
	}


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

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

			Node* pParent = parent->_parent;

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

			if (parent == _root)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (pParent->_left == parent)
					pParent->_left = subL;
				else
					pParent->_right = subL;

				subL->_parent = pParent;
			}
		}
		void RotateL(Node* parent)
		{
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			parent->_right = subRL;
			if (subRL)
				subRL->_parent = parent;

			Node* parentParent = parent->_parent;
			subR->_left = parent;
			parent->_parent = subR;
			if (parentParent == nullptr)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (parent == parentParent->_left)
					parentParent->_left = subR;
				else
					parentParent->_right = subR;
				subR->_parent = parentParent;
			}
		}

		Node* Copy(Node* root)
		{
			if (root == nullptr)
				return nullptr;
			Node* newnode = new Node(root->_data);
			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);

			return newnode;
		}

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

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}
private:
	Node* _root = nullptr; 
};

(2)MySet.h

#pragma once
#include "RBTree.h"
namespace blue
{
	template<class K>
	class set
	{
		struct KeyOfSet
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, const K, KeyOfSet>::Iterator iterator;
		typedef typename RBTree<K, const K, KeyOfSet>::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();
		}

	public:
		pair<iterator,bool> insert(const K& key)
		{
			return _t.Insert(key);
		}
	private:
		RBTree<K, const K, KeyOfSet> _t;
	};
}

(3)MyMap.h

#pragma once
#include "RBTree.h"
namespace blue
{
	template<class K,class V>
	class map
	{
		struct KeyOfMap
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::Iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, KeyOfMap>::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();
		}

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

		V& operator[](const K& key)
		{
			pair<iterator, bool> ret = _t.Insert({ key,V() });
			return (ret.first)->second;
		}

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

(4)Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include "MyMap.h"
#include "MySet.h"

void Print(const blue::set<int>& s)
{
	blue::set<int>::const_iterator it = s.end();
	while (it != s.begin())
	{
		--it;
		cout << *it << " ";
	}
	cout << endl;
}

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

	blue::set<int>::iterator sit = s.begin();
	//*sit += 10;
	while (sit != s.end())
	{
		cout << *sit << " ";
		++sit;
	}
	cout << endl;


	Print(s);

}

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

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

	blue::map<string, string>::iterator it = dict.begin();
	while (it != dict.end())
	{
		// 不能修改first，可以修改second
		//it->first += 'x';
		it->second += 'x';

		cout << it->first << ":" << it->second << endl;
		++it;
	}
	cout << endl;
}

int main()
{
	TestSet();
	cout << "-----------------------" << endl;
	TestMap();
	return 0;
}

八、总结

本篇内容到这里就结束啦，主要讲了如何用红黑树来封装set和map容器，希望对大家有帮助，祝生活愉快！

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 【C++】用红黑树封装set和map

点赞(0) 打赏

本文分类：文章资讯
本文标签：【C++】用红黑树封装set和map
浏览次数：9 次浏览
本文链接：https://freeymw.com/article/36855.html

评论列表共有 0 条评论

暂无评论

【C++】用红黑树封装set和map

一、共用一颗红黑树

二、 红黑树中Insert带来的问题

三、erase和find带的来问题

四、迭代器

五、[]

六、其他问题

1、构造函数

2、拷贝构造

3、赋值重载

4、析构函数

七、源码

八、总结

评论列表 共有 0 条评论

发表评论 取消回复

二、红黑树中Insert带来的问题

评论列表共有 0 条评论

发表评论取消回复