【C++】红黑树

以你之姓@ 2024-04-26 11:03 7阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> 🚀write in front🚀  
> 📜所属专栏： [C++学习][C]  
> 🛰️博客主页：[睿睿的博客主页][Link 1]  
> 🛰️代码仓库：🎉[VS2022\_C语言仓库][VS2022_C]  
> 🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  前言
 *  一.红黑树的概念
 *  二.红黑树的性质：
 *  二.红黑树结点的定义：
 *  三.结点的插入：
 *   *  1.按照二叉搜索的树规则插入新节点
     *  2.检测新节点插入后，红黑树的性质是否造到破坏
     *   *  情况1：parent为黑色
         *  情况2：parent为红色，uncle为红色：
         *  情况3：parent为红色，uncle为黑色或者不存在：
         *   *  p为g的左孩子，cur为p的左孩子，则进行右单旋转
             *  p为g的右孩子，cur为p的右孩子，则进行左单旋转
             *  p为g的左孩子，cur为p的右孩子，则针对p做左右旋转:
             *  p为g的右孩子，cur为p的左孩子，则针对p做右左旋转
 *  四.红黑树的验证：
 *  五.红黑树的删除:
 *  五.红黑树和AVL树的比较：
 *  总结

## 前言 ##

在前面的学习中我们学习了AVL树的相关知识，并且手动模拟了一下他的插入函数。今天我们来讲一个能解决二叉搜索树高度问题的另一种树：红黑树

## 一.红黑树的概念 ##

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

![在这里插入图片描述][33b52436063744d79217b11ce4ede045.png]

## 二.红黑树的性质： ##

红黑树满足以下性质：

*  非黑即红
 *  任何路径没有连续的红结点
 *  每条路径的黑色结点数量相同（路径是指从根到树叶的路径，从上到下）
 *  根是黑色的

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

其实通过两条性质就可以说明，每条路径的黑色结点数量相同，所以红结点会穿插在黑节点之间，并且路径没有连续的红结点，所以不会超过最短路径的两倍啦  
![在这里插入图片描述][5baaf8f5f8ee41b9b97580f88cc3554e.png]

## 二.红黑树结点的定义： ##

enum Colour
    {
        
    	RED,
    	BLACK
    };
    
    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)
    		:_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_kv(kv)
    		,_col(RED)
    	{
        }
    };

在这里和二叉搜索树相比，就多了一个结点的颜色。为什么结点的颜色要默认为红色呢？  
  在前面的性质里面，每个路径的黑色结点数量相同，如果我们插入结点的颜色是黑色，就会打乱这个性质，并且很难调整（一定要调整），而如果我们插入的是红色，只可能有时候会违背红色结点不连续这一个性质（在黑节点下插入就不用调整），相比之下要比打乱黑色结点数量要好调整的多。

> Tips：  
> 如果插入节点默认为黑色，那么**这颗树整体就被影响**了，该路径上的黑色节点与其他路径黑色节点数量不同  
> 如果插入节点默认为红色，那么就算要影响，也是**只影响该路径**，其他路径不受影响

## 三.结点的插入： ##

红黑树里面结点的插入可以分为两个部分：

### 1.按照二叉搜索的树规则插入新节点 ###

这里就和搜索二叉树一样，就不用多说了：

template<class K, class V>
    struct RBTree
    {
        
    	typedef RBTreeNode<K, V> Node;
    public:
    	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;

### 2.检测新节点插入后，红黑树的性质是否造到破坏 ###

在这里，我们要设当前结点为`cur`，父节点为`parent`，父亲的兄弟为`uncle`，父亲和父亲兄弟的父亲为`grandfather`。

#### 情况1：parent为黑色 ####

. parent为黑色，说明没有影响红黑树的结构，插入就成功了。

#### 情况2：parent为红色，uncle为红色： ####

先举一个例子：  
![在这里插入图片描述][33ee7ff5f1534413bf2357d05baeb01a.png]  
  对于`uncle`为红的情况，让`parent`和`uncle`变黑，`grandfather`边红。这样不仅保持了插入的红结点处不连续了，还保持了每条路径的黑色结点数量相同了。此时我们会发现，`grandfather`和他的父亲结点又变成了连续的红色结点，此时我们就继续此过程就ok了

具体过程如下：

![在这里插入图片描述][1409b9591c0a441b94bddb2a666d4c1f.png]  
变色完成后这里还会有三种情况：

1.  `grandfather`为根节点，没有父亲，那就直接把他变黑即可
2.  `grandfather`有父亲，且父亲为黑色，此时调整就已经成功了
3.  `grandfather`有父亲，且父亲为红色，就相当于下面插入了一个子树，但是此时红色结点有连续了。这个时候就让`cur=parent`，继续判断uncle的情况，然后根据不同情况操作。

总结一下，这里的操作就是：

> 解决方式：将parent,uncle改为黑，grandfather改为红，然后把g当成cur，继续向上调整。

#### 情况3：parent为红色，uncle为黑色或者不存在： ####

ncle情况分为2种：

**uncle不存在**:  
![在这里插入图片描述][ac7ba78e3aec4ed38e99eff41140cc16.png]

**uncle存在且为黑：**  
![在这里插入图片描述][11d4286b89f54289a7617e73efa984d8.png]

其实，在这里就是根据`grandfather`，`parent`，`cur`的位置关系来判断是左旋，右旋还是左右双旋，右左双旋。

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

这里的旋转和AVL树类似，就是最后要调整一下颜色：  
让`parent`变黑，`grandfather`变红。本质上也是在旋转之后调整黑色结点的数量。

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

这里和右单旋转类似

##### p为g的左孩子，cur为p的右孩子，则针对p做左右旋转: #####

![在这里插入图片描述][27954e71d6c6414588a16ca29f243cb5.png]  
通过画图我们可以知道，最后让`cur`变黑，`grandfather`变红就可以了。

##### p为g的右孩子，cur为p的左孩子，则针对p做右左旋转 #####

这里和左右双旋类似，最后就是让`cur`变黑，`grandfather`变红就可以了。

最后要注意的是，如果经过旋转，就不用在往上调整了，只要是旋转过了，就已经平衡了。这里和AVL树类似

代码实现：

bool Insert(const pair<K, V>& kv)
    	{
        
    		Node* cur = _root;
    		Node* parent = nullptr;
    
    		if (cur == nullptr)
    		{
        
    			_root = new Node(kv);
    			_root->_col = BLACK;
    			return true;
    		}
    
    		//找到位置：
    		while (cur)
    		{
        
    			if (cur->_kv.first > kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_left;
    			}
    			else if (cur->_kv.first < kv.first)
    			{
        
    				parent = cur;
    				cur = cur->_right;
    			}
    			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;
    
    
    		//修改颜色：
    		//如果为黑色就已经正确了，当然前提是parent不为空
    		while (parent && parent->_col == RED)
    		{
        
    			Node* grandfather = parent->_parent;
    			//四种情况，我们分两种讨论：主要是为了找到uncle！！
    			if (grandfather->_left == parent) 
    			{
        
    				Node* uncle = grandfather->_right;
    
    				//uncle为红的时候：
    				if (uncle && uncle->_col == RED)
    				{
        
    					//变色
    					uncle->_col = parent->_col = BLACK;
    					grandfather->_col = RED;
    					//向上处理
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				//uncle不存在或uncle为黑
    				else
    				{
        
    					if (parent->_left == cur)
    					{
        
    						//右旋
    							 //g
    						   //p
    						 //c
    
    						   //p
    						//c    g
    						RotateR(grandfather);
    						//调颜色：
    						parent->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					else
    					{
        
    						//左右旋
    						//    g
    						//   p
    						//		c
    
    						  //    g
    						  //  c
    						  //p
    
    							// c
    						  //p     g
    						RotateL(parent);
    						RotateR(grandfather);
    
    						cur->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					break;
    				}
    			}
    			else  //为什么要分左右？  找到uncle！！
    			{
        
    				Node* uncle = grandfather->_left;
    
    				//uncle为红的时候：
    				if (uncle && uncle->_col == RED)
    				{
        
    					//变色
    					uncle->_col = parent->_col = BLACK;
    					grandfather->_col = RED;
    					//向上处理
    					cur = grandfather;
    					parent = cur->_parent;
    				}
    				//uncle不存在或uncle为黑
    				else
    				{
        
    					if (parent->_right == cur)
    					{
        
    						//左旋
    						 //g
    						 //	  p
    						 //      c
    
    						RotateL(grandfather);
    						//调颜色：
    						parent->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					else
    					{
        
    						//右左旋：
    						 //g
    							//  p
    						 //c
    						RotateR(parent);
    						RotateL(grandfather);
    
    						cur->_col = BLACK;
    						grandfather->_col = RED;
    					}
    					break;
    				}
    			}
    
    		}
    		_root->_col = BLACK;
    
    		return true;
    
    
    	}
    
    	void RotateL(Node* parent)
    	{
        
    		//++_rotateCount;
    
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    
    		parent->_right = curleft;
    		if (curleft)
    		{
        
    			curleft->_parent = parent;
    		}
    
    		cur->_left = parent;
    
    		Node* ppnode = parent->_parent;
    
    		parent->_parent = cur;
    
    
    		if (parent == _root)
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
        
    			if (ppnode->_left == parent)
    			{
        
    				ppnode->_left = cur;
    			}
    			else
    			{
        
    				ppnode->_right = cur;
    
    			}
    
    			cur->_parent = ppnode;
    		}
    	}
    
    
    
    	void RotateR(Node* parent)
    	{
        
    		//++_rotateCount;
    
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    
    		parent->_left = curright;
    		if (curright)
    			curright->_parent = parent;
    
    		Node* ppnode = parent->_parent;
    		cur->_right = parent;
    		parent->_parent = cur;
    
    		if (ppnode == nullptr)
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    		else
    		{
        
    			if (ppnode->_left == parent)
    			{
        
    				ppnode->_left = cur;
    			}
    			else
    			{
        
    				ppnode->_right = cur;
    			}
    
    			cur->_parent = ppnode;
    		}
    	}

## 四.红黑树的验证： ##

那么，红黑树如何验证呢？

1.  检测其是否满足二叉搜索树(中序遍历是否为有序序列)
2.  检测其是否满足红黑树的性质

bool CheckColour(Node* root,int count,int benchmark)
    	{
        
    	//遍历每一条路径，观察黑色结点数是否相等
    		//这里检查黑结点数是否相等
    		if (root == nullptr)
    		{
        
    			if (count == benchmark)
    			{
        
    				return true;
    			}
    			return false;
    		}
    
    		if (root->_col == BLACK)
    		{
        
    			count++;
    		}
    		//在遍历的时候，检查是否有红色结点连续的时候
    		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    		{
        
    			cout << root->_kv.first << "出现连续红色节点" << endl;
    			return false;
    		}
    		return CheckColour(root->_left, count, benchmark) && CheckColour(root->_right, count, benchmark);
    	}
    
    	bool _IsBalance(Node* root)
    	{
        
    		if (root == nullptr)
    		{
        
    			return true;
    		}
    		
    		//根节点是否为黑色
    		if (root->_col != BLACK)
    		{
        
    			return false;
    		}
    		
    		//统计随便一条路径的黑色结点的个数（性质说明每条路径黑色结点数量相同）
    		int benchmark = 0;
    		Node* cur = _root;
    		while (cur)
    		{
        
    			if (cur->_col == BLACK)
    			{
        
    				benchmark++;
    			}
    			cur = cur->_left;
    		}
    
    		return CheckColour(root, 0, benchmark);
    	}
    	bool IsBalance()
    	{
        
    		return _IsBalance(_root);
    	}

## 五.红黑树的删除: ##

红黑树的删除很复杂，等有时间我再来学习一下！！！！  
[详细][Link 2]

## 五.红黑树和AVL树的比较： ##

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O( l o g 2 N log\_2 N log2N)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，**降低了插入和旋转的次数**，所以在**经常进行增删**的结构中性能比AVL树更优，而且**红黑树实现比较简单**，所以实际运用中**红黑树更多**。

## 总结 ##

总的来说，红黑树所用之处还是非常多的，都是大佬们智慧的结晶，真的很牛逼！！不过大家下来一定要多加复习！！才能做到真正意义上的手撕红黑树。

更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 3]  
> [C语言学习][C 1]  
> [算法][Link 4]  
> [智力题][Link 5]  
> [初阶数据结构][Link 6]  
> [Linux学习][Linux]  
> [C++学习][C]  
> 更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/919bd6c94788455290b89b3cba4e5944.gif
[C]: https://blog.csdn.net/qq_74310471/category_12289978.html
[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5c4aa2c7ca654059a5a6c204f9c9d908.gif
[33b52436063744d79217b11ce4ede045.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/59bc4996b0354045932fc1fa834a603f.png
[5baaf8f5f8ee41b9b97580f88cc3554e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/06e30e46f5fe4f5da6e916c2494781e8.png
[33ee7ff5f1534413bf2357d05baeb01a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/1351f98119f34a89b70a0e08b6589fd6.png
[1409b9591c0a441b94bddb2a666d4c1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/7603833fb2744d6d86a9bc7990dbed0a.png
[ac7ba78e3aec4ed38e99eff41140cc16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/7526a8a36d1c4c958ebda3a70057ece4.png
[11d4286b89f54289a7617e73efa984d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f473d296d6d941a0924948f422e8ba2b.png
[27954e71d6c6414588a16ca29f243cb5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/635d6976376948b1a05ce0df5353f6db.png
[Link 2]: http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html
[Link 3]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[C 1]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 5]: https://blog.csdn.net/qq_74310471/category_12166402.html
[Link 6]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Linux]: https://blog.csdn.net/qq_74310471/category_12291120.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/7ceecc8a73fa48b980b11c0652dcf8f6.gif