深入理解C++系列（16）——红黑树的深度解析及模拟实现- 惊觉

⭐️博主： 此生决int-@CSDN博客

速胜派就是最大的投降派！！！

🔥热门专栏🔥

上期回顾

上一篇我们主要学习了 AVL树的模拟实现，了解了什么是AVL树，重点学习了平衡因子的更新，左单旋，右单旋，左右双旋，右左双旋。那么，今天我们来看与AVL树类似的，也是对二叉搜索树进行的优化，但是运用更加广泛的——红黑树！

红黑树

红黑树的定义

我们想对二叉搜索树进行优化，目的就是为了避免它出现一边倒的情况（即某棵左右子树中某一棵子树特别高）。
在这里插入图片描述

那 AVL 树是通过平衡因子来完成优化的，平衡因子保证了左右子树的高度差小于等于 1。而红黑树采用了另一种方式，即给每个节点带上颜色（红和黑），通过一些特定的规则来保证树的高度趋向于 log N。

红黑树的4条规则⭐️⭐️⭐️⭐️

一，每个节点不是黑色，就是红色。
二、根节点必须为黑色。
三、红节点的孩子一定不能是红色（即不能有两个相邻的红节点），所以，红节点的孩子一定是黑色或空。
四、每条路径上的黑色节点数量相同。
对于第四点，我们需要知道，这里的路经指的是：从根节点一直走到空的路线，才会算为一条路径！
例如：
在这里插入图片描述
根据红黑树的四条规则，我们可以得到：对于一棵拥有 N 个节点的红黑树，最短路径为h（即从根到空的最小高度），来说，他满足：2^h - 1 <= n < 2^{2h} - 1
$2^h - 1 \leq n < 2^{2h} - 1$
所以树的高度 h 就约等于 log n
两颗极端的红黑树：
在这里插入图片描述

红黑树的实现

红黑树的结构

与 AVL 树类似，只不过把平衡因子换成了颜色color，颜色只能为黑或者红

template<class K, class V>
struct RBTreeNode
{
	pair<K, V> _kv;
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	Colour _col;
	RBTreeNode(const pair<K, V>& kv)
	...
};

insert插入函数的实现

还是符合二叉搜索树的插入规则。前面还是一样，
1，先找到插入位置。
2，插入后，判断是否符合红黑树的四条规则。进行调整即可

找插入位置（二叉搜索树通用）

前面已经写过很多遍了，这里直接给代码：

Node* cur = _root;
Node* parent = _root;
while (cur)
{
	if (kv.first < cur->_kv.first)
	{
		parent = cur;
		cur = cur->_left;
	}
	else if (kv.first > cur->_kv.first)
	{
		parent = cur;
		cur = cur->_right;
	}
	else
		return false;
}

颜色更新

颜色更新和AVL树哪里一样，更新完插入节点的颜色后，要继续向上更新！即cur=grandfather
首先我们要明确两个基本规则：
1，你插入的节点的颜色一定是红色的，根除外
2，插入之后你插入的节点不能说又立刻变为黑色，那不就等于插入黑色吗？
解释：如果不插红，插黑，那玩个蛋啊？那一直插黑，整棵树都是黑色，那都不用更新了，那跟普通的二叉搜索树有什么区别？所以，插入节点一定是红色！
我们后面的研究要用到自己（cur节点）、自己的父亲（parent）、自己的爷爷（grandfather）以及叔叔（uncle）
然后，就会出现以下几种情况：1. The parent node is black: No action needed.
2. The parent node is red: Then we need to look at the situation of the uncle node.
(a) The uncle exists and is red:
(b) The uncle **does not exist or is black:

1，父亲为红，叔叔存在且为红！

调整策略：变色

即：父亲和爷爷换颜色，即父亲变为黑色，爷爷变为红色。
这是插入节点时的情况：
在这里插入图片描述
还有就是向上更新，更新后，cur为红，cur的父亲也为红！

在这里插入图片描述
代码实现：

while (parent&&parent->_col==RED)//父亲为红
{
	Node* grandfather = parent->_parent;
	Node* uncle = nullptr;
	if (parent == grandfather->_left)
	{
		uncle = grandfather->_right;//得到叔叔
			if (uncle && uncle->_col == RED)//叔叔存在且为红
			{
				//仅变色
				grandfather->_col = RED;
				uncle->_col = BLACK;
				parent->_col = BLACK;
			}

2，父亲为红，叔叔不存在或为黑

调整策略：旋转加变色

1，单旋+变色

适用场景：
满足父亲为红，叔叔不存在或为黑，并且他们之间的关系是这样的，我c和父亲p的关系，和父亲p和爷爷g的关系是一样的！
在这里插入图片描述

代码实现：

if (parent == grandfather->_left)//父亲是爷爷的左孩子
{
	uncle = grandfather->_right;//得到叔叔
		if (uncle && uncle->_col == RED)//叔叔存在且为红
             ...
		else if (parent->_left == cur)//叔叔不存在或为黑，然后有分，我和父亲的关系和父亲和爷爷的关系是一样的，都是左孩子
		{
			//右单旋
			RotateR(grandfather);
			//变色
			parent->_col = BLACK;
			grandfather->_col = RED;
			break;
		}

2，双旋+变色

与单旋的情况正好相反。这里我、父亲、叔叔和爷爷的关系为
在这里插入图片描述
这恰好和单双旋的性质是一样的！

代码实现：

if (parent == grandfather->_left)//父亲是爷爷的左孩子
{
	uncle = grandfather->_right;//得到叔叔
		if (uncle && uncle->_col == RED)//叔叔存在且为红
         ...
		else if (parent->_left == cur)//父亲是左，我也是左
		...
		else if (parent->_right == cur)//我c是父亲p的右孩子，双旋
		{
			//左右双旋
			RotateL(parent);
			RotateR(grandfather);
			cur->_col = BLACK;
			grandfather->_col = RED;
			break;
		}

以上都是父亲是爷爷的左孩子的情况，另一种情况大差不差！

旋转函数的实现

这里的旋转函数和AVL树1的几乎一致，不过，不用更新平衡因子
代码：

// 右旋
void RotateR(Node* parent)
{
	Node* sub = parent;
	Node* subL = parent->_left;
	Node* pparent = parent->_parent;
	Node* subLR = subL->_right;
	sub->_left = subLR;
	if (subLR)subLR->_parent = sub;
	subL->_right = sub;
	sub->_parent = subL;
	if (pparent == nullptr)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else if (pparent->_left == sub)
	{
		pparent->_left = subL;
		subL->_parent = pparent;
	}
	else if (pparent->_right == sub)
	{
		pparent->_right = subL;
		subL->_parent = pparent;
	}
	else
		assert(false);
}
// 左旋
void RotateL(Node* parent)
{
	Node* sub = parent;
	Node* subR = parent->_right;
	Node* pparent = parent->_parent;
	Node* subRL = subR->_left;
	sub->_right = subRL;
	if (subRL) subRL->_parent = sub;
	subR->_left = sub;
	sub->_parent = subR;
	if (pparent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else if (pparent->_left == sub)
	{
		pparent->_left = subR;
		subR->_parent = pparent;
	}
	else if (pparent->_right == sub)
	{
		pparent->_right = subR;
		subR->_parent = pparent;
	}
	else
		assert(false);
}

insert完整代码

// 插入
bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		_root->_col = BLACK;
		return true;
	}
	//依旧先找到插入位置
	Node* cur = _root;
	Node* parent = _root;
	while (cur)
	{
		if (kv.first < cur->_kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else
			return false;
	}
	cur = new Node(kv);
	//还是要根据kv来比！！！！，第三次犯这个错误了！！！
	/*if (parent->_left == cur)
	{
		parent->_left = new Node(kv);
	}
	else if (parent->_right == cur)
		parent->_right = new Node(kv);
	else assert(false);*/
	if (kv.first < parent->_kv.first)
	{
		parent->_left = cur;
		cur->_parent = parent;
	}
	else if (kv.first > parent->_kv.first)
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else
		assert(false);
	//更新颜色
	//情况一：父亲是黑是，不用处理
	//情况二：父亲是红色
	//1，叔叔存在，也是红色
	//2，叔叔不存在，或者是黑色
	//2.1单旋+变色
	//2.2双旋+变色

	while (parent&&parent->_col==RED)//父亲为红
	{
		Node* grandfather = parent->_parent;
		Node* uncle = nullptr;
		if (parent == grandfather->_left)//父亲是爷爷的左孩子
		{
			uncle = grandfather->_right;//得到叔叔
				if (uncle && uncle->_col == RED)//叔叔存在且为红
				{
					//仅变色
					grandfather->_col = RED;
					uncle->_col = BLACK;
					parent->_col = BLACK;
				}
				else if (parent->_left == cur) // 叔叔不存在或为黑，然后有分，我和父亲的关系和父亲和爷爷的关系是一样的，都是左孩子
				{
					//右单旋
					RotateR(grandfather);
					//变色
					parent->_col = BLACK;
					grandfather->_col = RED;
					break;
				}
				else if (parent->_right == cur)//我c是父亲p的右孩子，双旋
				{
					//左右双旋
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
					break;
				}
				else
					assert(false);
			
		}
		else if (parent == grandfather->_right)
		{
			uncle = grandfather->_left;
			
				if (uncle && uncle->_col == RED)
				{
					//仅变色
					grandfather->_col = RED;
					uncle->_col = BLACK;
					parent->_col = BLACK;
				}
				else if (parent->_right == cur)//uncle存在与否已经不重要了
				{
					//左单旋
					RotateL(grandfather);
					//变色
					parent->_col = BLACK;
					grandfather->_col = RED;
					break;
				}
				else if (parent->_left == cur)
				{
					//右左双旋
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
					break;
				}
				else
					assert(false);
		}
		else
			assert(false);
		//继续更新
		cur = grandfather;
		parent = cur->_parent;
	}
	//根一定是黑，最后统一处理，
	_root->_col = BLACK;
	return true;

}

IsBalance，是否是平衡的红黑树

检查一棵树是否是红黑树，只需要看它是否满足红黑树的四个规则。第一和第二规则很显然，我们用宏定义了红和黑两种颜色，并且插入后都对根进行了变色，强制变为黑，不用测试，只需要验证它是否满足第三和第四个规则即可。
第三个规则，我们只需要前序遍历一棵树。如果是红节点，那我们只需要看他的父亲是否为红节点即可。
第四个规则，我们可以先走出一条路，得到那条路径上黑色节点的数量。
然后进行递归：用一个递归来统计走到空节点时，路径上的黑色节点数量是否等于我们最开始统计的那个数值。

代码如下：

// 检查红黑树是否平衡
bool IsBalance()
{
	if (_root == nullptr)return true;
	Node* cur = _root;
	int refnum = 0;
	while (cur)
	{
		if (cur->_col == BLACK)
			refnum++;
		cur = cur->_left;
	}
	return Check(_root, 0, refnum);
}
private:
// 检查红黑树性质
bool Check(Node* root, int blackNum, const int refNum)
{
	//满足四条规则：
	//1,2，肯定不用看，
	//3，所有的红节点的父亲是不是红色
	//4，路径黑色是不是一样多
	//前序遍历
	if (root == nullptr)
	{
		if (blackNum != refNum)
			return false;
		else
			return true;
	}
	if (root->_col == BLACK)blackNum++;
	if (root->_col == RED)
	{
		if (root->_parent&&root->_parent->_col == RED)
			return false;
		else if (root->_parent == nullptr)
		{
			if (root->_col == RED)
			{
				cout << "根节点为红色！！" << endl;
				return false;
			}
		}
	}
	
	return Check(root->_left,blackNum,refNum) && Check(root->_right, blackNum, refNum);
}

下期预告

封装map和set

结语

本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。
也欢迎订阅我的
深入理解 C++系列：从语法入门到底层原理，系统掌握现代 C++
算法系列：从入门到精通，蓝桥杯、ACM、LeetCode 与面试算法全路线
快速复习系列：知识梳理、查漏补缺，考前冲刺必备
Java 速通系列：已学 C 语言，快速上手 Java，轻松备战期末考试

愿每一次敲下键盘，都比昨天更进一步！ 愿每一行代码落下，都让未来多一种可能！

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/2502_94353935/article/details/163566624

深入理解C++系列（16）——红黑树的深度解析及模拟实现

文章目录