【C++杂货铺】一文带你走进RBTree

Love The Way You Lie 2024-02-27 03:16 49阅读 0赞

![在这里插入图片描述][81826b817d124014966f2b39acdfea0d.gif_pic_center]

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

*  一、红黑树的概念
 *  二、红黑树的性质
 *  三、红黑树结点的定义
 *  四、红黑树的插入操作
 *   *  4.1 情况一：uncle 存在且为红
     *  4.2 情况二：uncle 不存在
     *  4.3 情况三：uncle 存在且为黑
     *  4.4 插入完整源码
 *  五、红黑树的验证
 *  六、红黑树与 AVL 树的比较
 *  七、结语

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

红黑树是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，这句话换个意思就是：红黑树中最长路径不超过最短路径的 2 倍。因而是接近平衡的，而 AVL 树是严格平衡的，这就导致，红黑树的高度会比 AVL 树高一些，但是效率并不会比 AVL 树差。  
![在这里插入图片描述][c1b669c153a34dfe8e7c186a2aa268ac.png_pic_center]

## 二、红黑树的性质 ##

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

**小Tips**：第三点决定了一颗红黑树的任何路径没有连续的红色结点。在红黑树中计算路径一定是计算到 `NIL` 结点。一颗红黑树中的最短路径是全为黑结点的路径，最长路径是一黑一红相间的路径。任意一条路径上黑色结点的占比一定是大于等于  1 / 2 1/2 1/2 的。这就决定了，红黑树中其最长路径中结点个数不会超过最短路径结点个数的两倍。

## 三、红黑树结点的定义 ##

//红黑树的结点
    template<class K, class V>
    struct RBTreeNode
    {
        
    	RBTreeNode(const& pair<K, V> kv = pair<K, V>(), Color color = RED)
    		:_kv(kv)
    		,_left(nullptr)
    		,_right(nullptr)
    		,_parent(nullptr)
    		,_col(color)
    	{
        }
    
    	pair<K, V> _kv;//结点中存的值
    	RBTreeNode<K, V>* _left;//结点的左孩子
    	RBTreeNode<K, V>* _right;//结点的右孩子
    	RBTreeNode<K, V>* _parent;//结点的父亲
    	Color _col;//结点的颜色
    };

**小Tips**：新节点默认颜色是 `RED`。这是因为，如果新插入结点的颜色是 `BLACK`，那意味着当前路径上新增了一个黑色结点，为了保证二叉树的第四条性质，我们要对这颗红黑树其他的所有路径进行检查，可见新插入结点如果默认是 `BLACK`，会存在着牵一发而动全身的影响。而让新插入结点默认是 `RED` 则不会出现这样的结果。假如新插入结点的 `parent` 恰好是 `BLACK`，那这次插入就没有什么问题。如果新插入结点是 `parent` 是 `RED`，此时需要对这颗红黑树稍作调整。

## 四、红黑树的插入操作 ##

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

*  按照二叉搜索树的规则插入结点。
 *  检测新节点插入后，红黑树的性质是否遭到破坏。

因为新结点的默认颜色是 `RED`，因此：如果其双亲结点的颜色是 `BLACK`，没有违反红黑树任何性质，则不需要调整；但是当新插入节点的双亲结点颜色为 `RED` 时，就违反了性质三不能有连在一起的红色结点，此时需要对红黑树分情况来讨论：

**约定**：`cur`为当前结点，`parent` 为父结点，`grandp` 为祖父结点，`uncle` 为叔叔结点。如果 `parent` 为红那 `grandp` 一定为黑。所以当前唯一不确定的就是 `uncle`，主要分以下三种情况

### 4.1 情况一：uncle 存在且为红 ###

![在这里插入图片描述][7912b2f2a15541ea9cfd994daac099cb.png_pic_center]  
**小Tips**：此处看到的树，可能是一颗完整的树，也可能是一颗子树。

**解决方式**：将 `parent` 和 `uncle` 改为黑，`grandp` 改成红。然后把 `grandp` 当成 `cur`，继续向上调整。

*  如果 `grandp` 是根结点，将 `grandp` 再改成黑色，本次插入就算结束。
 *  如果 `grandp` 是子树，则其一定也有双亲，且 `grandp` 的双亲如果是红色，需要继续向上调整。

![在这里插入图片描述][0c01ff7060ff41ad9706c3a9de0e23bc.png_pic_center]

### 4.2 情况二：uncle 不存在 ###

如果 `uncle` 结点不存在，则 `cur` 一定是新插入结点，因为如果 `cur` 不是新插入结点，则 `cur` 和 `parent` 一定有一个结点的颜色是黑色，就不满足性质四：每条路径黑色结点个数相同。  
![在这里插入图片描述][1835a57ba57a4fd6a31021853574c44c.png_pic_center]  
**解决方法**：直接进行旋转即可。

### 4.3 情况三：uncle 存在且为黑 ###

![在这里插入图片描述][57ce4cb1990b48e19f070c87d144e2ae.png_pic_center]  
叔叔存在且为黑，那么 `cur` 一定不是新插入的结点，并且 `cur` 结点原来的颜色一定是黑色，现在看到是红色的原因是因为 `cur` 的子树在调整的过程中将 `cur` 结点的颜色由黑色改成了红色。

### 4.4 插入完整源码 ###

public:
    	bool Insert(const pair<K, V>& kv)
    	{
        
    		if (_root == nullptr)
    		{
        
    			_root = new Node(kv);
    			_root->_col = BLACK;
    			return true;//插入成功
    		}
    
    		//找插入位置
    		Node* cur = _root;
    		Node* parent = nullptr;
    
    		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);
    		cur->_col = RED;
    		if (kv.first < parent->_kv.first)
    		{
        
    			parent->_left = cur;
    		}
    		else
    		{
        
    			parent->_right = cur;
    		}
    
    		cur->_parent = parent;
    
    		//检测新结点插入后，红黑树的性质是否遭到破坏
    		while (parent && parent->_col == RED)
    		{
        
    			Node* grandp = parent->_parent;
    			if (parent == grandp->_left)
    			{
        
    				Node* uncle = grandp->_right;
    				if (uncle && uncle->_col == RED)//叔叔存在且为红
    				{
        
    					parent->_col = BLACK;
    					uncle->_col = BLACK;
    					grandp->_col = RED;
    
    					//继续向上处理
    					cur = grandp;
    					parent = cur->_parent;
    				}
    				else //uncle不存在或者存在为黑
    				{
        
    					if (cur == parent->_left)
    					{
        
    						RotateR(grandp);
    						parent->_col = BLACK;//parent当了根
    						grandp->_col = RED;
    					}
    					else if (cur == parent->_right)
    					{
        
    						RotateLR(grandp);
    						cur->_col = BLACK;//cur当了根节点
    						grandp->_col = RED;
    					}
    
    					break;
    				}
    			}
    			else if (parent == grandp->_right)
    			{
        
    				Node* uncle = grandp->_left;
    				if (uncle && uncle->_col == RED)//叔叔存在且为红
    				{
        
    					parent->_col = BLACK;
    					uncle->_col = BLACK;
    					grandp->_col = RED;
    
    					//继续向上处理
    					cur = grandp;
    					parent = cur->_parent;
    				}
    				else //uncle不存在或者存在为黑
    				{
        
    					if (cur == parent->_right)
    					{
        
    						RotateL(grandp);
    						parent->_col = BLACK;//parent当了根
    						grandp->_col = RED;
    					}
    					else if (cur == parent->_left)
    					{
        
    						RotateRL(grandp);
    						cur->_col = BLACK;//cur当了根节点
    						grandp->_col = RED;
    					}
    
    					break;
    				}
    			}
    		}
    
    		_root->_col = BLACK;//根结点始终变黑
    		return true;
    	}
    private:
    	//左单旋
    	void RotateL(Node* parent)
    	{
        
    		++_rotatecount;
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    
    		parent->_right = curleft;
    		cur->_left = parent;
    
    		if (curleft)
    		{
        
    			curleft->_parent = 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;//此时的情况是curright比cur大，比parent小
    
    		parent->_left = curright;
    		cur->_right = parent;
    
    		if (curright)
    		{
        
    			curright->_parent = parent;
    		}
    
    		Node* ppnode = parent->_parent;
    		parent->_parent = cur;
    
    		if (ppnode)
    		{
        
    			cur->_parent = ppnode;
    			if (ppnode->_left == parent)
    			{
        
    				ppnode->_left = cur;
    			}
    			else
    			{
        
    				ppnode->_right = cur;
    			}
    		}
    		else
    		{
        
    			_root = cur;
    			cur->_parent = nullptr;
    		}
    	}
    
    	//右左双旋
    	void RotateRL(Node* parent)
    	{
        
    		Node* cur = parent->_right;
    		Node* curleft = cur->_left;
    
    		RotateR(parent->_right);
    		RotateL(parent);
    
    	}
    
    	//左右双旋
    	void RotateLR(Node* parent)
    	{
        
    		Node* cur = parent->_left;
    		Node* curright = cur->_right;
    
    		RotateL(cur);
    		RotateR(parent);
    
    	}

## 五、红黑树的验证 ##

红黑树的检测分为两步：

*  检测其是否满足二叉搜索树（中序遍历是否为有序序列）。
 *  检测其是否满足红黑树的性质（主要是性质三和性质四）。

public:
    	bool Isblance()
    	{
        
    		if (_root == nullptr)
    			return true;
    
    		//根节点如果不是黑色说明就不是红黑树
    		if (_root->_col != BLACK)
    		{
        
    			return false;
    		}
    
    		//计算红黑树中任意一条路径上黑色结点的个数作为一个基准值
    		Node* cur = _root;
    		int count = 0;
    		while (cur)
    		{
        
    			if (cur->_col == BLACK)
    			{
        
    				++count;
    			}
    			cur = cur->_left;
    		}
    
    		return CheckColour(_root, 0, count);
    	}
    private:
    	//检查颜色
    	bool CheckColour(Node* root, int blacknum, int stand)
    	{
        
    		if (root == nullptr)
    		{
        
    			//到这里说明一条路径结束，那么这条路径上的黑色结点数也一定统计出来了
    			if (blacknum != stand)
    			{
        
    				cout << "当前路径上黑色结点的个数有问题" << endl;
    				return false;
    			}
    
    			return true;
    		}
    
    		//检查是否出现连续的红色结点
    		if (root->_col == RED && root->_parent && root->_parent->_col == RED)
    		{
        
    			cout << root->_kv.first << ":为红色节点，并且孩子结点也是红色" << endl;
    		}
    
    		//统计一条路径上黑色结点个数
    		if (root->_col == BLACK)
    		{
        
    			++blacknum;
    		}
    
    		return CheckColour(root->_left, blacknum, stand) && CheckColour(root->_right, blacknum, stand);
    	}

## 六、红黑树与 AVL 树的比较 ##

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

*  C++ STL 库----map、set、mutilmap、mutilset。
 *  Java 库。
 *  Linux 内核。
 *  其它一些库。

## 七、结语 ##

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，[春人的主页][Link 1]还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！

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

[81826b817d124014966f2b39acdfea0d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/e455098dee7b431593bef16454c41a5d.png
[c1b669c153a34dfe8e7c186a2aa268ac.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/d24401b0a3044a899c02843ec0cb793f.png
[7912b2f2a15541ea9cfd994daac099cb.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/766a33648f5f4d0bba852b5b1ae3ccba.png
[0c01ff7060ff41ad9706c3a9de0e23bc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/a15d7794a356433cb21c1f936b4ade21.png
[1835a57ba57a4fd6a31021853574c44c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/9d73c28a57c343b3aee8ef0c2565c1a1.png
[57ce4cb1990b48e19f070c87d144e2ae.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/7f75f5f22ec24bd5b2d6a395940abdf5.png
[Link 1]: https://blog.csdn.net/weixin_63115236?spm=1000.2115.3001.5343
[edc78985d03043828f98dcd5a8d2983e.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/27/36e160611cb14f3381723ea02e709287.png