使用红黑树模拟实现map和set

在STL的源代码中，map和set的底层原理都是红黑树。但这颗红黑树跟我们单独写的红黑树不一样，它需要改造一下：

改造红黑树

节点的定义

因为map和set的底层都是红黑树。而且map是拥有键值对pair<K,V>的，而set是没有键值对，只有一个K。因此，为了应对这两种不同的情况，就使用模板参数T。

当map使用这棵红黑树的时候，T就会变成pair<K,V>。当set使用时，T就会变成K。

代码语言：javascript复制

//使用枚举
enum Colour
{
	RED,
	BLACK,
};


// 如果是map，则为pair<K, V>; 如果是set，则为k
//因此，对于节点来说，需要再套一层模板，来应付两种不同的情况
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)
		, _col(RED)  //默认是红色
	{}
};

改版的红黑树的插入操作

红黑树的模板参数有三个：K、valueType和仿函数KeyOfValue。

K是key的类型，ValueTyp要么是set的K，要么是map的pair<const K,V>。

而仿函数是为了比较节点的值的大小的，因为官方库中键值对pair<K,V>比较大小的方法是比较first和second。但是红黑树中，新增节点是通过比较first，因此我们需要自己写一个仿函数用于单独比较first。

代码语言：javascript复制

//跟节点的定义一样
//因为关联式容器中存储的是<key, value>的键值对，因此
// k为key的类型，
// ValueType: 如果是map，则为pair<K, V>; 如果是set，则为k。如下：
// map->RBTree<K,pair<const K,V>,MapKeyOfT> _t;
// set->RBTree<K,K,SetKeyOfT> _t
// 
// KeyOfValue: 通过value来获取key的一个仿函数类。其作用就是用于比较。
template<class K,class ValueType,class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<ValueType> Node;
public: 
    //迭代器
    typedef __RBTreeIterator<ValueType> iterator;
   //......
private:
	Node* _root = nullptr;
};

迭代器

红黑树的迭代器不能使用原生指针，因为它是一棵树，节点地址不连续，因此需要封装起来。

代码语言：javascript复制

//set的K，map的pair<K,V>
template<class ValueType>
struct __RBTreeIterator
{
	typedef RBTreeNode<ValueType> Node;
	typedef __RBTreeIterator<ValueType> Self;
	Node* _node;

	__RBTreeIterator(Node* node)
		:_node(node)
	{}
};

1.operator ()

红黑树是二叉搜索树，采用的是中序遍历的方法。因此，迭代器每次向前走，是按照中序遍历的顺序走的。

因此，对于往前 ，有两种情况：第一种情况是当前节点的右孩子不为空，那么按照中序遍历的顺序，下一个节点便是右子树的最小值。第二种情况是当前节点的右孩子为空：这种情况下，又分两种情况：①当前节点是父节点的左孩子，那么下一个节点肯定是当前节点的父节点。②当前节点是父节点的右孩子，这意味着当前节点的父节点也被遍历了，又没有右孩子节点，只能往上找了，找的节点是祖先节点，而这个祖先节点是特征是：孩子节点是它的左节点。

代码语言：javascript复制

	//左 根  右
	Self& operator  ()
	{
		//当当前节点的右子树不为空，根据中序遍历的顺序，那就找右子树最小值
		if (_node->_right)
		{
			Node* minValue = _node->_right;
			while (minValue->_left)
			{
				minValue = minValue->_left;
			}

			//找到最小值的节点后，更新节点
			_node = minValue;
		}
		else  //当当前节的的右子树为空，说明它是叶子节点。此时需要判断情况
		{
			//判断当前节点是父亲节点的左孩子还是右孩子
			//第一种情况：如果是cur==parent->_right，即当前节点是父节点的右孩子的话，就
			//去找祖先节点（这个祖先节点的特征：孩子节点是它的左节点）
			//第二种情况：当前节点是父亲节点的左孩子，那么下一个节点就是父亲节点了
			Node* cur = _node;
			//定义父亲节点。
			Node* parent = cur->_parent;
			//如果当前节点不是父亲的右孩子，并且父亲是不存在，那么就是根节点或者是左孩子节点了
			//那就不进入循环。
			while (parent && cur == parent->_right)
			{
				//如果是，那就往上找到下一个节点。
				cur = cur->_parent;
				parent = parent->_parent;
			}

			//更新节点
			_node = parent;

		}
		return *this;
	}

2.begin()和end();

迭代器的begin和end，是左闭右开的区间。那么begin就是最左的节点，end则是最右节点的下一个节点。这里不使用哨兵来作为end节点。

对于begin，就找到最左的节点就好啦！

代码语言：javascript复制

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

对于end，这里选择直接置为空，传入匿名对象。这样子做的话，当遍历到最后一个节点后，它会往回遍历，一直到了根节点的上面一个节点，也就是空。此时就会结束循环。

代码语言：javascript复制

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

迭代器整体代码：

代码语言：javascript复制

template<class ValueType>
struct __RBTreeIterator
{
	typedef RBTreeNode<ValueType> Node;
	typedef __RBTreeIterator<ValueType> Self;
	Node* _node;

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

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

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

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

		
			_node = minValue;
		}
		else 
		{
			Node* cur = _node;
	
			Node* parent = cur->_parent;
			while (parent && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

set的模拟实现

仿函数

由于set只有Key，因此就让仿函数直接返回Key值就可以了。

代码语言：javascript复制

template<class K>
	class set
	{
		//set的仿函数，返回set的K值
		struct SetKeyOfValue
		{

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

整体都是复用了红黑树的接口，并没有什么技术含量，问题都在红黑树中解决了。

代码语言：javascript复制

namespace my_set
{
	template<class K>
	class set
	{
		//set的仿函数，返回set的K值
		struct SetKeyOfValue
		{

			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfValue>::iterator iterator;

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

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

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

	};

map的模拟实现：

仿函数

由于比较的是first，因此我们返回键值对中的first即可。

代码语言：javascript复制

template<class K, class V>
	class map
	{
		struct MapKeyOfValue
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};

整体代码，一样的都是复用了红黑树的接口，并没有什么技术含量：

代码语言：javascript复制

namespace my_map
{
	template<class K, class V>
	class map
	{
		struct MapKeyOfValue
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfValue>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}

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

最后是红黑树的整体代码，这段代码跟单独写的红黑树的代码差不多，就是在新增节点的操作那里，比较节点的值使用的是仿函数。

代码语言：javascript复制

#pragma once

//使用枚举
enum Colour
{
	RED,
	BLACK,
};


// 如果是map，则为pair<K, V>; 如果是set，则为k
//因此，对于节点来说，需要再套一层模板，来应付两种不同的情况
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)
		, _col(RED)  //默认是红色
	{}
};

template<class ValueType>
struct __RBTreeIterator
{
	typedef RBTreeNode<ValueType> Node;
	typedef __RBTreeIterator<ValueType> Self;
	Node* _node;

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

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

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

	//左 根  右
	Self& operator  ()
	{
		//当当前节点的右子树不为空，根据中序遍历的顺序，那就找右子树最小值
		if (_node->_right)
		{
			Node* minValue = _node->_right;
			while (minValue->_left)
			{
				minValue = minValue->_left;
			}

			//找到最小值的节点后，更新节点
			_node = minValue;
		}
		else  //当当前节的的右子树为空，说明它是叶子节点。此时需要判断情况
		{
			//判断当前节点是父亲节点的左孩子还是右孩子
			//第一种情况：如果是cur==parent->_right，即当前节点是父节点的右孩子的话，就
			//去找祖先节点（这个祖先节点的特征：孩子节点是它的左节点）
			//第二种情况：当前节点是父亲节点的左孩子，那么下一个节点就是父亲节点了
			Node* cur = _node;
			//定义父亲节点。
			Node* parent = cur->_parent;
			//如果当前节点不是父亲的右孩子，并且父亲是不存在，那么就是根节点或者是左孩子节点了
			//那就不进入循环。
			while (parent && cur == parent->_right)
			{
				//如果是，那就往上找到下一个节点。
				cur = cur->_parent;
				parent = parent->_parent;
			}

			//更新节点
			_node = parent;

		}
		return *this;
	}

	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};
//跟节点的定义一样
//因为关联式容器中存储的是<key, value>的键值对，因此
// k为key的类型，
// ValueType: 如果是map，则为pair<K, V>; 如果是set，则为k。如下：
// map->RBTree<K,pair<const K,V>,MapKeyOfT> _t;
// set->RBTree<K,K,SetKeyOfT> _t
// 
// KeyOfValue: 通过value来获取key的一个仿函数类。其作用就是用于比较。
template<class K,class ValueType,class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<ValueType> Node;
public:
	typedef __RBTreeIterator<ValueType> iterator;

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

	iterator end()
	{
		return iterator(nullptr);
	}
	bool Insert(const ValueType& data)
	{
		//先按二叉搜索树的规矩来创建一棵二叉搜索树
		if (_root == nullptr)
		{
			_root = new Node(data);
			//因为红黑树的根节点是黑色的
			_root->_col = BLACK;
			return true;
		}

		KeyOfValue kot;
		Node* parent = nullptr;
		Node* cur = _root;
		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;
			}
		}

		cur = new Node(data);
		cur->_col = RED;//多写一步，防止写错代码。
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

		//创建完二叉搜索树
		//开始创建红黑树，使用颜色来判断是否需要调整
		//循环往上走，循环条件：当走到的parent不为空，并且parent是红色的
		//即我们列举是三种情况，parent都是红的，就需要重新调整
		//如果parent是黑色的，那就不需要了。直接就是一棵红黑树,不进入循环
		while (parent && parent->_col == RED)
		{
			//保存祖先节点，即g节点
			Node* grandfther = parent->_parent;
			//判断父节点是在祖先节点的哪边
			if (parent == grandfther->_left)
			{
				//父节点在左边，那么叔叔节点就在右边
				Node* uncle = grandfther->_right;
				//情况一：uncle存在且为红。改变颜色即可
				if (uncle && uncle->_col == RED)
				{
					//变色。
					parent->_col = uncle->_col = BLACK;
					grandfther->_col = RED;

					//往上走
					cur = grandfther;
					parent = cur->_parent;
				}
				else  //uncle不存在 或者 存在但是黑色
				{
					//情况二  p是g的左孩子，cur是p的左孩子，以g为轴右单旋
					if (cur == parent->_left)
					{
						//右单旋
						RotateR(grandfther);
						//变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
						parent->_col = BLACK;
						grandfther->_col = RED;
					}
					else  //情况三  p是g的左孩子，cur是p的右孩子.
					{
						//先以p为轴左旋转
						RotateL(parent);
						//变成情况二，再以g为轴右单旋
						RotateR(grandfther);
						//变色  cur变成根节点，为黑色。p和g是红色
						cur->_col = BLACK;
						grandfther->_col = RED;

					}

					break;
				}
			}
			else  //parent是在grandfther的右边
			{
				//叔叔节点就在祖先节点的左边
				Node* uncle = grandfther->_left;
				//情况一：uncle存在且为红。改变颜色即可
				if (uncle && uncle->_col == RED)
				{
					//变色。
					parent->_col = uncle->_col = BLACK;
					grandfther->_col = RED;

					//往上走
					cur = grandfther;
					parent = cur->_parent;
				}
				else  //uncle不存在 或者 存在但是黑色
				{
					//情况二  p是g的右孩子，cur是p的右孩子。
					if (cur == parent->_right)
					{
						//左单旋
						RotateL(grandfther);
						//变色  右单旋后，parent为根节点，变黑色。cur和g节点为红色
						parent->_col = BLACK;
						grandfther->_col = RED;
					}
					else  //情况三  p是g的右孩子，cur是p的左孩子.
					{
						//先以p为轴右旋转
						RotateR(parent);
						//变成情况二，再以g为轴左单旋
						RotateL(grandfther);
						//变色  cur变成根节点，为黑色。p和g是红色
						cur->_col = BLACK;
						grandfther->_col = RED;

					}

					break;
				}
			}
		}
		//最后将根节点置为黑
		_root->_col = BLACK;
		return true;
	}



	void RotateL(Node* parent)
	{

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

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

	}
	void RotateR(Node* parent)
	{

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

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

			}
			else
			{
				ppNode->_right = subL;
			}


			subL->_parent = ppNode;
		}
	}

	void Inorder()
	{
		_Inorder(_root);
	}

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

		_Inorder(root->_left);
		std::cout << root->_kv.first << ": " << root->_kv.second << std::endl;
		_Inorder(root->_right);
	}
	bool Check(Node* root, int blackNum, const int ref)
	{
		if (root == nullptr)
		{
			//cout << blackNum << endl;
			if (blackNum != ref)
			{
				cout << "违反规则：本条路径的黑色节点的数量跟最左路径不相等" << endl;
				return false;
			}

			return true;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则：出现连续红色节点" << endl;
			return false;
		}

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

		return Check(root->_left, blackNum, ref)
			&& Check(root->_right, blackNum, ref);
	}

	bool IsBalance()
	{
		if (_root == nullptr)
		{
			return true;
		}

		if (_root->_col != BLACK)
		{
			return false;
		}

		int ref = 0;
		Node* left = _root;
		while (left)
		{
			if (left->_col == BLACK)
			{
				  ref;
			}

			left = left->_left;
		}

		return Check(_root, 0, ref);
	}
private:
	Node* _root = nullptr;
};

map set 遍历 函数 接口

0 人点赞