手撕红黑树

红黑树的概念

由于AVL对于平衡的要求过于严格，这就导致了AVL的调整操作会被大量的进行，别看单词的时间消耗短，由于AVL树对于平衡要求的苛刻，这就会积累大量的旋转操作，这一累加起来就是不小的时间消耗；
为了减少AVL树的旋转操作，红黑树不就诞生了！
红黑树:红黑树不是一颗严格的二叉树，只是一颗近似平衡的二叉树；
满足一下性质的树就是一颗红黑树:

1. 首先得是一颗搜索二叉树；
2. 节点不是黑色就是红色；
3. 根节点必须是黑色；
4. 红色节点的左右孩子不允许是红色节点(这一点保证了红黑树不会有两个连续的红色节点)；
5. 红黑树的叶子节点是黑色的，其中这里的叶子节点不是度为0的节点，而是空节点；
6. 从任意一个节点到其后代所有叶子节点的路径上的黑色节点数必须相等！
   满足上面这些条件的二叉树就叫红黑树；
   
   思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点
   个数的两倍?
   假设某一个节点到其所有后代叶子节点的路径上的黑色节点数都是N个；
   那么该节点到其后代叶子叶子节点的最短路劲是不是就是这N个黑色节点组成的；
   同理，该节点到其后代叶子节点的最长路径是不是就是红黑相间的节点组成的，那么这个路径的长度不就是2N嘛；
   那么最长路径/最短路径不就刚好等于2嘛，这还是我们模拟的极端情况，实际情况是，我们的路径一定比最长路径短，一定不最短路径长，那么这么一除不就是红黑树中任意一个节点的任意两条路径的长度之商（长/短）都不会超过2,这不就保证了其最长路径中节点个数不会超过最短路径节点个数的两倍；

红黑树节点定义

//定义颜色
#define RED true//红色
#define BLOCK false//黑色
//红黑树节点
//T表示存放的数据的类型
template<class T>
struct RBTNode
	{
		RBTNode(const T&data)
			:_data(data),
			_color(RED),
			_left(nullptr),
			_right(nullptr),
		   _parent(nullptr)
		{}

		bool _color;//标记节点颜色
		T _data;//有效数据
		RBTNode<T>* _left;
		RBTNode<T>* _right;
		RBTNode<T>* _parent;
	};

从上面的定义中我们可以看到，我们将节点的默认颜色给成的红色，可是为什么要给红色，为什么不给黑色呢？
假设，我们给了黑色，我们进行插入过后，势必会造成 “插入节点” 的任意一个祖先节点都不在满足从该节点到其所有后代节点的路径上的黑色节点数目相等，在 “插入节点” 这条路劲上黑色节点的数目始终会比其他路径多一个，这就导致了我们插入节点过后改变了红黑树的性质，我们必须对其进行调整让其在插入节点过后还是颗红黑树，可是这样的话我们每插入一次就需要调整一次，那么这插入的成本也太高了！
假设，默认插入的是红色节点，我们进行插入过后，必然不会造成 “插入节点” 的任意一个祖先节点从该节点到其所有后代节点的路径上的黑色节点数目不相等，因为我这个“新插入”的节点必然是插在这些祖宗节点的某一条路径上面的，我们在利用红色节点进行插入过后，并没有使这条路径上的黑色节点数目改变，因此是满足上面的性质6的，可是我们还需要进行经一不检查，性质6是满足了，性质5就不一定了，如果“新插入的节点”的父节点是红色的话，那么我们是不是就要进行调整了，因为红黑树不允许出现两个连续的红色节点；可是如果父节点是黑色的话，那么我们这次插入不就是完美了嘛！
相比于两种情况，一种是插入了必调整，一种是插入了可能调整，二者谁的成本高一目了然；
为此我们采用的节点的默认颜色就是红色！

节点有了，我们再来把红黑树这个结构也定义一下吧：

//红黑树
//K,表示key的类型
//V,表示节点数据域的类型
//KeyOfValue:用于获取_data数据域的key值
//Compare:用于自定义比较，默认小于
template<class K,class V,class KeyOfValue,class Compare=std::less<K>>
class RBTree
{
	typedef RBTNode<V> Node;//红黑树的节点
public:
	RBTree()
		:_root(nullptr)
	{}
private:
	Node* _root;
}；

我来解释一下红黑树这些参数的意义:
K:表示key值的类型，用于find()函数使用的
V:表示的是实际要存储的数据类型;
KeyOfValue:是一个仿函数，由用户提供，是用于获取_data数据的中的Key值的，因为_data的类型不一定是一个自定义类型，也可能就是Key本身；
Compare：自定义Key的比较方式；
至于参数为什么这样设计:
1、主要是由于set和map底层是用红黑树实现的；
2、红黑树本身就是KV模型，对于map直接使用是没问题的，但是对于set来说由于只有key值，那么使用KV模型的红黑树就需要调整一下策略了；
map的模板参数是<Key,Value>,那么如果给红黑树传参的话，就是:<Key,pair<const Key,Value>,KeyOfValue,less< Key> >;
set的模板参数只有< Key>,那么如果给红黑树传参的话就是:<Key,Key,KeyOfValue,less< Key>>;
由于set和map对应的红黑树中的节点类型是不一样的，我们无法在红黑树中用一种统一的方式来获取Key值，因此我们需要set和map给红黑树自己传递一个能够获取节点的Key值的仿函数；

insert

我们就简单的手撕一下红黑树的插入吧；
老样子，我们先写入二叉搜索树的插入模板:

bool insert(const V& data)
{
	
	KeyOfValue kof;
	Compare com;
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_color = BLOCK;
		return true;
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		parent = cur;
		if ( com(kof(cur->_data),kof(data)))
		{
			cur = cur->_right;
		}
		else if (com(kof(data), kof(cur->_data)))
		{
			cur = cur->_left;
		}
		else
			return false;
	}
	cur = new Node(data);
	cur->_parent = parent;
	Node* tmp = cur;
	if (com(kof(cur->_data),kof(parent->_data)))
		parent->_left = cur;
	else
		parent->_right = cur;
	//检查插入节点过后，是否还是红黑树
	Node* grandfather = nullptr;
	Node* uncle = nullptr;
	//这里我们需要检测父亲是否也是红色节点
	while (parent && parent->_color == RED)
	{
		//父亲是红色节点，进行调整操作;
	}
	return true;
}

为了表述方便，我们就用parent表示父节点；
cur表示插入节点；
grandfather:表示爷爷节点；
uncle:表示叔叔节点；

只有当父亲是红色节点时，我们才进行调整：
分析:
如果父亲是红色节点的话，那么父亲一定不是根节点，因为根节点的颜色一定是黑色，那么grandfather一定存在且为黑色，如果grandfather为红色，那么说明在插入之前这棵树就不在是红黑树了；

对于如何调整的策略，有分为这几种情况:
①uncle节点存在且为红

很明显,cur和parent这两个节点存在了连续的红色节点，此时这整科数已经不在是红黑树了，我们需要对其进行调整；
这调整的原则就是:从grandfather节点(未调整以前的)的父节点看下来，这颗子树的任意一条路径上的黑色节点数目不变！ 记住这一个原则我们就可以完成红黑树的调整了，举个例子:

为此，对于uncle节点存在且为红色的情况的旋转方式就是:
将parent节点与uncle节点都染成黑色，grandfather节点染成红色：

如果我们像这样调整的话，再从pg节点的右子树来看：pg节点的右子树中的每一条路径是不是都至少有一个黑色节点，与调整前的要求一致，同时我cur节点和parent节点也解决了连续红色节点相连接的问题，这样的调整方案，堪称完美，可是这就完了吗？
显然没有，我们的grandfather节点被染成了红色，我们又不确定pg节点的颜色，如果pg节点的颜色也为红色，那么不是又出现了两个连续的红色节点:

这样一来，又不满足红黑树的要求了，因此我们需要继续往上调整:
cur=parent;
parent=grandfather;
grandfather=grandfather->_parent;
但是如果pg节点的颜色是黑色，那么就不存在两个红色节点相连接，此次插入很完美！我们可以退出了：

当然，对于上面我们只是讨论LL类型，其实还有LR、RR、RL类型由于这些情况的处理方法都是一样的，为此读者们可以自己验证；

②uncle节点不存在

而针对uncle不存在这种情况，我们又可以对其进行细分：

1. grandfather与parent、cur节点成LL型：
   
   从图中我们可以看到：调整之前，pg节点的右子树中的每一条路径至少都有一个黑色节点，那么秉承着前面调整的原则，我们再调整之后也需要保持pg节点的右子树中的每一条路径都至少有一个黑色节点：
   为此，我们的调整策略就是:
   将grandfather这颗子树进行右旋，关于什么是右旋、左旋可以移步至我的另一篇博客:二叉搜索树(内含AVL树的旋转操作的详细解释)；
   于是我们就得到了如下的一颗子树:
   
   可是我们发现调整过后的子树中并不能满足pg的右子树中的每一条路径都含有至少有1个黑色节点的数目：为此，我们还需要进行进一步的染色处理，你看，如果我们将parent节点染成黑色，grandfather节点染成红色，是不是就满足了调整d原则了，同时也将parent与cur这两个连续红色节点的条件给消除了:
   
   这样我们就完成了本次的处理，同时我们也不需要继续往上调整了，因为pg节点的右节点都是黑色了，无论pg节点本身是什么颜色都能保证整颗红黑树是合法的！为此在调整完毕过后，我们可以立马break；
2. grandfather与parent、cur节点成LR型:
   
   对于这种情况，我们的调整策略是:
   a.现将parent这课子树进行左旋:
   
   我们可以发现，虽然调整前后满足调整的原则，但是cur和parent这两个红色节点还是连接在一起的，不是特别合适,为此我们还需要进行旋转，实际上通过查看旋转过后的树，我们可以发现这和LL型的模型是一模一样的，因此，我们可以采取针对LL型模型的处理方法;
   b. 将grandfather这课子树进行右旋：
   
   c. 再根据调整原则进行染色:
   将cur节点染成黑色；
   grandfather节点染成红色;
   
   这样的话，本次调整就完美完成了，也不需要继续往上调整了，因为pg的右节点是黑色，无论pg节点本身是什么颜色都满足红黑树的特点；
3. grandfather与parent、cur节点成RR型:
   
   调整策略:
   将grandfather这课子树进行左旋:
   
   然后再根据染色的原则，
   将parent节点染成黑色;
   grandfather节点染成红色;
   
4. grandfather与parent、cur节点成RL型:
   
   >调整策略:
   a. 现将parent这课树进行右旋:
   
   从图中看出来，将parent这课树进行右旋过后，grandfather这课树就变成了RR模型，为此我们采用RR模型的处理方式来解决:
   b. 将grandfather这颗树进行左旋:
   
   c. 根据染色原则进行染色:
   cur染成黑色；
   grandfather染成红色;

③uncle节点存在且为黑;

这样的话，pg这个节点的右子树中的每一条路径都需要至少含有两个黑色节点！为此我们再用上面的图来讨论就不死那么合适了，我们需要对上面的图做一下处理，让其保证grandfather这课子树中的任意一条路径黑色节点数至少为2：

这样就保证了，grandfather这课子树中的每一条路径的黑色节点数至少是2个;

1. grandfather与parent、cur节点成LL型:
   
   调整策略:
   将grandfather这课子树进行右旋:
   
   然后根据染色原则，
   将parent节点染成黑色，
   grandfather节点染成红色;
2. grandfather与parent、cur节点成LR型:
   
   调整策略:
   a. 先将parent这课子树进行右旋:
   
   b. 在将grandfather这课子树进行右旋:
   
   c. 然后根据调整原则进行染色:
   cur染黑色；
   grandfather染成红色:
   
3. grandfather与parent、cur节点成RR型:
   
   调整策略:
   将grandfather这课树进行右旋:
   
   然后根据染色原则，
   将parent染成黑色，
   grandfather染成红色:
   
4. grandfather与parent、cur节点成RL型:
   
   调整策略:
   a. 将parent这棵树进行右旋:
   
   b. 将grandfather这课树进行左旋:
   
   c. 根据调整原则，进行染色:
   cur染成黑色,
   grandfather染成红色:
   

综上所述,也就这三种大情况，同时通过上面的讨论为我们可以知道，对于uncle不存在/uncle存在且为黑这两种情况来说处理方法是完全一样的，我们可以合并为一起处理，这样的话，最终的情况也就变为了2种,下面是代码实现,可能有点略有不同(博主主要是跟着STL的新式保持一致，看不懂的地方可以去查手册，但是大体逻辑是不变的):

std::pair<iterator,bool> insert(const V& data)
{
	//insert的返回值pair<iterator,bool>
	//插入位置的迭代器和插入是否成功
	KeyOfValue kof;
	Compare com;
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_color = BLOCK;
		return std::make_pair(iterator(_root),true);
	}
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		parent = cur;
		if ( com(kof(cur->_data),kof(data)))
		{
			cur = cur->_right;
		}
		else if (com(kof(data), kof(cur->_data)))
		{
			cur = cur->_left;
		}
		else
			return std::make_pair(iterator(cur), false);
	}
	cur = new Node(data);
	cur->_parent = parent;
	Node* tmp = cur;
	if (com(kof(cur->_data),kof(parent->_data)))
		parent->_left = cur;
	else
		parent->_right = cur;
	//检查插入节点过后，是否还是红黑树
	Node* grandfather = nullptr;
	Node* uncle = nullptr;
	while (parent && parent->_color == RED)
	{
		//cur为红，parent为红，grandfather一定存在
		grandfather = parent->_parent;
		//确定叔叔节点的位置
		if (parent == grandfather->_left)
			uncle = grandfather->_right;
		else
			uncle = grandfather->_left;
		//根据叔叔分情况
		//1、叔叔不存在或者||叔叔存在且为黑,这两种情况处理方式一样，可以归为一类
		if (uncle == nullptr || uncle->_color == BLOCK)
		{
			if (grandfather->_left == parent && parent->_left == cur)//LL
			{
				RotateR(grandfather);
				parent->_color = BLOCK;
				grandfather->_color = RED;
			}
			else if (grandfather->_left == parent && parent->_right == cur)//LR
			{
				RotateL(parent);
				RotateR(grandfather);
				cur->_color = BLOCK;
				grandfather->_color = RED;
			}
			else if (grandfather->_right == parent && parent->_right == cur)//RR
			{
				RotateL(grandfather);
				parent->_color = BLOCK;
				grandfather->_color = RED;
			}
			else if (grandfather->_right == parent && parent->_left == cur)//RL
			{
				RotateR(parent);
				RotateL(grandfather);
				cur->_color = BLOCK;
				grandfather->_color = RED;
			}
			else
				assert(false);
			break;
	
		}//2、叔叔存在且为红
		else if (uncle->_color == RED)
		{
			//p->黑，u->黑,g->变红
			parent->_color = BLOCK;
			uncle->_color = BLOCK;
			grandfather->_color = RED;
			//grandfather为红，有可能与其父亲是连续红，需要向上继续调整
			cur = grandfather;
			parent = cur->_parent;
			//如果已经无法向上调整了，说明grandfather就是根节点，我们需要矫正根节点的颜色;
			if (parent == nullptr)
				grandfather->_color = BLOCK;
		}
		else//出现其他情况直接报错
			assert(false);
	}
	return std::make_pair(iterator(tmp), true);
}


//右旋
void RotateR(Node* parent)
{
	KeyOfValue kof;
	Compare com;
	Node* SubL = parent->_left;
	Node* SubLR = SubL->_right;
	Node* ppNode = parent->_parent;
	parent->_left = SubLR;
	if (SubLR)//SubLR节点存在
		SubLR->_parent = parent;
	SubL->_right = parent;
	parent->_parent = SubL;
	if (ppNode == nullptr)//parent是根节点
	{
		SubL->_parent = nullptr;
		_root = SubL;
	}
	else
	{
		SubL->_parent = ppNode;
		if (com(kof(SubL->_data), kof(ppNode->_data)))
			ppNode->_left = SubL;
		else
			ppNode->_right = SubL;
	}
}

//左旋
void RotateL(Node* parent)
{
	KeyOfValue kof;
	Compare com;
	Node* SubR = parent->_right;//这个节点一定存在，可以证明
	Node* SubRL = parent->_right->_left;//这个节点就不一定存在了
	Node* ppNode = parent->_parent;//提前记录一下parent的父亲
	//开始链接SubRL节点
	parent->_right = SubRL;
	if (SubRL)//只有当这个节点存在时，才需要维护器=其父亲节点
		SubRL->_parent = parent;
	//开始链接parent节点
	SubR->_left = parent;
	parent->_parent = SubR;
	
	//开始链接SubR节点
	if (ppNode == nullptr)//如果parent就是根，那么需要更新根节点
	{
		SubR->_parent = nullptr;
		_root = SubR;
	}
	else//parent不是根节点
	{
		SubR->_parent = ppNode;
		if (com(kof(SubR->_data), kof(ppNode->_data)))
			ppNode->_left = SubR;
		else
			ppNode->_right = SubR;
	}
}

红黑树的验证

我们写完了红黑树的插入，必然要检查一下红黑树的合法性，为此，我们可以从一下几个方面进行验证:
0、检查是否是二叉搜索树(中序打印结果);
1、判断根节点是不是黑色;
2、判断是否存在连续的红色节点;
3、判断是否任意一个节点到其后代叶子节点的所有路径上的黑色节点数目均相等;

//检查是否是二叉搜索树(中序打印结果);
void inoder()const
{
	KeyOfValue kof;
	std::stack<Node*> st;
	Node* cur = _root;
	while (cur || st.empty() == false)
	{
		while (cur)
		{
			st.push(cur);
			cur = cur->_left;
		}
		std::cout << kof(st.top()->_data) << " ";
		cur = st.top()->_right;
		st.pop();
	}
std::cout << std::endl;
}

//检查1、2、3合在一起检查
bool check()const
{
	if (_root == nullptr)
		return true;
	//1、检查根是否为黑色
	if (_root->_color == RED)
		return false;
	//2、检查是否有连续的红色节点
	if (red(_root) == true)
		return false;
	//3、检查一颗树的所有路径的黑节点数目是否相等
	return same(_root);
}
//检查是否有连续的红色节点
bool red(Node* root)const
{
	if (root == nullptr)
		return false;
	if (root->_color == RED && root->_parent->_color == RED)
		return true;
	return red(root->_left) && red(root->_right);
}

//检查该树中的任意一个节点的所有路径上的黑节点数目是否相等
bool same(Node* root)const
{
	if (root == nullptr)
		return true;
	int size = 0;
	Node* cur = root;
	//先求出该树的任意一条路径，的黑节点的个数
	while (cur)
	{
		if (cur->_color == BLOCK)
			size++;
		cur = cur->_left;
	}
	//先检查根节点的所有路径上黑节点数目是否相等
	if (check_path(root,size) == false)
		return false;
	//用同样的方法检测左子树，右子树
	return same(root->_left)&&same(root->_right);
}

//先检查根节点的所有路径上黑节点数目是否相等
bool check_path(Node* root,int size)const
{
	if (root == nullptr)
		return size == 0 ? true : false;
	if (root->_color == BLOCK)
		size--;
	return check_path(root->_left, size) && check_path(root->_right, size);
}

红黑树的迭代器

红黑树的迭代器，就是针对Node* 节点的封装

正向迭代器

//正向迭代器
	template<class V, class Sef, class Ptr>
	class ___RBTree___iterator___
	{
		typedef ___RBTree___iterator___<V, Sef, Ptr>  Self;//正向迭代器
		typedef  RBTNode <V>  Node;//红黑树的节点
	public:
		___RBTree___iterator___(Node* cur = nullptr) :_cur(cur)
		{}
		bool operator!=(const Self& s)const
		{
			return _cur != s._cur;
		}
		//前置--
		Self& operator--()
		{
			//右子树 根 左子树
			if (_cur->_left)
			{
				_cur = _cur->_left;
				while (_cur->_right)
				{
					_cur = _cur->_right;
				}
			}
			else
			{
				Node* parent = _cur->_parent;
				//_cur==parent->_left,说明_cur是parent的左子树，表示parent这课树访问完了
				//继续往上走
				while (parent && parent->_left == _cur)
				{
					parent = parent->_parent;
					_cur = _cur->_parent;
				}
				_cur = parent;
			}
			return *this;
		}
		//前置++
		Self& operator++()
		{
			if (_cur->_right)
			{
				_cur = _cur->_right;
				while (_cur->_left)
				{
					_cur = _cur->_left;
				}
			}
			else
			{
				Node* parent = _cur->_parent;
				while (parent && parent->_right == _cur)
				{
					_cur = _cur->_parent;
					parent = parent->_parent;
				}
				_cur = parent;
			}
			return *this;
		}

		Sef operator*()
		{
			return _cur->_data;
		}
		Ptr operator->()
		{
			return &(_cur->_data);
		}
	private:
		Node* _cur;
	};
}

反向迭代器

//反向迭代器
	//It:封装的正向迭代器
	//Sef:*的返回值
	//Ptr:->的返回值
	//根据是不是const对象来决定传那个参数
	template<class It,class Sef,class Ptr>
	class ___RBTree__reverse_iterator___
	{
	typedef ___RBTree__reverse_iterator___<It,Sef,Ptr> ReSelf;
	public:
		explicit ___RBTree__reverse_iterator___(const It& it=It()) :_it(it) {};
		bool operator!=(const ReSelf& rit)
		{
			return _it != rit._it;
		}
		//前置++,也就是正向迭代器的--
		ReSelf& operator++()
		{
			--_it;
			return *this;
		}
		//前置--也就是正向迭代器的++
		ReSelf& operator--()
		{
			++_it;
			return *this;
		}
		Sef operator*()
		{
			return *_it;
		}
		Ptr operator->()
		{
			return _it.operator->();
		}
			private:
		It _it;//正向迭代器
	};

class RBTree 类中:文章来源地址https://www.toymoban.com/news/detail-441505.html

template <class K,class V,class KeyOfValue,class Compare=less<K>>
class RBTree
{
typedef RBTNode<V> Node;//红黑树的节点
	public:
//正向迭代器
typedef ___RBTree___iterator___<V, V&, V*> iterator;
typedef ___RBTree___iterator___<V, const V&, const V*> const_iterator;
//反向迭代器
typedef ___RBTree__reverse_iterator___<iterator, V&, V*> reverse_iterator;
typedef ___RBTree__reverse_iterator___<const_iterator, const V&, const V*> const_reverse_iterator;
	private:
	Node*_root;
};

到了这里，关于手撕红黑树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！