C++红黑树_业界新闻

发布时间:2024-07-19 14:06

阅读量:2

🎉个人名片：

🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
————————————————

文章目录

1.红黑树的概念
2 红黑树的性质
3 红黑树节点的定义
4.红黑树的插入操作（分类详解）
5.红黑树与AVL树的比较

1.红黑树的概念

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

2 红黑树的性质

性质：

每个结点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

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

首先，要满足黑色节点数目相同，则当只有黑色节点的时候，路径最短，因为红色节点不能连续出现，所以当黑色节点与红色节点交替的时候，路径最长，并且为最短的两倍。

3 红黑树节点的定义

enum color                      //颜色 { 	RED, 	BLACK }; template<class K, class V> struct AVLNode { 	AVLNode<K, V>* _left; 	AVLNode<K, V>* _right; 	AVLNode<K, V>* _parent; 	pair<K, V> _kv; 	color _col;                 //记录节点颜色  	AVLNode(pair<K, V>& kv)       		:_left(nullptr) 		, _right(nullptr) 		, _parent(nullptr) 		, _kv(kv) 		, _col(RED)           //新节点的颜色默认为红色 	{} };

新插入节点的颜色为红色的原因？

原因：因为红黑树有一条规则，就是每条路径的黑色节点数目相等，插入前每条路径的黑色数目是相等的，但是如果插入的是黑色节点的话，那么该条路径的黑色节点的数目就多了一个，直接违反规则，所以插入新节点为红色节点；

4.红黑树的插入操作（分类详解）

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索的树规则插入新节点
检测新节点插入后，红黑树的性质是否造到破坏
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；
但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连在一起的红色节点，此时需要对红黑树分情况来讨论：

含义解析：
cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

情况一：cur为红色，p为红色，g为黑色，u存在并且为红色

根据上图进行分析：

解析：
这里p与cur都为红色，违反规则，我们不能直接将p的颜色改为黑色，如果直接改为黑色的话，则每条路径的黑色节点数目就变化了，违反规则。

我们应该将p与u变为红色，g变为黑色，如果g是子树，还需向上调整（比如上图中的下面一种情况），如果g是根节点，则需要变回黑色，因为规则里根节点必须为黑色；

代码实现

    //这里是一个while循环，只展示了循环体里面的代码 	//情况一：uncle存在并且为红色 	if (uncle && uncle->_col == RED) 	{ 		uncle->_col = BLACK; 		parent->_col = BLACK; 		grandfather->_col = RED; 		parent = grandfather;          //如果为子树，则继续向上调整 		cur = parent;  		if (_root == grandfather)      //如果g为根节点，则改回黑色 		{ 			grandfather->_col = BLACK; 		} 	}

情况二：u不存在或则u存在并且为黑色
下面的分类与AVL树的旋转的分类很类似；

分析一：u不存在/存在且黑色，并且p为g的左，c为p的左或则 p为g的右，c为p的右（p，g，c在一条线上）

当u不存在时：处理方法：单旋+变色

当u存在时：处理方法：也是单旋+变色

总结：

当u存在为黑色或则不存在时，都需要旋转+变色（这里的旋转与上章AVL旋转一样）
如果c为p的左，并且p为g的左，则右旋
如果c为p的右，并且p为g的右，则左旋
变色：都是p变成黑色，g变为红色

代码实现

//p为g左，c为p左 if (parent==grandfather->_left && cur==parent->_left) {  	rotateR(grandfather); 	parent->_col = BLACK; 	grandfather->_col = RED; } //p为g右，c为p右 else if (parent == grandfather->_right && cur == parent->_right) { 	rotateL(grandfather); 	parent->_col = BLACK; 	grandfather->_col = RED; }

分析三：u不存在或则存在为黑色，但是p为g的左，c为p的右边或则 p为g的右，c为p的左（p，g，c不在一条线上）

当u不存在时：处理方法：双旋+变色

当u存在时：处理方法：双旋+变色

总结：
当g，p，c不在一条街直线上时，需要双旋+变色处理
旋转方向的判定和AVL树的旋转一样；（上章讲过）

代码实现：

//一左一右 else if(parent == grandfather->_left && cur == parent->_right) { 	rotateL(parent); 	rotateR(grandfather); 	cur->_col = BLACK; 	parent->_col = BLACK; 	break; } else if (parent == grandfather->_right && cur == parent->_left) { 	rotateR(parent); 	rotateL(grandfather); 	cur->_col = BLACK; 	parent->_col = BLACK; 	break; }

插入总代码

bool insert(pair<K, V>& kv) { 	if (_root == nullptr) 	{ 		_root = new Node(kv); 		_root->_col = BLACK; 	} 	//找插入点 	Node* parent = nullptr; 	Node* cur = _root; 	while (cur) 	{ 		if (cur->_kv > kv) 		{ 			parent = cur; 			cur = cur->_left; 		} 		else if (cur->_kv < kv) 		{ 			parent = cur; 			cur = cur->_right; 		} 		else 		{ 			return false; 		} 	} 	//插入 	if (cur == parent->left) 	{ 		cur = new Node(kv); 		parent->_left = cur; 		cur->_parent = parent; 	} 	else if (cur == parent->right) 	{ 		cur = new Node(kv); 		parent->_right = cur; 		cur->_parent = parent; 	}  	//调节颜色/调节使其满足规则 	while (parent && parent->_col == RED) 	{ 		Node* grandfather = parent->_parent; 		if (parent = grandfather->_left) 		{ 			Node* uncle = grandfather->_right; 		} 		else 		{ 			Node* uncle = grandfather->_left; 		} 		//情况一：uncle存在并且为红色 		if (uncle && uncle->_col == RED) 		{ 			uncle->_col = BLACK; 			parent->_col = BLACK; 			grandfather->_col = RED; 			parent = grandfather;          //如果为子树，则继续向上调整 			cur = parent;  			if (_root == grandfather)      //如果g为根节点，则改回黑色 			{ 				grandfather->_col = BLACK; 			} 		} 		//uncle不存在或则存在为黑色 		else 		{ 			//p为g左，c为p左 			if (parent==grandfather->_left && cur==parent->_left) 			{  				rotateR(grandfather); 				parent->_col = BLACK; 				grandfather->_col = RED; 				break; 			} 			//p为g右，c为p右 			else if (parent == grandfather->_right && cur == parent->_right) 			{ 				rotateL(grandfather); 				parent->_col = BLACK; 				grandfather->_col = RED; 				break; 			} 			//一左一右 			else if(parent == grandfather->_left && cur == parent->_right) 			{ 				rotateL(parent); 				rotateR(grandfather); 				cur->_col = BLACK; 				parent->_col = BLACK; 				break; 			} 			else if (parent == grandfather->_right && cur == parent->_left) 			{ 				rotateR(parent); 				rotateL(grandfather); 				cur->_col = BLACK; 				parent->_col = BLACK; 				break; 			} 		} 	} } //左单旋 void rotateL(Node* parent) { 	Node* pparent = parent->_parent;     //记录所旋转根节点的父亲 	Node* pNodeR = parent->_right; 	Node* pNodeRL = pNodeR->_left; 	if (pNodeRL)                         //如果该旋转节点的右节点的左孩子存在 		parent->_right = pNodeRL; 	pNodeR->_left = parent;  	//新的父节点的链接 	if (parent == _root) 	{ 		_root = pNodeR; 		pparent = nullptr; 	} 	else 	{ 		if (pparent->_left == parent) 		{ 			pparent->_left = pNodeR; 		} 		else 		{ 			pparent->_right = pNodeR; 		} 	} } //右单旋 void rotateR(Node* parent) { 	Node* pparent = parent->_parent;  	Node* pNodeL = parent->_left; 	Node* pNodeLR = pNodeL->_right;  	if (pNodeLR) 		parent->_left = pNodeLR; 	pNodeL->_right = parent;  	if (parent == _root) 	{ 		_root = pNodeL; 		pparent = nullptr; 	} 	else 	{ 		if (pparent->_left == parent) 		{ 			pparent->_left = pNodeL; 		} 		else 		{ 			pparent->_right = pNodeL; 		} 	} }