【C++】—— 实现底层为红黑树的Map和Set

STL关联式容器map/set介绍：

STL关联式容器map/set相关接口介绍

红黑树的模拟实现

浅析红黑树及其模拟实现

这两篇博客介绍了map/set的相关接口使用和红黑树的模拟实现，现在我们来用一个红黑树封装实现MyMap和MySet，在实现之前先简单解释一下map和set，map和set都是容器，唯一不同的是，map中存储的是一个一个的键值对pair<K,V>,set中存的是一个值，所以在用红黑树实现MyMap和MySet之前我们需要改造红黑树的节点，使他即能存储键值对又能存储一个值。

改造红黑树的节点

原来红黑树的节点

template<class K,class V>
struct RBSTreeNode
{
	RBSTreeNode(const pair<K, V>& kv)
	:_left(nullptr)
	, _right(nullptr)
	, _parent(nullptr)
	, _kv(kv)
	, _col(RED)
	{}
	RBSTreeNode<K, V>* _left;
	RBSTreeNode<K, V>* _right;
	RBSTreeNode<K, V>* _parent;

	pair<K, V> _kv;
	color _col;
};

改造后红黑树的节点

//改造红黑树的节点，通过Map或Set传过来的模板参数来决定节点中是存value值，还是pair<K,V>值
template<class V>
struct RBTreeNode
{
	typedef V ValueType;
	RBTreeNode(const ValueType& value)
	:_left(nullptr)
	, _right(nullptr)
	, _parent(nullptr)
	, _value(value)
	, _col(RED)
	{}
	RBTreeNode<ValueType>* _left;
	RBTreeNode<ValueType>* _right;
	RBTreeNode<ValueType>* _parent;

	ValueType _value;
	color _col;
};

改造红黑树的Insert

需要改变的地方：

• 第一个就是插入的值不再仅仅只是键值对，而是看是MyMap使用红黑树时，就传pair<K,V>,MySet使用时就传value
• 第二个比较关键的改造是在于，比较所存储值的大小，我们知道map中存储的是键值对，比较大小使用键值对中的第一个值key进行比较，而set比较直接就是用该值进行的，因此这里我们就借助了一个仿函数来实现，创建一个仿函数对象，通过该对象的返回值来进行大小的比较

	bool Insert(const ValueType& value)
	{
		//若树为空，直接插入
		if (_root == nullptr)
		{
			_root = new Node(value);
			_root->_col = BLACK;
			return true;
		}

		//不为空，先找到插入位置再插入节点
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfValue kov;//创建一个仿函数对象，通过该对象的返回值来进行大小的比较

		while (cur)
		{
			parent = cur;
			if (kov(value) < kov(cur->_value))
				cur = cur->_left;
			else if (kov(value) > kov(cur->_value))
				cur = cur->_right;
			else
			{
				return false;//如果树中已经有该元素，则插入失败
			}
				
		}

		//找到插入位置，插入节点
		//插入的节点颜色为红色，破坏红黑树的性质3,更好处理
		cur = new Node(value);
		cur->_col = RED;
		if (kov(value) < kov(parent->_value))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//插入节点成功后，检查红黑树的性质有没有被破坏
		//若是有则要进行节点的颜色调整以满足红黑树性质
		//若是父节点存在且父节点的颜色为红色则需要调整，否则满足红黑树性质
		while (parent && parent->_col == RED)
		{
			// 注意：grandFather一定存在
			// 因为parent存在，且不是黑色节点，则parent一定不是根，则其一定有双亲
			Node* grandfather = parent->_parent;

			//1、父节点是祖父节点的左孩子
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//1、叔叔节点存在且叔叔节点的颜色为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}

				//2、叔叔节点不存在或者叔叔节点的颜色为黑色
				else
				{
					//1、如果cur是parent的右孩子，此时需要进行左单旋将情况转换为情况2
					if (parent->_right == cur)
					{
						RotateL(parent);
						swap(cur, parent);
					}

					//1、如果cur是parent的z左孩子，此时只需进行一个右单旋，并将parent的颜色变为黑，grandparent的颜色置红
					RotateR(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}

			}

			//2、父节点是祖父节点的右孩子
			else
			{
				Node* uncle = grandfather->_left;
				//1、叔叔节点存在且叔叔节点的颜色为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}

				//2、叔叔节点不存在或者叔叔节点的颜色为黑色
				else
				{
					//1、若是cur为parent的左孩子，先进行一个右单旋转换为情况二一起处理
					if (parent->_left == cur)
					{
						RotateR(parent);
						swap(cur, parent);
					}

					//2、若是cur为parent的右孩子，进行一个左单旋，并将parent的颜色变为黑，grandparent的颜色置红
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
		}

		//旋转完成之后，将根节点的颜色置成黑色
		_root->_col = BLACK;
		return  true;
	}

搭建简易的MyMap

#include "RBtree.h"

template<class K, class V>//外部定义map时显示实例化还是使用K-V
class MyMap
{
	typedef pair<K, V> ValueType;//这里红黑树节点中将会存储pair<K, V>
public:
	struct MapKeyOfValue//传给红黑树的仿函数
	{
		const K& operator()(const ValueType& kv)
		{
			return kv.first;//我们需要使用pair的first进行比较
		}
	};
	bool Insert(const ValueType& key)
	{
		return t.Insert(key);
	}

private:
	RBTree<K, ValueType, MapKeyOfValue> t;//第一个参数：K值 第二个参数：节点中存的值 第三个参数：仿函数
};

搭建简易的MySet

template<class K>
class Myset
{
	typedef K ValueType;
public:
	struct SetKeyOfValue//传给红黑树的仿函数
	{
		const ValueType& operator()(const ValueType& key)
		{
			return key;//set直接通过存储的值进行比较
		}
	};

	pair<iterator, bool> Insert(const ValueType& key)
	{
		return t.Insert(key);
	}
private:
	RBTree<K, ValueType,SetKeyOfValue> t;//第一个参数：K值 第二个参数：节点中存的值 第三个参数：仿函数
};

红黑树的迭代器iterator

• 现在我们已经将简易的MyMap和MySet的框架搭建了起来，已经能往容器中插入数据了，现在我们想的应该就是怎么打印出来这些数据，我们知道STL模板都是大多都能通过迭代器iterator来遍历数据，这里我们就来实现一个迭代器来遍历MyMap和MySet中的数据。
• 实现之前我们要了解其实红黑树的迭代器其实就是一个节点的指针，我们知道迭代器都支持*解引用，->访问，++，- -等操作，这里我们就来实现一下这些功能

//红黑树迭代器
template<class V>
struct _RBTreeIterator
{
	typedef V ValueType;
	typedef RBTreeNode<ValueType> Node;
	typedef _RBTreeIterator<ValueType> Self;
	
	Node* _node;//迭代器的本质其实是一个节点的指针

	_RBTreeIterator(Node* node)//构造函数
		:_node(node)
	{}

	//_RBTreeIterator(const Self& node)//拷贝构造
	//	:_node(node)
	//{}

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

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

	Self& operator=(const Self& node)
	{
		_node = node._node;
	}

	bool operator!=(const Self& node)
	{
		return _node != node._node;
	}

	Self& operator++()
	{
		/*
		分两种情况讨论:
		1. _node的右子树存在
		2. _node的右子树不存在
		*/

		// 1. _node的右子树存在，则在右子树中找最小(最左侧)的节点
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			//第二种情况是_node的右子树不存在，一直向上找，找不是父节点的右节点节点
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}	
};

由于其他功能较为简单，我们这里主要分析一下operator++，我们知道红黑树遍历是是一个中序遍历，因此返回一个节点的下一个节点也应该是中序遍历的下一个节点，这里主要分为两种情况讨论：

• 第一种情况，该节点的右子树不为空，此时找_node节点右子树的最左节点即为_node节点的下一个节点
  
• 第二种情况，_node的右子树不存在时，此时要一直往上找不是父节点右孩子的节点，返回该节点的父节点，即为_node++后的下一个节点

MyMap的operator[]

这里讲一下MyMap的operator[]，之前在STL关联式容器map/set ,也讲到过operator[]，功能是随机访问map中的值，若是存在则返回该值的迭代器，不存在则插入，也可以用来修改map中的值。

	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = t.Insert(make_pair(key,V()));//插入成功将value设置为类型的默认缺省类型
		return ret.first->second;//ret.first取到这个节点的迭代器，ret.first->second可以对value进行修改
	}

基本改造已经实现，下面给出完整的代码

MyMap

• 这里使用了一个关键字叫typename，typedef typename RBTree<K, ValueType, MapKeyOfValue>::iterator iterator;其实是告诉编译器RBTree<K, ValueType, MapKeyOfValue>::iterator只是一个类型，不用去寻找他的代码，如果不加上关键字typename则编译不通过

#include "RBtree.h"

template<class K, class V>//外部定义map时显示实例化还是使用K-V
class MyMap
{
	typedef pair<K, V> ValueType;//这里红黑树中将会存储pair<K, V>
public:

	struct MapKeyOfValue//传给红黑树的仿函数
	{
		const K& operator()(const ValueType& kv)
		{
			return kv.first;//我们需要使用pair的first进行比较
		}
	};
	typedef typename RBTree<K, ValueType, MapKeyOfValue>::iterator iterator;
	
	iterator begin()
	{
		return t.begin();
	}

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

	pair<iterator,bool> Insert(const ValueType& key)
	{
		return t.Insert(key);
	}

	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = t.Insert(make_pair(key,V()));//插入成功将value设置为类型的默认缺省类型
		return ret.first->second;//ret.first取到这个节点的迭代器，ret.first->second可以对value进行修改
	}

private:
	RBTree<K, ValueType, MapKeyOfValue> t;//第一个参数：K值 第二个参数：节点中存的值 第三个参数：仿函数
};

void TestMyMap()
{
	MyMap<string, string> mm;
	mm.Insert(std::make_pair(string("sort"), string("排序")));
	mm.Insert(std::make_pair(string("string"), string("字符串")));
	mm.operator[]("left");
	mm.operator[]("left") = "剩余";
	mm.operator[]("string") = "STL模板";

	MyMap<string, string>::iterator it = mm.begin();
	while (it != mm.end())
	{
		cout << (*it).first << ":" << (*it).second << " ";
		++it;
	}
	cout << endl;
}

MySet

#include "RBtree.h"


template<class K>
class Myset
{
	typedef K ValueType;
public:
	struct SetKeyOfValue//传给红黑树的仿函数
	{
		const ValueType& operator()(const ValueType& key)
		{
			return key;
		}
	};

	typedef typename RBTree<K, ValueType, SetKeyOfValue>::iterator iterator;
	iterator begin()
	{
		return t.begin();
	}

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

	pair<iterator, bool> Insert(const ValueType& key)
	{
		return t.Insert(key);
	}
private:
	RBTree<K, ValueType,SetKeyOfValue> t;
};


void TestMySet()
{
	Myset<int> ms;
	ms.Insert(1);
	ms.Insert(2);
	ms.Insert(5);
	ms.Insert(8);

	Myset<int>::iterator it = ms.begin();
	while (it != ms.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

红黑树的实现

• 这里还进一步修改了红黑树的Insert，不只是返回bool值，而是返回一个键值对pair <iterator,bool>，第一个值为节点的迭代器，第二个值为是否插入成功的bool值。

#pragma once

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

enum color
{
	RED,
	BLACK
};

//改造红黑树的节点，通过Map或Set传过来的模板参数来决定节点中是存value值，还是pair<K,V>值
template<class V>
struct RBTreeNode
{
	typedef V ValueType;
	RBTreeNode(const ValueType& value)
	:_left(nullptr)
	, _right(nullptr)
	, _parent(nullptr)
	, _value(value)
	, _col(RED)
	{}
	RBTreeNode<ValueType>* _left;
	RBTreeNode<ValueType>* _right;
	RBTreeNode<ValueType>* _parent;

	ValueType _value;
	color _col;
};

//红黑树迭代器
template<class V>
struct _RBTreeIterator
{
	typedef V ValueType;
	typedef RBTreeNode<ValueType> Node;
	typedef _RBTreeIterator<ValueType> Self;
	
	Node* _node;//迭代器的本质其实是一个节点的指针

	_RBTreeIterator(Node* node)//构造函数
		:_node(node)
	{}

	//_RBTreeIterator(const Self& node)//拷贝构造
	//	:_node(node)
	//{}

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

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

	Self& operator=(const Self& node)
	{
		_node = node._node;
	}

	bool operator!=(const Self& node)
	{
		return _node != node._node;
	}

	Self& operator++()
	{
		/*
		分两种情况讨论:
		1. _node的右子树存在
		2. _node的右子树不存在
		*/

		// 1. _node的右子树存在，则在右子树中找最小(最左侧)的节点
		if (_node->_right)
		{
			Node* cur = _node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			_node = cur;
		}
		else
		{
			//第二种情况是_node的右子树不存在，一直向上找，找不是父节点的右节点节点
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}	
};


template<class K, class ValueType,class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<ValueType> Node;
public:
	RBTree()
		:_root(nullptr)
	{}
	
	typedef _RBTreeIterator<ValueType> iterator;
	iterator begin()
	{
		Node* left = _root;//找到红黑树的最左节点
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}

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

	pair<iterator,bool> Insert(const ValueType& value)
	{
		//若树为空，直接插入
		if (_root == nullptr)
		{
			_root = new Node(value);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}

		//不为空，先找到插入位置再插入节点
		Node* parent = nullptr;
		Node* cur = _root;
		KeyOfValue kov;

		while (cur)
		{
			parent = cur;
			if (kov(value) < kov(cur->_value))
				cur = cur->_left;
			else if (kov(value) > kov(cur->_value))
				cur = cur->_right;
			else
			{
				return make_pair(iterator(cur),false);//如果树中已经有该元素，则插入失败
			}
				
		}

		//找到插入位置，插入节点
		//插入的节点颜色为红色，破坏红黑树的性质3,更好处理
		cur = new Node(value);
		cur->_col = RED;
		if (kov(value) < kov(parent->_value))
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		else
		{
			parent->_right = cur;
			cur->_parent = parent;
		}

		//插入节点成功后，检查红黑树的性质有没有被破坏
		//若是有则要进行节点的颜色调整以满足红黑树性质
		//若是父节点存在且父节点的颜色为红色则需要调整，否则满足红黑树性质
		while (parent && parent->_col == RED)
		{
			// 注意：grandFather一定存在
			// 因为parent存在，且不是黑色节点，则parent一定不是根，则其一定有双亲
			Node* grandfather = parent->_parent;

			//1、父节点是祖父节点的左孩子
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				//1、叔叔节点存在且叔叔节点的颜色为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}

				//2、叔叔节点不存在或者叔叔节点的颜色为黑色
				else
				{
					//1、如果cur是parent的右孩子，此时需要进行左单旋将情况转换为情况2
					if (parent->_right == cur)
					{
						RotateL(parent);
						swap(cur, parent);
					}

					//1、如果cur是parent的z左孩子，此时只需进行一个右单旋，并将parent的颜色变为黑，grandparent的颜色置红
					RotateR(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}

			}

			//2、父节点是祖父节点的右孩子
			else
			{
				Node* uncle = grandfather->_left;
				//1、叔叔节点存在且叔叔节点的颜色为红色
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}

				//2、叔叔节点不存在或者叔叔节点的颜色为黑色
				else
				{
					//1、若是cur为parent的左孩子，先进行一个右单旋转换为情况二一起处理
					if (parent->_left == cur)
					{
						RotateR(parent);
						swap(cur, parent);
					}

					//2、若是cur为parent的右孩子，进行一个左单旋，并将parent的颜色变为黑，grandparent的颜色置红
					RotateL(grandfather);
					grandfather->_col = RED;
					parent->_col = BLACK;
					break;
				}
			}
		}

		//旋转完成之后，将根节点的颜色置成黑色
		_root->_col = BLACK;
		return make_pair(iterator(cur),true);
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* pparent = parent->_parent;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		parent->_parent = subR;

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

	//右单旋
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
		Node* pparent = parent->_parent;

		parent->_left = subLR;
		if (subLR)//置parent->_left的时候可以不管subLR是否为空，但是若是subLR为空取其parent就会出错
		{
			subLR->_parent = parent;
		}

		subL->_right = parent;
		parent->_parent = subL;

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

		}
	}


	void Inorder()
	{
		_Inorder(_root);
	}

	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;
		_Inorder(root->_left);
		cout << root->_value << ":" << root->_kv.second << endl;
		_Inorder(root->_right);
	}

	bool IsValidRBTree()
	{
		Node* pRoot = _root;

		// 空树也是红黑树
		if (nullptr == pRoot)
			return true;

		// 检测根节点是否满足情况
		if (BLACK != pRoot->_col)
		{
			cout << "违反红黑树性质二：根节点必须为黑色" << endl;
			return false;
		}

		// 获取任意一条路径中黑色节点的个数
		size_t blackCount = 0;
		Node* pCur = pRoot;
		while (pCur)
		{
			if (BLACK == pCur->_col)
				blackCount++;
			pCur = pCur->_left;
		}

		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
		size_t k = 0;
		return _IsValidRBTree(pRoot, k, blackCount);
	}

	bool _IsValidRBTree(Node* root, size_t k, const size_t blackCount)
	{
		if (nullptr == root)
			return true;

		// 统计黑色节点的个数
		if (BLACK == root->_col)
			k++;

		// 检测当前节点与其双亲是否都为红色
		Node* parent = root->_parent;
		if (parent && RED == parent->_col && RED == root->_col)
		{
			cout << "违反性质三：没有连在一起的红色节点" << endl;
			return false;
		}

		// 如果root是因子节点，检测当前路径中黑色节点的个数是否有问题
		if (nullptr == root->_left&& nullptr == root->_right)
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
		}

		//递归判断左右子树都满足红黑树的性质
		return _IsValidRBTree(root->_left, k, blackCount) &&
			_IsValidRBTree(root->_right, k, blackCount);
	}

private:
	Node* _root;
};

该图片转载至大佬博客：https://blog.csdn.net/Dawn_sf/article/details/78506299