【数据结构】红黑树

红黑树的概念

红黑树的性质

红黑树结点的定义

红黑树的插入

平衡化操作

情形一：uncle结点存在且为红

情形二：uncle结点不存在或者存在且为黑

红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black；通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的；

红黑树的性质

性质一: 每个结点不是红色就是黑色；

性质二: 根节点是黑色的；

性质三: 如果一个节点是红色的，则它的两个孩子结点必须是黑色的(即没有连续的红色结点)

性质四: 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(即每条路径都包含相同数量的黑色结点)；

性质五:每个叶子结点都是黑色的(此处的叶子结点指的是空结点)；

思考一：为什么满足上面的性质，红黑树就能保证:其最长路径中节点个数不会超过最短路径节点个数的两倍？

当某条路径最短时，这条路径上所有节点必然由黑色节点构成，由于性质四限定了从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点，所以最长路径上的黑节点的数目和最短路径上的黑节点的数目相等，由于性质三限定不能出现两个连续的红色节点，因此最长路径必然是由红色和黑色节点交替构成；

最短路径：全黑 最长路径：一黑一红

思考二：节点的定义中，需要将节点的默认颜色设置为黑色还是红色？

若将节点的默认颜色设置为黑色，一定会违反红黑树的性质四：从任一节点到其每个叶子节点的所有路径必须包含相同数量的黑色节点；

若将节点的默认颜色设置为红色，若插入位置的父节点为黑色，未违反红黑树性质，则插入结束；若插入位置的父节点为红色，则出现连续的红色结点违反红黑树性质三，需要处理；

因此结点的默认颜色设置为红色；

红黑树结点的定义


enum Color
{
	RED,
	BLACK
};
template<class k,class v>
struct RBTreeNode
{
	RBTreeNode* _left;//指向左孩子
	RBTreeNode* _right;//指向右孩子
	RBTreeNode* _parent;//指向父节点
	Color _col;//结点颜色
	pair _kv;//存储有效数据
 
	//节点类的构造函数
	RBTreeNode(const pair& kv)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		, _kv(kv)
	{}
};

红黑树的插入

红黑树的插入分为两步：

按照搜索二叉树的规则插入新节点（红色节点）；
检测插入红色结点后，若插入位置的父节点为黑色，未违反红黑树性质，则插入结束；检测插入红色结点后，若插入位置的父节点为红色，需要对红黑树进行平衡化操作；


template <class k, class v>
class RBTree
{
	typedef RBTreeNode Node;
public:
	//首先按照搜索二叉树的规则插入数据
	bool Insert(const pair& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			//红黑树根结点为黑色
			_root->_col = BLACK;
			return true;
		}
		//parent记录父节点的位置,cur寻找插入位置
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur != nullptr)
		{
			//根据键值key比较,确定迭代左子树或是右子树
			if ((cur->_kv).first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if ((cur->_kv).first>kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			//为维护搜索二叉树逻辑结构,同一颗树不能出现相等的数值
			else
			{
				return false;
			}
		}
		//开辟结点,存储数据，建立链接关系
		cur = new Node(kv);
		if ((parent->_kv).first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
        
		//平衡化操作
		//...
 
		return true;
	}
private:
	Node* _root = nullptr;
};

平衡化操作

规定：

cur 为新增节点，p (parent)为父节点，g (grandfather)为祖父节点，u (uncle)为叔叔节点；

情形一：uncle结点存在且为红

具象图：

若调整过程中cur的父结点p为空，说明cur为根节点，已经调整到根结点处，此时将根节点改为黑色；

情形二的处理方式为旋转加变色(稍后讨论)，情形一向上迭代的过程中可能会产生情形二；

抽象图：

无论父亲p/叔叔u是爷爷g的左孩子还是右孩子，无论cur是父亲p的左孩子还是右孩子，情形一的处理方式相同，对变色毫无影响；

情形二：uncle结点不存在或者存在且为黑

uncle结点不存在

case 1：p为g的左孩子，cur为p的左孩子，进行右单旋，p变黑，g变红；

case 2：p为g的右孩子，cur为p的右孩子，进行左单旋，p变黑，g变红；

case 3：p为g的左孩子，cur为p的右孩子，进行左右双旋，cur变黑，g变红；

case 4：p为g的右孩子，cur为p的左孩子，进行右左双旋，cur变黑，g变红；

uncle结点存在且为黑

case 1：p为g的左孩子，cur为p的左孩子，进行右单旋，p变黑，g变红；

case 2：p为g的右孩子，cur为p的右孩子，进行左单旋，p变黑，g变红；

case 3：p为g的左孩子，cur为p的右孩子，进行左右双旋，cur变黑，g变红；

case 4：p为g的右孩子，cur为p的左孩子，进行右左双旋，cur变黑，g变红；

抽象图：

左旋代码实现


void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
 
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
 
	subR->_left = parent;
	Node* ppnode = parent->_parent;
	parent->_parent = subR;
 
	if (parent == _root)
	{
		_root = subR;
		subR->_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;
 
	subL->_right = parent;
 
	Node* ppnode = parent->_parent;
	parent->_parent = subL;
 
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = subL;
		}
		else
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
}

Insert()函数代码实现


//首先按照搜索二叉树的规则插入数据
bool Insert(const pair& kv)
{
	if (_root == nullptr)
	{
		_root = new Node(kv);
		//红黑树根结点为黑色
		_root->_col = BLACK;
		return true;
	}
	//parent记录父节点的位置,cur寻找插入位置
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur != nullptr)
	{
		//根据键值key比较,确定迭代左子树或是右子树
		if ((cur->_kv).first < kv.first)
		{
			parent = cur;
			cur = cur->_right;
		}
		else if ((cur->_kv).first>kv.first)
		{
			parent = cur;
			cur = cur->_left;
		}
		//为维护搜索二叉树逻辑结构,同一颗树不能出现相等的数值
		else
		{
			return false;
		}
	}
	//开辟结点,存储数据，建立链接关系
	cur = new Node(kv);
	if ((parent->_kv).first > kv.first)
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
        
	//平衡化操作
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			// 情况一：叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
 
				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// 情况二：叔叔不存在或者存在且为黑
				// 旋转+变色
				if (cur == parent->_left)
				{
					//       g
					//    p    u
					// c
					RotateR(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//       g
					//    p     u
					//      c
					RotateL(parent);
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
 
				break;
			}
		}
		//parent==grandfather->_right
		else
		{
			Node* uncle = grandfather->_left;
			// 情况一：叔叔存在且为红
			if (uncle && uncle->_col == RED)
			{
				// 变色
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
 
				// 继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// 情况二：叔叔不存在或者存在且为黑
				// 旋转+变色
				//      g
				//   u     p
				//            c
				if (cur == parent->_right)
				{
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					//		g
					//   u     p
					//      c
					RotateR(parent);
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
 
				break;
			}
		}
	}
	_root->_col = BLACK;
	return true;
}

红黑树的验证

红黑树的检测分为两步：

检测其是否满足搜索二叉树(中序遍历是否为有序序列)

检测其是否满足红黑树的性质

根节点是否为黑色；

是否存在连续红节点；

统计每条路径上的黑节点数是否相等；


//红黑树的检测
 
//中序遍历检测是否满足搜索二叉树的性质
void _InOrder(Node* root)
{
	if (root == nullptr)
		return;
 
	_InOrder(root->_left);
	cout << root->_kv.first << endl;
	_InOrder(root->_right);
}
void InOrder()
{
	_InOrder(_root);
}
 
//blackNum记录每条路径黑色结点的数量,refBlackNum为最左路径的黑色结点数量作为基准值
bool Check(Node* cur, int blackNum, int refBlackNum)
{
	if (cur == nullptr)
	{
		if (refBlackNum != blackNum)
		{
			cout << "黑色节点的数量不相等" << endl;
			return false;
		}
 
		return true;
	}
    
    //检测红黑树性质二
	if (cur->_col == RED && cur->_parent->_col == RED)
	{
		cout << cur->_kv.first << "存在连续的红色节点" << endl;
		return false;
	}
 
	if (cur->_col == BLACK)
		++blackNum;
 
	return Check(cur->_left, blackNum, refBlackNum)
		&& Check(cur->_right, blackNum, refBlackNum);
}
 
 
bool IsRBTree()
{
	//检查根结点是否为黑色
	if (_root && _root->_col == RED)
		return false;
 
	//检查是否满足红黑树性质二
	//思路1:如果当前节点为红色，检测它的孩子是否为红色，但孩子可能为空，需要判断孩子是否为空;
    //思路2:如果当前节点为红色，我们去检测它的父亲是否为红色;
 
	//检查是否满足红黑树性质三
	//首先每个结点均需要求取从根到当前结点的黑色结点的数量(例如:根到根的黑色结点数量为1)
	//将最左路径/最右路径的黑色节点数量作为基准值,求取到下一条路径的空节点时与基准值比较;
	int refBlackNum = 0;//基准值
	Node* cur = _root;
	while (cur)
	{
		if (cur->_col == BLACK)
			refBlackNum++;
 
		cur = cur->_left;
	}
 
	return Check(_root, 0, refBlackNum);
}

欢迎大家批评指正，博主会持续输出优质内容，谢谢各位观众老爷观看，码字画图不易，希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~

相关阅读:
Mac下通过brew安装多个版本的go并实现切换
 物理层（2.1）
Git实战技巧-查看不同版本之间的差异和代码的改动
 SD6.23集训总结
 __builtin_return_address()函数的使用方法
 玩转数据可视化之R语言ggplot2：（十一）坐标轴和刻度线设置2
2022年深圳技能大赛-大数据技术应用职业技能竞赛介绍
 第十八章：Swing自述
 XXE漏洞原理、xxe-lab演示和防御
 vue导航栏滚动下拉条上拉隐藏，下拉显示切换样式变化(源码)
原文地址：https://blog.csdn.net/m0_58963318/article/details/137808900