【C++进阶】RBTree封装map与set

2024-06-20 1154阅读

1.红黑树的迭代器

1.1 begin()

begin()就是红黑树的开头，那么对于红黑树来说按照中序序列是该树的最左节点。

	Iterator Begin()
	{
		Node* leftMin = _root;
		while (leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return Iterator(leftMin);
	}

1.2 end()

begin()就是红黑树的结尾的下一个，那么对于红黑树来说按照中序序列应该是该树的最右节点的下一个位置，但下一个位置是nullptr（这里库中源码写的是使用了一个哨兵位的头节点作为End,我们可以简单来写，以nullptr作为End）。

Iterator End()
{
	return Iterator(nullptr);
}

1.3 operator++

【C++进阶】RBTree封装map与set

Self& operator++()
{
	//1.右不为空，下一个是右子树最左节点
	if (_node->_right)
	{
		Node* leftMin = _node->_right;
		while (leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		_node = leftMin;
	}
	//2.右为空，下一个倒着在祖先中找孩子是父亲的左的祖先节点
	else
	{
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent && cur == parent->_right)
		{
			cur = parent;
			parent = cur->_parent;
		}
		_node = parent;
	}
	return *this;
}

2.改造红黑树

因为我们之前写的红黑树是不能同时满足set和map的使用，如果需要还必须再写一份来满足另一个，那么我们可不可以把红黑树改造成能同时满足set和map呢？

答案是可以的，我们实质上是偷了个懒，把写另一个的事情交给编译器去做，这也是能体现面向对象中封装的特性的！

#pragma once
#include
enum Color
{
	RED,
	BLACK
};
template
struct RBTreeNode
{
	RBTreeNode* _left;	//该节点的左孩子
	RBTreeNode* _right;	//该节点的右孩子
	RBTreeNode* _parent;	//该节点的双亲
	Color _col;
	T _data;	//存放Key或者pair
	RBTreeNode(const T& data)	//该节点初始化
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}
};
template
struct __RBTreeIterator
{
	typedef RBTreeNode Node;
	typedef __RBTreeIterator 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;
	}
	Self& operator++()
	{
		//1.右不为空，下一个是右子树最左节点
		if (_node->_right)
		{
			Node* leftMin = _node->_right;
			while (leftMin->_left)
			{
				leftMin = leftMin->_left;
			}
			_node = leftMin;
		}
		//2.右为空，下一个倒着在祖先中找孩子是父亲的左的祖先节点
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};
template
class RBTree
{
	typedef RBTreeNode Node;
public:
	typedef __RBTreeIterator Iterator;
	typedef __RBTreeIterator ConstIterator;
	RBTree() = default;
	//t2(t1)
	RBTree(const RBTree& t)
	{
		_root = Copy(t._root);
	}
	~RBTree()
	{
		Destroy(_root);
		_root = nullptr;
	}
	//t2 = t1
	RBTree& operator=(const RBTree t)
	{
		swap(_root, t._root);
		return *this;
	}
	Iterator Begin()
	{
		Node* leftMin = _root;
		while (leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return Iterator(leftMin);
	}
	Iterator End()
	{
		return Iterator(nullptr);
	}
	ConstIterator Begin() const
	{
		Node* leftMin = _root;
		while (leftMin->_left)
		{
			leftMin = leftMin->_left;
		}
		return ConstIterator(leftMin);
	}
	ConstIterator End() const
	{
		return ConstIterator(nullptr);
	}
	Iterator Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key _right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;
			}
			else
			{
				return Iterator(cur);
			}
		}
		return End();
	}
	pair Insert(const T& data)
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(Iterator(_root), true);
		}
		
		KeyOfT kot;
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (kot(cur->_data) _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;
		cur->_col = RED;	//新增节点给红色
		if (kot(parent->_data) _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 = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else //叔叔不存在/叔叔存在且为黑 -->旋转操作
				{
					if (cur == parent->_left)
					{
						//      g
						//    p   u
						//  c
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//      g
						//    p   u
						//      c
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = grandfather->_left;
				//叔叔存在且为红->变色即可
				if (uncle && uncle->_col == RED)
				{
					parent->_col = BLACK;
					uncle->_col = BLACK;
					grandfather->_col = RED;
					//继续往上调整
					cur = grandfather;
					parent = cur->_parent;
				}
				else //叔叔不存在/叔叔存在且为黑 -->旋转操作
				{
					if (cur == parent->_right)
					{
						//     g
						//   u   p 
						//         c
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//      g
						//    u   p
						//      c
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;//无论是否调整到根节点都让根节点始终是黑色
		return make_pair(Iterator(newnode), true);
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		parent->_left = subLR;
		if (subLR)	//subLR有可能为空，不为空时才能调整subLR的父节点
			subLR->_parent = parent;
		subL->_right = parent;
		//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点
		Node* ppNode = parent->_parent;
		parent->_parent = subL;
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)	//subRL有可能为空，不为空时才能调整subRL的父节点
			subRL->_parent = parent;
		subR->_left = parent;
		//parent不一定就是根节点，也可能是子树，所以要设置一个ppNode来标记parent的父节点
		Node* ppNode = parent->_parent;
		parent->_parent = subR;
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}
	void InOrder()
	{
		_InOrder(_root);
		cout _col == RED)
		{
			return false;
		}
		int refNum = 0;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_col == BLACK)
				++refNum;
			cur = cur->_left;
		}
		return Check(_root, 0, refNum);
	}
private:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
		Node* newroot = new Node(root->_data);
		newroot->_col = root->_col;
		newroot->_left = Copy(root->_left);
		if (newroot->_left)
			newroot->_left->_parent = newroot;
		newroot->_right = Copy(root->_right);
		if (newroot->_right)
			newroot->_right->_parent = newroot;
		return newroot;
	}
	void Destroy(Node* root)
	{
		if (root == nullptr)
			return;
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
		root = nullptr;
	}
	bool Check(Node* root, int blackNum, const int refNum)
	{
		if (root == nullptr)
		{
			//检查规则4
			if (blackNum != refNum)
			{
				cout _parent->_col == RED)
		{
			cout _kv.first _left, blackNum, refNum)
			&& Check(root->_right, blackNum, refNum);
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout _kv.first
VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]