可怕的红黑树

1.红黑树介绍

1.1概念

1.2.红黑树的性质

1.3.红黑树节点的定义

1.红黑树介绍

1.1概念

红黑树 ，是一种 二叉搜索树 ，但 在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或

Black 。通过对 任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路

径会比其他路径长出俩倍 ，因而是 接近平衡 的。

如图：

1.2.红黑树的性质


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

最短路径全都是黑色节点构成即长度为N.

最长路径则是由红色和黑色交替构成，在该路径中红色节点和黑树节点的个数相同，我们就可以得到最长路径的长度为2N，所以在黑树中最长路径不会超过最短路径的2倍，从而达到了近似平衡。

1.3.红黑树节点的定义


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

2.红黑树的旋转

旋转其实与AVL树的旋转是一样的，也是分为左右单旋，和左右.右左双旋。

2.1右单旋

代码：


void RotateL(Node* parent)
	{   
        Node* ppNode = parent->_parent;//先存储父亲结点的父亲结点
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
 
		parent->_right = subRL;
		subR->_left = parent;
        if(subRL)                      //subRL可能为空
			subRL->_parent = parent;
		parent->_parent = subR;
 
		if (parent == _root)           //如果parent是根节点
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else                            //如果parent不是根节点
		{
			if (parent == ppNode->_left)//如果parent在其父亲结点左侧
			{
				ppNode->_left = subR;
			}
			else                        //如果parent在其父亲结点右侧
			{
				ppNode->_right = subR;
			}
			subR->_parent = ppNode;
		}
	}

2.2左单旋

对应代码


void RotateR(Node* parent)
	{   
        Node* ppNode = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
        subL->_right = parent;
		parent->_left = subLR;
 
		if (subLR)
			subLR->_parent = parent;
		parent->_parent = subL;
 
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
 
	}

3.红黑树的插入

要插入一个节点我们是希望他是红色节点还是黑树节点？很显然是红色节点，如果插入的是黑色节点，这会破坏红黑树中任何一条路径中黑色节点的数量相同。对应这种情况我们对红黑树进行调整就变得很麻烦。因此我们希望插入的节点为红色节点。

先简单定义下概念：把要插入的结点定义为cur，父亲结点定义为p，父亲结点的父亲结点定义为g，其叔叔定义为u.

如图：

主要根据叔叔结点分情况讨论

3.1插入情况一

cur 为红， p 为红， g 为黑， u 存在且为红

将p,u结点变黑，如果g不是根结点，把其变红，然后再向上调整。

对应代码实现(假设cur为p的左孩子，p为g的左孩子）：


while (parent && parent->_col == RED)
{
	Node* grandfater = parent->_parent;
	assert(grandfater);
 
	if (grandfater->_left == parent)
	{
		Node* uncle = grandfater->_right;
		if (uncle && uncle->_col == RED) // 叔叔存在且为红
		{
 
			parent->_col = uncle->_col = BLACK;
			grandfater->_col = RED;
			cur = grandfater;
			parent = cur->_parent;
		}
	}
}

3.2插入情况2

cur 为红， p 为红， g 为黑， u 不存在 /u 存在且为黑

先看最简单的情况：u不存在

这种情况直接进行右旋就可以。可直接调用上面右旋的代码


 while (parent && parent->_col == RED)
{
		Node* grandfater = parent->_parent;
		assert(grandfater);
		if (grandfater->_left == parent)
		{
			Node* uncle = grandfater->_right;
			if (uncle && uncle->_col == RED) // 叔叔存在且为红
			{
				parent->_col = uncle->_col = BLACK;
				grandfater->_col = RED;
				cur = grandfater;
				parent = cur->_parent;
			}
			else // 叔叔不存在 或者 叔叔存在且为黑
			{
				if (cur == parent->_left) // 单旋
				{
					RotateR(grandfater);//进行左单旋
				    parent->_col = BLACK;
					grandfater->_col = RED;
				}
				break;
			}
        }
}

如果u存在且为黑呢？如图：

一样的是以g为旋转点进行右旋。

补充：

p为g的左孩子，cur为p的左孩子，则进行右单旋转；

p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红(g不是根节点的情况下）

3.3插入情况3

cur为红，p为红，g为黑，u不存在/u存在且为黑，但 1--：p为g的左孩子，cur为p的右孩子，2--：p为g的右孩子，cur为p的左孩子。

先看一种最简单的情况，u不存在，p为g的左孩子，cur为p的右孩子，如图：

对p进行左单旋，也就变成了情况二中的情况，再对g进行右单旋即可，然后再更改颜色。

如果u存在且为黑呢？

思路是一样的，代码实现：


 while (parent && parent->_col == RED)
{
		Node* grandfater = parent->_parent;
		assert(grandfater);
		if (grandfater->_left == parent)
		{
			Node* uncle = grandfater->_right;
			if (uncle && uncle->_col == RED) // 叔叔存在且为红
			{
				parent->_col = uncle->_col = BLACK;
				grandfater->_col = RED;
				cur = grandfater;
				parent = cur->_parent;
			}
			else // 叔叔不存在 或者 叔叔存在且为黑
			{
				if (cur == parent->_left) // 单旋，parent为grandfather的左，cur为parent的左
				{
					RotateR(grandfater);//进行左单旋
				    parent->_col = BLACK;
					grandfater->_col = RED;
				}
                else           // 双旋parent为grandfather的左，cur为parent的右
				{
					RotateL(parent);//对parent进行左单旋
					RotateR(grandfater);//对grandfather进行右单旋
				   cur->_col = BLACK;
					grandfater->_col = RED;
				}
				break;
			}
        }
}

以上情况p都为grandfather的左孩子进行演示的。

完整插入代码实现：


bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)//如果是空树，直接插入
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
 
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)          //按规则进行比较
		{
			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);
		cur->_col = RED;  
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
//*******************************************************************
//插入节点成功，下面对节点进行调整
		
		while (parent && parent->_col == RED)
		{
			Node* grandfater = parent->_parent;
			assert(grandfater);
 
			if (grandfater->_left == parent)    //p为g的左孩子
			{
				Node* uncle = grandfater->_right; //u为g的右孩子
				if (uncle && uncle->_col == RED) // 叔叔存在且为红。情况一
				{
				
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
					cur = grandfater;
					parent = cur->_parent;
				}
				else                           // 叔叔不存在 或者 叔叔存在且为黑
				{
					if (cur == parent->_left) // 单旋，p为g的左孩子，cur为p的左孩子
					{
						RotateR(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else                      // 双旋，p为g的左孩子，cur为p的右孩子
					{
						RotateL(parent);
						RotateR(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
 
					break;
				}
			}
			else //(grandfater->_right == parent)，p为g的右孩子
			{
				Node* uncle = grandfater->_left;// u为g的左孩子
				if (uncle && uncle->_col == RED)
				{
				
					parent->_col = uncle->_col = BLACK;
					grandfater->_col = RED;
					cur = grandfater;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
		
						RotateL(grandfater);
						parent->_col = BLACK;
						grandfater->_col = RED;
					}
					else 
					{
						RotateR(parent);
						RotateL(grandfater);
						cur->_col = BLACK;
						grandfater->_col = RED;
					}
 
					break;
				}
			}
		}
 
		_root->_col = BLACK;//把根节点变为黑色
 
		return true;
	}

3.4情况总结

红黑树插入后，如何进行调整主要看u（叔叔）节点，以及cur与p节点的关系

1--u存在且为红：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

2--cur为红，p为红，g为黑，u不存在/u存在且为黑：p为g的左孩子，cur为p的左孩子，则进行右单旋转；p为g的右孩子，cur为p的右孩子，则进行左单旋转 .p、g变色--p变黑，g变红

3--cur为红，p为红，g为黑，u不存在/u存在且为黑：p为g的左孩子，cur为p的右孩子，则进行左单旋转；p为g的右孩子，cur为p的左孩子，则进行右单旋转 .这样变为了情况2.

4.红黑树的验证

如何验证上面的代码生成的是一颗红黑树呢？

红黑树的检测分为两步：

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

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

第二步如何检测呢？

1：不存在连续的红节点 2.每条路径上的黑色节点数目是相同的。3.根节点为黑色

例如：

这颗红黑树一共有13条路径，需要检测每条路径是否存在连续的红节点，以及每条路径上黑节点的个数是否相同。可以先算出最右边路径上黑节点的数目，然后从根节点递归检测

中序遍历代码：


void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
 
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}

检测每一条路径：


bool IsBalanceTree()
	{
 
		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->_right;
		}
 
		// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
		size_t k = 0;
		return _IsValidRBTree(pRoot, k, blackCount);
	}
 
 
bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
	{
		
		if (nullptr == pRoot)//走到null之后，判断k和black是否相等
		{
			if (k != blackCount)
			{
				cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;
				return false;
			}
			return true;
		}
 
		// 统计黑色节点的个数
		if (BLACK == pRoot->_col)
			k++;
 
		// 检测当前节点与其双亲是否都为红色
		if (RED == pRoot->_col && pRoot->_parent && pRoot->_parent->_col == RED)
		{
			cout << "违反性质三：存在连在一起的红色节点" << endl;
			return false;
		}
 
		return _IsValidRBTree(pRoot->_left, k, blackCount) &&
			_IsValidRBTree(pRoot->_right, k, blackCount);
	}

5.红黑树与AVL树的比较

AVL树是通过控制左右高度差不超过1来实现二叉树平衡的，实现的是二叉树的严格平衡。
红黑树是通过控制结点的颜色，从而使得红黑树当中最长可能路径不超过最短可能路径的2倍，实现的是近似平衡。
红黑树和 AVL 树都是高效的平衡二叉树，增删改查的时间复杂度都是 O($log_2 N$) ，红黑树不追 求绝对平衡，其只需保证最长路径不超过最短路径的 2 倍，相对而言，降低了插入和旋转的次数， 所以在经常进行增删的结构中性能比 AVL 树更优，而且红黑树实现比较简单，所以实际运用中红 黑树更多。

相关阅读:
肥泽-酒店辅助订购系统
 linux 文件系统命令
 使用单调栈解决 “下一个更大元素” 问题
 零食食品经营小程序商城的作用是什么
 js逆向播放量增加，增加视频热度，uuid，sid，buvid3，aid，b_lsid, b_nut 还原实现过程
 华为OD机试真题 Java 实现【数组二叉树】【2023 B卷 200分】，附详细解题思路
 mathtype符号显示不全的问题
 C++基础入门指针
 宁德时代打响增长保卫战
 阶段性检测实战项目----文件搜索引擎
原文地址：https://blog.csdn.net/m0_64397669/article/details/126452393