数据结构与算法之树（四）红黑树

以你之姓@ 2024-04-19 13:25 80阅读 0赞

**数据结构与算法之树**

[数据结构与算法之树（一）二叉树概念及遍历方式（图文并茂）][Link 1]

[数据结构与算法之树（二）二叉查找树][Link 2]

[数据结构与算法之树（三）AVL树][AVL]

[数据结构与算法之树（四）红黑树][Link 3]

# 数据结构与算法之树（四）红黑树 #

### 文章目录 ###

*  数据结构与算法之树（四）红黑树
 *   *  一、为什么需要红黑树？
     *  二、红黑树性质
     *  三、红黑树的插入操作
     *   *  3.1 情况分类
         *  3.2 调整操作
     *  四、总结

上一篇文章我们介绍了平衡二叉搜索树和讲解了AVL树还有旋转操作，本文将讲解红黑树，红黑树也是平衡二叉搜索树的一种，下面将进行详细介绍

## 一、为什么需要红黑树？ ##

我们上一篇文章讲解了AVL树，其是一种高度平衡的二叉树，那为什么有了AVL树还需要红黑树呢？

AVL树虽然提供了高效的搜索，但为了维持高度平衡，每次插入与删除都比较费事，如果需要频繁的插入数据的话，使用AVL树是一种不小的代价

而红黑树只是做了近似平衡，它的平衡条件并没有AVL树严格，红黑树能保证的是没有一条路径的高度会比其他路径长2倍，但它的插入与删除要比AVL树高效

所以红黑树的插入、删除与查找都比较稳定，在工程上更倾向于使用红黑树，如C++ STL中的set和map就是使用了红黑树做底部支撑

## 二、红黑树性质 ##

红黑树给每个节点增加一个颜色标记（黑或红），通过相应的规则对节点的颜色进行束缚，来达到一定的平衡状态。红黑树能保证没有一条路径会比其他路径长2倍，达到以一种近似平衡的状态

首先来看，作为一棵红黑树需要满足什么性质

> 1.每个节点非黑即红
> 
> 2.根节点为黑色
> 
> 3.每个叶节点（NIL）为黑色（红黑树中的NULL不为空，而是指向一个空节点，目的是为了实现方便）
> 
> 4.如果一个节点为红色，即它的两个子节点为黑色（不允许两个连续的红色节点）
> 
> 5.对于每个节点，从该节点都每个叶子节点的路径上，黑色节点的个数相同

如下图所示，就是一棵红黑树

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]

关于红黑树应该怎样去调整是有调整才能满足红黑树的性质是有固定的步骤的，下面讲解红黑树的插入操作

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

红黑树插入节点的默认颜色是红色，而且插入在叶子节点中，至于插入到哪个位置是根据二叉搜索树的规则，插入后如果打破红黑树的性质怎么调整是红黑树的规则

在讲解插入操作之前，我们先讲解一些概念（以上述红黑树为例）

我们把关注节点（2节点）的父亲（3节点）叫`父节点`，把父节点的兄弟节点（8节点）称为`叔节点`，把父节点的父节点（5节点）称为`祖父节点`

### 3.1 情况分类 ###

红黑树的调整主要是采用旋转操作和调整颜色，红黑树的插入的情况可分为5种

其中两种特殊情况是比较容易处理的，此外其他情况都会打破红黑树的性质，如下

> 1.如果插入节点的父节点是黑色的，那么不需要任何调整
> 
> 2.如果插入节点是根节点，那么将根节点修改为黑色即可

另外三种情况是一个迭代的调整过程，如下

> 1.关注节点的叔叔节点为红色
> 
> 2.关注节点的叔叔节点为黑色，关注节点位于内侧
> 
> 3.关注节点的叔叔节点为黑色，关注节点位于外侧

何为内侧与外侧？

如果父节点是祖父节点的左子节点，关注节点在父节点的左子节点，这种情况称为`LL`

如果父节点是祖父节点的左子节点，关注节点在父节点的右子节点，这种情况称为`LR`

如果父节点是祖父节点的右子节点，关注节点在父节点的右子节点，这种情况称为`RR`

如果父节点是祖父节点的右子节点，关注节点在父节点的左子节点，这种情况称为`RL`

其中LL和RR称为外侧，LR和RL称为内侧

假设C节点为关注节点，对应的各种情况如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 1]

### 3.2 调整操作 ###

上述我们说了下面三种情况是一个迭代的操作，这里将详细说明

> 1.关注节点的叔叔节点为红色
> 
> 2.关注节点的叔叔节点为黑色，关注节点位于内侧
> 
> 3.关注节点的叔叔节点为黑色，关注节点位于外侧

**case 1**

> 1.关注节点的叔叔节点为红色

这种情况的对应策略是：将父节点和叔节点变为黑色，祖父节点变为红色，关注节点跳转到祖父节点，继续进行迭代

如下图所示（下面为了方便，我不画空节点）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 2]

**case 2**

> 2.关注节点的叔叔节点为黑色，关注节点位于内侧

这种情况对应的策略是：将关注节点跳转到父节点，进行一次单旋操作（LR做左旋，RL做右旋），然后继续进入迭代

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 3]

**case 3**

> 3.关注节点的叔叔节点为黑色，关注节点位于外侧

这种情况对应的策略是：将父节点修改为黑色，祖父节点修改为红色，对祖父节点进行一次单旋（LL做右旋，RR做左旋）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 4]

相应的伪代码如下（来自算法导论）

while z.p.color == RED //迭代
    	if z.p == z.p.p.left
    		y = z.p.p.right
    		if y.color == RED
    			z.p.color = BLACK //case 1
    			y.color = BALCK	  //case 1
    			z.p.p.color = RED //case 1
    			z = z.p.p		 //case 1
    		else if z == z.p.right
    			z = z.p				//case 2
    			LEFT-ROTATE(T, z)	 //case 2
    		z.p.color = BLACK		 //case 3
    		z.p.p.color = RED		 //case 3
    		RIGHT-ROTATE(T, z.p.p)	 //case 3
    	else
    		/* 与上述程序原理相同，左右互换 */
    	T.root.color = BLACK

## 四、总结 ##

本文讲解了为什么需要红黑树，红黑树的性质，红黑树的调整策略，其中插入操作种有5种情况，2种特殊情况容易解决，3种情况比较复杂，需要进行不断地迭代处理，其实红黑树的调整过程像是固定的公式，并没有太多的技巧性

[Link 1]: https://blog.csdn.net/weixin_42462202/article/details/100864133
[Link 2]: https://blog.csdn.net/weixin_42462202/article/details/100902052
[AVL]: https://blog.csdn.net/weixin_42462202/article/details/100979244#312__71
[Link 3]: https://blog.csdn.net/weixin_42462202/article/details/100996219
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190918190204824.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190918192540848.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190918193803132.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190918194355655.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190918195619278.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQ2MjIwMg==,size_16,color_FFFFFF,t_70