C++【STL】改造红黑树简单模拟实现set map（带你了解set map的底层实现结构）_业界新闻

发布时间:2024-07-13 21:18

阅读量:0

前言：

下面为了简单模拟实现set map所出现的代码是以C++中STL源码库中的代码逻辑基础进行的简化代码，本片博客目的是带你简单深入底层，了解set map底层的实现逻辑，对泛型编程有更加深刻的认识。

一、学前铺垫（泛型编程）

本篇博客我们通过对一个红黑树进行改造，使其可以让set和map的模拟实现都使用这一个红黑树结构，因为set map所存储的数据类型不一样,set底层存储的是pair<key,key>,map底层存储的是pair<key,value>,所以这里就一定会用上多个模板对红黑树进行改造，形成泛型编程，之后再对set map使用改造后的红黑树进行封装，达到模拟STL库中set map的效果。（有能力的可以直接去看STL中set map所实现的源码，逻辑与我所讲述的相同）

二、改造红黑树

1.红黑树节点的改造

这里节点的构造基本与二叉搜索树的节点构造相同，但是因为要同时兼顾set map两中类型，所以存储数据的类型不可以写死，要用到模板，节点代码如下：

template <class T> struct RBTreeNode { 	RBTreeNode<T>* _left; 	RBTreeNode<T>* _right; 	RBTreeNode<T>* _parent;  	Color _col; 	T _data;  	RBTreeNode(const T& data) 		:_left(nullptr) 		, _right(nullptr) 		, _parent(nullptr) 		, _data(data) 		, _col(RED) 	{} };

2.insert的改造

需要改造的地方：

1) 根据STL库中的set和map的insert的功能，插入成功返回插入位置所在的迭代器以及true，插入失败说明树中已存在改值，返回该值所在的位置的迭代器以及false，所以返回类型应为pair<iterator,bool>，所以返回类型需要进行改造。

2) 在insert中大小值的比较，因为要兼容set和map，而在set中的模板类型只需要一个就可以进行初始化，因为set中底层数据类型是一样的，而map不同，map底层类型其实是pair<key,pair<key,value>>实现，因为在实现find函数时需要用到key的值并且与set保持一致，所以将value类型定义为pair<key,value>，那么在后续的比较大小中就不能那么随意了，因为set直接拿其节点指向的_data进行比较即可，而map中的_data为pair<key,pair<key,value>>,不可以直接拿来进行比较,所以我们将代码进行改造。

下面是模拟实现set，map的简单封装。SetKeyOFT，MapKeyOFT就是解决大小比较所定义的内部类。
Mymap.h:

template <class K,class V> class map { public:  	struct MapKeyOFT 	{ 		const K& operator()(const pair<K, V>& kv) 		{ 			return kv.first; 		} 	}; private: 	RBTree<K, pair<K,V>, MapKeyOFT> _t; };

Myset.h:

template <class K> class set { public: 	struct SetKeyOFT 	{ 		const K& operator()(const K& key) 		{ 			return key; 		} 	}; private: 	RBTree<K,K, SetKeyOFT> _t; };

insert函数改造实现：

	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* parent = nullptr; 		Node* cur = _root; 		while (cur) 		{ 			if (kot(cur->_data) > kot(data)) 			{ 				parent = cur; 				cur = cur->_left; 			} 			else if (kot(cur->_data) < kot(data)) 			{ 				parent = cur; 				cur = cur->_right; 			} 			else 			{ 				//不允许冗余 				return make_pair(iterator(cur),false); 			} 		}  		//找到对应位置 		cur = new Node(data); 		cur->_parent = parent; 		 		Node* newcur = cur;  		if (kot(parent->_data) > kot(data)) 		{ 			parent->_left = cur; 		} 		else 		{ 			parent->_right = cur; 		}  		//父亲的颜色是黑色也就结束 		while (parent && parent->_col == RED)//红黑树出现错误需要改正 		{ 			Node* grandfather = parent->_parent; 			if (grandfather->_left == parent) 			{ 				//舅子树在右边 				Node* uncle = grandfather->_right; 				if (uncle && uncle->_col == RED) 				{ 					//存在且颜色为红 					parent->_col = BLACK; 					uncle->_col = BLACK; 					/*if (grandfather == _root) 					{ 						grandfather->_col = BLACK; 					} 					else 					{ 						grandfather->_col = RED; 					}*/  					grandfather->_col = RED;  					cur = grandfather; 					parent = grandfather->_parent; 				} 				else 				{ 					//舅子树不存在或颜色为黑 					if (parent->_left == cur) 					{ 						//单旋 						parent->_col = BLACK; 						grandfather->_col = RED; 						RNode(grandfather); 					} 					else 					{ 						//双旋 先左再右 						LNode(parent); 						cur->_col = BLACK; 						grandfather->_col = RED; 						RNode(grandfather); 					} 					break; 				} 			} 			else 			{ 				//舅子树在左边 				Node* uncle = grandfather->_left; 				if (uncle && uncle->_col == RED) 				{ 					parent->_col = BLACK; 					uncle->_col = BLACK; 					grandfather->_col = RED;  					cur = grandfather; 					parent = grandfather->_parent; 				} 				else 				{ 					if (parent->_right == cur) 					{ 						//单旋 						parent->_col = BLACK; 						grandfather->_col = RED; 						LNode(grandfather); 					} 					else 					{ 						//双旋 						RNode(parent); 						LNode(grandfather); 						grandfather->_col = RED; 						cur->_col = BLACK; 					} 					break; 				} 			} 		}  		_root->_col = BLACK;  		return make_pair(iterator(newcur),true); 	}

因为只在红黑树insert函数里面使用的都是模板，所以是不知道所传数据的具体类型，但是在模拟实现的set，map中知道其对应的类型，所以我们可以在set，map类里面定义一个类，在这个类里面定义一个仿函数用于提取所对应比较大小的值，再将这个类用模板参数传递给红黑树中，在需要比较大小时提前用这个类定义一个变量，在通过仿函数进行大小的比较，这样就可以实现set，map的兼容。

3.迭代器的实现

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题：● begin()与end()

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行--操作，必须要能找最 后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：

● operator++()与operator--()

// 找迭代器的下一个节点，下一个节点肯定比其大 void Increasement() { 	//分两种情况讨论:_pNode的右子树存在和不存在 	// 右子树存在 	if (_pNode->_pRight) 	{ 		// 右子树中最小的节点，即右子树中最左侧节点 		_pNode = _pNode->_pRight; 		while (_pNode->_pLeft) 			_pNode = _pNode->_pLeft; 	} 	else 	{ 		// 右子树不存在，向上查找，直到_pNode != pParent->right 		PNode pParent = _pNode->_pParent; 		while (pParent->_pRight == _pNode) 		{ 			_pNode = pParent; 			pParent = _pNode->_pParent; 		} 		// 特殊情况：根节点没有右子树 		if (_pNode->_pRight != pParent) 			_pNode = pParent; 	} } // 获取迭代器指向节点的前一个节点 void Decreasement() { 	//分三种情况讨论：_pNode 在head的位置，_pNode 左子树存在，_pNode 左子树不 	存在 		// 1. _pNode 在head的位置，--应该将_pNode放在红黑树中最大节点的位置 		if (_pNode->_pParent->_pParent == _pNode && _pNode->_color == RED) 			_pNode = _pNode->_pRight; 		else if (_pNode->_pLeft) 		{ 			// 2. _pNode的左子树存在,在左子树中找最大的节点，即左子树中最右侧节点 			_pNode = _pNode->_pLeft; 			while (_pNode->_pRight) 				_pNode = _pNode->_pRight; 		} 		else 		{ 			// _pNode的左子树不存在，只能向上找 			PNode pParent = _pNode->_pParent; 			while (_pNode == pParent->_pLeft) 			{ 				_pNode = pParent; 				pParent = _pNode->_pParent; 			} 			_pNode = pParent; 		} }

4.完整改造代码

#pragma once #include <iostream> using namespace::std;  enum Color { 	RED,//(0) 	BLACK//(1) };  template <class T> struct RBTreeNode { 	RBTreeNode<T>* _left; 	RBTreeNode<T>* _right; 	RBTreeNode<T>* _parent;  	Color _col; 	T _data;  	RBTreeNode(const T& data) 		:_left(nullptr) 		, _right(nullptr) 		, _parent(nullptr) 		, _data(data) 		, _col(RED) 	{} };  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; 	}  	Self& operator--() 	{ 		if (_node->_left) 		{ 			//存在左子树 			Node* cur = _node->_left; 			while (cur->_right) 			{ 				cur = cur->_right; 			} 			_node = cur; 		} 		else 		{ 			//不存在左子树 			Node* parent = _node->_parent; 			if (parent && parent->_left == _node) 			{ 				//为父亲的左孩子 				while (parent && parent->_left == _node) 				{ 					_node = parent; 					parent = parent->_parent; 				} 				_node = parent; 			} 			else 			{ 				//为父亲的右孩子 				_node = parent; 			} 		}  		return *this; 	}  	Self& operator++() 	{ 		if (_node->_right) 		{ 			//存在右子树 			_node = _node->_right; 			while (_node && _node->_left) 			{ 				_node = _node->_left; 			} 		} 		else 		{ 			//不存在右子树 			Node* parent = _node->_parent; 			while (parent && _node == parent->_right) 			{ 				_node = parent; 				parent = parent->_parent; 			} 			_node = parent; 		} 		return *this; 	} };  template <class K, class T, class KeyOfT> class RBTree { 	typedef RBTreeNode<T> Node; public: 	typedef __RBTreeIterator<T, T&, T*> iterator; 	typedef __RBTreeIterator<T,const T&,const T*> const_iterator;  	RBTree() = default;//强制编译器生成构造函数  	//拷贝构造 	RBTree(RBTree<K, const T, KeyOfT>& t) 	{ 		_root = copy(t._root); 	}  	iterator begin() 	{ 		Node* LeftMin = _root; 		while (LeftMin && LeftMin->_left) 		{ 			LeftMin = LeftMin->_left; 		} 		return iterator(LeftMin); 	}  	iterator end() 	{ 		return iterator(_root->_parent); 	} 	 	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); 	}  	//右单旋，满足二叉树引发右单旋之后平衡因子一定为0 	void RNode(Node* parent) 	{ 		Node* pparent = parent->_parent;  		Node* subL = parent->_left; 		Node* subLR = subL->_right;  		parent->_left = subLR; 		if (subLR) 			subLR->_parent = parent;  		subL->_right = parent; 		parent->_parent = subL;  		if (pparent) 		{ 			subL->_parent = pparent;  			if (pparent->_left == parent) 			{ 				pparent->_left = subL; 			} 			else 			{ 				pparent->_right = subL; 			} 		} 		else 		{ 			_root = subL; 			subL->_parent = nullptr; 		} 	}  	//左单旋 	void LNode(Node* parent) 	{ 		Node* pparent = parent->_parent;  		Node* subR = parent->_right; 		Node* subRL = subR->_left;  		parent->_right = subRL; 		if (subRL) 			subRL->_parent = parent;  		subR->_left = parent; 		parent->_parent = subR;  		if (pparent) 		{ 			subR->_parent = pparent;  			if (pparent->_left == parent) 			{ 				pparent->_left = subR; 			} 			else 			{ 				pparent->_right = subR; 			} 		} 		else 		{ 			_root = subR; 			subR->_parent = 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* parent = nullptr; 		Node* cur = _root; 		while (cur) 		{ 			if (kot(cur->_data) > kot(data)) 			{ 				parent = cur; 				cur = cur->_left; 			} 			else if (kot(cur->_data) < kot(data)) 			{ 				parent = cur; 				cur = cur->_right; 			} 			else 			{ 				//不允许冗余 				return make_pair(iterator(cur),false); 			} 		}  		//找到对应位置 		cur = new Node(data); 		cur->_parent = parent; 		 		Node* newcur = cur;  		if (kot(parent->_data) > kot(data)) 		{ 			parent->_left = cur; 		} 		else 		{ 			parent->_right = cur; 		}  		//父亲的颜色是黑色也就结束 		while (parent && parent->_col == RED)//红黑树出现错误需要改正 		{ 			Node* grandfather = parent->_parent; 			if (grandfather->_left == parent) 			{ 				//舅子树在右边 				Node* uncle = grandfather->_right; 				if (uncle && uncle->_col == RED) 				{ 					//存在且颜色为红 					parent->_col = BLACK; 					uncle->_col = BLACK;  					grandfather->_col = RED;  					cur = grandfather; 					parent = grandfather->_parent; 				} 				else 				{ 					//舅子树不存在或颜色为黑 					if (parent->_left == cur) 					{ 						//单旋 						parent->_col = BLACK; 						grandfather->_col = RED; 						RNode(grandfather); 					} 					else 					{ 						//双旋 先左再右 						LNode(parent); 						cur->_col = BLACK; 						grandfather->_col = RED; 						RNode(grandfather); 					} 					break; 				} 			} 			else 			{ 				//舅子树在左边 				Node* uncle = grandfather->_left; 				if (uncle && uncle->_col == RED) 				{ 					parent->_col = BLACK; 					uncle->_col = BLACK; 					grandfather->_col = RED;  					cur = grandfather; 					parent = grandfather->_parent; 				} 				else 				{ 					if (parent->_right == cur) 					{ 						//单旋 						parent->_col = BLACK; 						grandfather->_col = RED; 						LNode(grandfather); 					} 					else 					{ 						//双旋 						RNode(parent); 						LNode(grandfather); 						grandfather->_col = RED; 						cur->_col = BLACK; 					} 					break; 				} 			} 		}  		_root->_col = BLACK;  		return make_pair(iterator(newcur),true); 	}  	bool IsRBTree() 	{ 		if (_root->_col == RED) 		{ 			cout << "根节点为红节点" << endl; 			return false; 		}  		int DefNum = 0; 		Node* cur = _root; 		while (cur) 		{ 			if (cur->_col == BLACK) 			{ 				DefNum++; 			}  			cur = cur->_left; 		}  		return _Check(_root, 0, DefNum); 	}  	~RBTree() 	{ 		Destory(_root);  		_root = nullptr; 	}  private: 	Node* copy(const Node* root) 	{ 		if (root == nullptr) 		{ 			return nullptr; 		}  		Node* newnode = new Node(root->_data); 		newnode->_col = root->_col;  		newnode->_left = copy(root->_left); 		if(newnode->_left) 			newnode->_left->_parent = newnode; 		newnode->_right = copy(root->_right); 		if (newnode->_left) 			newnode->_left->_parent = newnode;  		return newnode; 	}  	void Destory(Node* root) 	{ 		if (root == nullptr) 		{ 			return; 		}  		Destory(root->_left); 		Destory(root->_right);  		delete root; 		root = nullptr; 	}  	bool _Check(Node* root, int BlackNum, int DefNum) 	{ 		if (root == nullptr) 		{ 			if (BlackNum != DefNum) 			{ 				cout << BlackNum << "|" << DefNum << endl; 				cout << "存在黑色节点数量不相等的路径" << endl; 				return false; 			} 			return true; 		}  		if (root->_col == RED && root->_parent->_col == RED) 		{ 			cout << root->_kv.first << "->存在连续的两个红节点" << endl; 			return false; 		}  		if (root->_col == BLACK) 		{ 			BlackNum++; 		}  		return _Check(root->_left, BlackNum, DefNum) 			&& _Check(root->_right, BlackNum, DefNum); 	}   	Node* _root = nullptr;  };

三、set的模拟实现封装

set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来(具体实现可参考map)。

template <class K> class set { public: 	struct SetKeyOFT 	{ 		const K& operator()(const K& key) 		{ 			return key; 		} 	};  	typedef typename RBTree<K, K, SetKeyOFT>::iterator iterator; 	typedef typename RBTree<K, const K, SetKeyOFT>::iterator const_iterator;  	pair<iterator,bool> insert(const K& key) 	{  		return _t.Insert(key); 	}  	iterator begin() 	{ 		return _t.begin(); 	}  	iterator end() 	{ 		return _t.end(); 	}  	const_iterator begin() const 	{ 		return _t.begin(); 	}  	const_iterator end() const 	{ 		return _t.end(); 	}  private: 	RBTree<K, const K, SetKeyOFT> _t; };

四、map的模拟实现封装

template <class K,class V> class map { public:  	struct MapKeyOFT 	{ 		const K& operator()(const pair<K, V>& kv) 		{ 			return kv.first; 		} 	};  	typedef typename RBTree<K, pair<const K, V>, MapKeyOFT>::iterator iterator; 	typedef typename RBTree<K, pair<const K, V>, MapKeyOFT>::iterator const_iterator;  	V& operator[](const K& key) 	{ 		pair<iterator,bool> ret = _t.Insert(make_pair(key,V())); 		return ret.first->second; 	}  	pair<iterator,bool> insert(const pair<K,V>& kv) 	{ 		return _t.Insert(kv); 	}  	iterator begin() 	{ 		return _t.begin(); 	}  	iterator end() 	{ 		return _t.end(); 	} 	 	const_iterator begin() const 	{ 		return _t.begin(); 	}  	const_iterator end() const 	{ 		return _t.end(); 	}  private: 	RBTree<K, pair<const K,V>, MapKeyOFT> _t; };