【C++】使用红黑树进行封装map和set-Toy模板网

这篇具有很好参考价值的文章主要介绍了【C++】使用红黑树进行封装map和set。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🌇个人主页：平凡的小苏
📚学习格言：命运给你一个低的起点，是想看你精彩的翻盘，而不是让你自甘堕落，脚下的路虽然难走，但我还能走，比起向阳而生，我更想尝试逆风翻盘。
🛸C++专栏：C++内功修炼基地
> 家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路过的友友麻烦多多点赞关注。欢迎你们的私信提问，感谢你们的转发！关注我，关注我，关注我，你们将会看到更多的优质内容！！

一、STL库中的set和map源码

本文难点：使用红黑树封装set和map，必须保证两种数据结构复用同一棵红黑树；且满足set和map的性质，set的value不可被改变，而map的value可以被改变。

【C++】使用红黑树进行封装map和set,C++修炼内功,c++,开发语言

二、利用模板区分map和set

template<class T>
struct RedBlackTreeNode
{
	T _data;
	RedBlackTreeNode<T>* _left;//该节点的左孩子
	RedBlackTreeNode<T>* _right;//该节点的右孩子
	RedBlackTreeNode<T>* _parent;//该节点是父亲节点
	Color _col;

	RedBlackTreeNode(const T& data)
		: _data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

map和set的区别在于value的不同，红黑树模板参数T，代表value用以区分set和map。

三、利用仿函数比较大小

我们会发现红黑树的插入等接口会对key值进行比较大小，像set直接对key进行比较，这没问题，但是map中的节点装的是pair<K,V>,pair的比较规则是first比完之后可能会再去比较second（而我们仅仅想要比较first，该比较规则不适用）。

通过源码启发，我们可以对红黑树新增一个模板参数：
仿函数KeyOfT，在set和map类中完善该仿函数的比较对象，
用于区分set和map的比较：

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

struct SetKeyOfT
{
    const K& operator()(const K& key)
    {
        return key;
    }
};

注：这里为什么只是返回key的数值，而不是在仿函数里面进行比较大小呢？

因为我们调用find的函数的时候不是传入两个数值进行比较的，而只是传一个。

使用红黑树封装的find

Node* Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

四、set和map的迭代器

STL源码采用下图结构，多搞了一个头结点。迭代器begin()可以指向header的左，迭代器end()指向header。

【C++】使用红黑树进行封装map和set,C++修炼内功,c++,开发语言

而小编使用的是无头结点进行封装的map和set，将nullptr作为结束

1、红黑树的begin()和end()

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

    return iterator(leftMin);
}

iterator end()
{
    return iterator(nullptr);
}

const_iterator begin() const
{
    Node* leftMin = _root;
    while (leftMin && leftMin->_left)
    {
        leftMin = leftMin->_left;
    }

    return const_iterator(leftMin);
}

const_iterator end() const
{
    return const_iterator(nullptr);
}

封装了const是为了适配const的map和set

2、operator++

1、如果_node的右不为空，找右孩子的最左节点

2、如果_node的右为空，如果孩子是父亲的左就返回父亲，否则就继续向上遍历，如果走到nullptr那就是遍历完成

Self& operator++()
{
    if (_node->_right)
    {
        Node* subleft = _node->_right;
        while (subleft->_left)
        {
            subleft = subleft->_left;
        }

        _node = subleft;
    }
    else
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right)//parent不为空
        {
            cur = parent;
            parent = parent->_parent;
        }
        _node = parent;
    }
    return *this;
}

3、operator–

1、如果_node的左不为空，找左孩子的最右节点

2、如果_node的左为空，如果孩子是父亲的右就返回父亲，否则就继续向上遍历，如果走到nullptr那就是遍历完成

Self& operator--()
{
    if (_node->_left)
    {
        Node* subright = _node->_left;
        while (subright->_right)
        {
            subright = subright->_right;
        }

        _node = subright;
    }
    else
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left)
        {
            cur = parent;
            parent = parent->_parent;
        }

        _node = parent;
    }
    return *this;
}

五、set的迭代器

对于set和map，它们的key都是不能改的。set的value不能修改，map的value可以修改。

因为set的value是不能改的，所以它的底层将普通迭代器和const迭代器全部封装成const迭代器来“解决”：

//注意这里是const_iterator变为iterator，在插入的时候会出现问题
typedef typename RedBlackTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RedBlackTree<K, K, SetKeyOfT>::const_iterator const_iterator;

这里iterator使用了const 的迭代器后，begin()和end()后面都需要加上const来解决问题；

iterator begin()const
{
    return _t.begin();
}
iterator end()const
{
    return _t.end();
}

这时使用迭代器调用上方函数会发现红黑树返回了普通迭代器类型的迭代器，类型不匹配。

在红黑树中补齐const版本的迭代器函数解决：

const_iterator begin() const
{
    Node* leftMin = _root;
    while (leftMin && leftMin->_left)
    {
        leftMin = leftMin->_left;
    }

    return const_iterator(leftMin);
}

const_iterator end() const
{
    return const_iterator(nullptr);
}

六、map的迭代器

map的value是可以改的，所以需要分别设计普通迭代器和const迭代器

typedef typename RedBlackTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RedBlackTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

iterator begin()
{
    return _t.begin();
}

iterator end()
{
    return _t.end();
}

const_iterator begin() const
{
    return _t.begin();
}

七、迭代器的拷贝构造

STL库中的普通迭代器都可以转换为const迭代器，这是迭代器类的拷贝构造所支持的。

这个拷贝构造有点特殊：

struct __TreeIterator
{
	typedef RedBlackTreeNode<T> Node;
	Node* _node;
	typedef __TreeIterator<T,Ref,Ptr> Self;
	typedef __TreeIterator<T, T&, T*> iterator;

	__TreeIterator(const iterator& it)
		:_node(it._node)
	{}

	__TreeIterator(Node* node)
		:_node(node)
	{}
}

1、当这个模板的的Ref和PTR被实例化为T&和T*时，__RBTreeIterator(const iterator& it)就是一个拷贝构造(没啥意义)

2、当这个模板的的Ref和PTR被实例化为const T&和const T*时，__RBTreeIterator(const iterator& it)就是一个构造函数，

支持用普通迭代器去构造const迭代器。此时const迭代器的拷贝构造函数则由编译器自动生成，刚好满足迭代器值拷贝的特点。文章来源地址https://www.toymoban.com/news/detail-729431.html

八、源码

1、set.h

#include "9.14RedBlackTree.h"

namespace sqy
{
	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RedBlackTree<K, K, SetKeyOfT>::const_iterator iterator;//注意这里是const_iterator变为iterator，在插入的时候会出现问题
		typedef typename RedBlackTree<K, K, SetKeyOfT>::const_iterator const_iterator;

		pair<iterator,bool> insert(const K& key)
		{
			pair<typename RedBlackTree<K, K, SetKeyOfT>::iterator,bool> ret = _t.Insert(key);//这里调用insert返回的是普通迭代器
			return pair<iterator, bool>(ret.first, ret.second);//这里需要用普通迭代器拷贝构造const的迭代器
		}
		iterator begin()const 
		{
			return _t.begin();
		}

		iterator end() const
		{
			return _t.end();
		}

	private:
		RedBlackTree<K, K, SetKeyOfT> _t;
	};
}

2、map.h

#include "9.14RedBlackTree.h"
namespace sqy
{
	template<class K,class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RedBlackTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RedBlackTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		const_iterator begin() const
		{
			return _t.begin();
		}

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

		const_iterator end()const
		{
			return _t.end();
		}
		pair<iterator,bool> insert(const pair<K,V>& kv)
		{
			return _t.Insert(kv);
		}
	private:
		RedBlackTree<K, pair<const K,V>, MapKeyOfT> _t;
	};
}

3、RedBlackTree.h

#include <iostream>
#include <cassert>
using namespace std;

enum Color
{
	RED,
	BLACK
};


template<class T>
struct RedBlackTreeNode
{
	T _data;
	RedBlackTreeNode<T>* _left;//该节点的左孩子
	RedBlackTreeNode<T>* _right;//该节点的右孩子
	RedBlackTreeNode<T>* _parent;//该节点是父亲节点
	Color _col;

	RedBlackTreeNode(const T& data)
		: _data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

template<class T,class Ref,class Ptr>
struct __TreeIterator
{
	typedef RedBlackTreeNode<T> Node;
	Node* _node;
	typedef __TreeIterator<T,Ref,Ptr> Self;
	typedef __TreeIterator<T, T&, T*> iterator;

	__TreeIterator(const iterator& it)
		:_node(it._node)
	{}

	__TreeIterator(Node* node)
		:_node(node)
	{}

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

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

	Self& operator++()
	{
		if (_node->_right)
		{
			Node* subleft = _node->_right;
			while (subleft->_left)
			{
				subleft = subleft->_left;
			}

			_node = subleft;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)//parent不为空
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}

		return *this;
	}

	Self& operator--()
	{
		if (_node->_left)
		{
			Node* subright = _node->_left;
			while (subright->_right)
			{
				subright = subright->_right;
			}

			_node = subright;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
		}

		return *this;
	}

	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 RedBlackTree
{
	typedef RedBlackTreeNode<T> Node;
public:
	typedef __TreeIterator<T, T&, T*> iterator;
	typedef __TreeIterator<T, const T&, const T*> const_iterator;

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

		return iterator(leftMin);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	const_iterator begin() const
	{
		Node* leftMin = _root;
		while (leftMin && leftMin->_left)
		{
			leftMin = leftMin->_left;
		}

		return const_iterator(leftMin);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}
	Node* Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		while (cur)
		{
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}
	pair<iterator,bool> Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}
		KeyOfT kot;
		Node* cur = _root;
		Node* parent = nullptr;
		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 make_pair(iterator(cur), false);
			}
		}

		cur = new Node(data);
		Node* newnode = cur;
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}

		cur->_parent = parent;

		// ... 控制平衡
		while (parent && parent->_col == RED)//parent不为空并且为红进循环
		{
			Node* grandfather = parent->_parent;
			if (grandfather->_left == parent)
			{
				if (parent->_left == cur)
				{
					Node* uncle = grandfather->_right;
					if (uncle && uncle->_col == RED)//叔叔节点为红
					{
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else //叔叔节点为空或者为黑的情况
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
				}
				else
				{
					Node* uncle = grandfather->_right;
					if (uncle && uncle->_col == RED)//叔叔存在并且叔叔节点为红
					{
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else //叔叔节点为空或者为黑的情况
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
				}
			}
			else
			{
				if (parent->_right == cur)
				{
					Node* uncle = grandfather->_left;
					if (uncle && uncle->_col == RED)//叔叔节点为红
					{
						parent->_col = uncle->_col = BLACK;
						grandfather->_col = RED;
						cur = grandfather;
						parent = cur->_parent;
					}
					else //叔叔节点为空或者为黑的情况
					{
						RotateL(grandfather);
						parent->_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 //叔叔节点为空或者为黑的情况
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
						break;
					}
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newnode), true);
	}

	bool IsBalance()
	{
		return _IsBalance(_root);
	}
private:
	bool checkColour(Node* root, int blacknum, int beachmark)
	{
		if (root == nullptr)
		{
			if (blacknum != beachmark)
			{
				return false;
			}
			return true;
		}

		if (root->_col == BLACK)
		{
			++blacknum;
		}

		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
		{
			cout << root->_kv.first << "出现连续红色节点" << endl;
			return false;
		}

		return checkColour(root->_left, blacknum, beachmark) && 
				checkColour(root->_right, blacknum, beachmark);
	}
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		if (root->_col != BLACK)
		{
			return false;
		}

		//基准值
		int beanchmark = 0;
		Node* cur = root;
		while (cur)
		{
			if (cur->_col == BLACK)
			{
				++beanchmark;
			}
			cur = cur->_left;
		}

		return checkColour(root, 0, beanchmark);
	}
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curRight = cur->_right;

		parent->_left = curRight;
		cur->_right = parent;
		Node* ppNode = parent->_parent;
		if (curRight)
		{
			curRight->_parent = parent;
		}

		parent->_parent = cur;

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

	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;

		parent->_right = curleft;
		if (curleft)//判断是否为空，空的话就不用接上父亲节点
		{
			curleft->_parent = parent;
		}

		cur->_left = parent;

		Node* ppnode = parent->_parent;

		parent->_parent = cur;


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

			}

			cur->_parent = ppnode;
		}

	}
private:
	Node* _root = nullptr;
};