C++使用红黑树进行封装map和set

一、STL库中的set和map源码

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

二、利用模板区分map和set

template
struct RedBlackTreeNode
{
	T _data;
	RedBlackTreeNode* _left;//该节点的左孩子
	RedBlackTreeNode* _right;//该节点的右孩子
	RedBlackTreeNode* _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,pair的比较规则是first比完之后可能会再去比较second（而我们仅仅想要比较first，该比较规则不适用）。

通过源码启发，我们可以对红黑树新增一个模板参数：

仿函数KeyOfT，在set和map类中完善该仿函数的比较对象，

用于区分set和map的比较：

struct MapKeyOfT
{
    const K& operator()(const pair& 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。

而小编使用的是无头结点进行封装的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::const_iterator iterator;
typedef typename RedBlackTree::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, MapKeyOfT>::iterator iterator;
typedef typename RedBlackTree, 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 Node;
	Node* _node;
	typedef __TreeIterator Self;
	typedef __TreeIterator 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迭代器的拷贝构造函数则由编译器自动生成，刚好满足迭代器值拷贝的特点。

八、源码

1、set.h

#include "9.14RedBlackTree.h"

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

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

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

	private:
		RedBlackTree _t;
	};
}

2、map.h

#include "9.14RedBlackTree.h"
namespace sqy
{
	template
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RedBlackTree, MapKeyOfT>::iterator iterator;
		typedef typename RedBlackTree, 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)
		{
			pairret = _t.Insert(make_pair(key, V()));
			return ret.first->second;
		}

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

3、RedBlackTree.h

#include 
#include 
using namespace std;

enum Color
{
	RED,
	BLACK
};


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

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

template
struct __TreeIterator
{
	typedef RedBlackTreeNode Node;
	Node* _node;
	typedef __TreeIterator Self;
	typedef __TreeIterator 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 RedBlackTree
{
	typedef RedBlackTreeNode Node;
public:
	typedef __TreeIterator iterator;
	typedef __TreeIterator 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 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;
};

到此这篇关于C++使用红黑树进行封装map和set的文章就介绍到这了,更多相关内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文地址：https://blog.csdn.net/VHhhbb/article/details/132921717