红黑树原理详解

墨蓝 2022-03-29 10:55 256阅读 0赞

--------------------

[二叉查找树][Link 1]由于在频繁的动态更新过程中，可能会出现树的高度远大于 `log2n`的情况，所以就会导致各个操作效率下降，最坏的情况下就会退化为链表，变为O(n)．很明显，想要解决这个问题，**有效的一种办法就是使得树的高度不要差很多，也就是平衡它．**

最先发明的平衡二叉查找树是[AVL树][AVL]，（它严格符合平衡二叉查找树的定义，即`任何节点的左右子树高度相差不超过 1，是一种高度平衡的二叉查找树。`）但是在工程中，我们经常听到的通常是`红黑树`，而不是AVL树．那么`为什么工程中都喜欢用红黑树，而不是其他平衡二叉查找树呢？`

其实在这里，我们应该能有一些想法了．既然他严格按照规定执行，每次的插入，删除，都就会引发树的调整．调整的多了，自然会影响树的效率．那么红黑树又是怎样解决这个问题的呐？

#### 其实，**平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。** ####

### 所以红黑树就是这种设计思路(近似平衡)了． ###

# 红黑树的定义 #

红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树．  
顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样四个要求：

## 重要 ##

*  1.　根节点是黑色的；
 *  2.　每个叶子节点都是黑色的空节点，也就是说，**叶子节点不存储数据**；
 *  3.　任何相邻的节点都不能同时为红色，也就是说，**红色节点是被黑色节点隔开的；**
 *  4.　每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

这里的第二点要求“叶子节点都是黑色的空节点”，主要是为了简化红黑树的代码实现而设置的．现在，我们暂时不管这一点．

下面是两个红黑树的图例，你可以看下。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]

# 为什么红黑树是近似平衡的呐？ #

首先，我们知道二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n，所以**如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 log2n 就好了。**

### 首先，我们来看，如果我们将红色节点从红黑树中去掉，那单纯包含黑色节点的红黑树的高度是多少呢？ ###

红色节点删除之后，有些节点就没有父节点了，它们会直接拿这些节点的祖父节点（父节点的父节点）作为父节点。所以，之前的二叉树就变成了四叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]

这时我们可以将有些节点拿出来组成一个完全二叉树，而完全二叉树的高度是 `log2n` ,很明显，我们的四叉树根本不会高于 `log2n`

### 我们现在知道只包含黑色节点的“黑树”的高度，那我们现在把红色节点加回去，高度会变成多少呢？ ###

从上面我画的红黑树的例子和定义看，**在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开**．红黑树中包含最多黑色节点的路径不会超过 log2n，所以加入红色节点之后，最长路径不会超过 2log2n，也就是说，红黑树的高度近似 2log2n。

所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。

--------------------

OK，红黑树的原理我们已经知道了，那么我们现在就来了解一下它的实现思想

# 实现红黑树的基本思想 #

在极客时间中老师用了魔方的例子来讲解其思想，我觉得很恰当．这里直接拿来用

**不知道你有没有玩过魔方？其实魔方的复原解法是有固定算法的：遇到哪几面是什么样子，对应就怎么转几下。你只要跟着这个复原步骤，就肯定能将魔方复原。**

实际上，红黑树的平衡过程跟魔方复原非常神似，大致过程就是：**遇到什么样的节点排布，我们就对应怎么去调整**。只要按照这些固定的调整规则来操作，就能将一个非平衡的红黑树调整成平衡的。

其实想想AVL树，不就是这样吗？在想想计算机，不就是不断"重复"的去做一些事情的吗？

和AVL树一样，在进行节点的插入和删除时，就会破坏红黑树的一些`规则`．在红黑树中主要破坏的是以下两点：

*  1．任何相邻的节点都不能同时为红色，也就是说，**红色节点是被黑色节点隔开的；**
 *  2． 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

很显然，我们需要也仅仅需要处理的就是如何把被破坏了的这两点规则还原回去．在还原之前，我们需要了解两个很重要的操作：**左旋与右旋（围绕某个节点的右旋）**，  
如图，其中 a，b，r 表示子树，可以为空。

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

感觉有个动画的效果是最好的了，哈哈哈～～不过也可以自己在脑中想象了啦

### 插入 ###

**`红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上`**。所以，关于插入操作的平衡调整，有这样两种特殊情况，但是也都非常好处理。

*  1．如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
 *  2.　如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
 *  其他：都会违背红黑树的定义，于是我们就需要进行调整，调整的过程包含两种基础的操作：**左右旋转和改变颜色。**

**其他情况主要有三种，如果要实现，可以对应各个情况各个击破**，红黑树的平衡调整过程是一个迭代的过程。就想魔方一样！！！对应规则调整就行了．

### 删除 ###

删除操作的平衡调整分为两步，第一步是**针对删除节点初步调整**。初步调整只是保证整棵红黑树在一个节点删除之后，**仍然满足最后一条定义的要求**，也就是说，每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；第二步是**针对关注节点进行二次调整，让它满足红黑树的第三条定义，即不存在相邻的两个红色节点。**

#### 1. 针对删除节点初步调整 ####

红黑树的定义中“只包含红色节点和黑色节点”，经过初步调整之后，`为了保证满足红黑树定义的最后一条要求，有些节点会被标记成两种颜色`，“红 - 黑”或者“黑 - 黑”。**如果一个节点被标记为了“黑 - 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点**。

这里具体有：**三种情况**

#### 2. 针对关注节点进行二次调整 ####

经过初步调整之后，关注节点变成了“红 - 黑”或者“黑 - 黑”节点。针对这个关注节点，我们再分四种情况来进行二次调整。二次调整是为了让红黑树中不存在相邻的红色节点。

这里具体有：**四种情况**

### 提问： ###

1.  如何理解红黑树定义的＂任何相邻的节点都不能同时为红色＂？  
       如果一个结点是红色的，则它的两个孩子都是黑色的．也就是说只要用线连起来的都不能同时是红色
2.  如何理解红黑树定义的＂每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点； ＂？  
       nullptr ．
3.  为什么插入的节点偏偏是红色呢？

将插入的结点着色为红色，不会违背 “性质 4”。而少违背一条性质，就意味着我们需要处理的情况越少。

1.  为什么红黑树的定义中，要求叶子节点是黑色的空节点？或者说是到底那里方便了？

只要满足这一条要求，那在任何时刻，红黑树的平衡操作都可以归结为上面的那几种情况。而且是简洁的．

1.  给红黑树添加黑色的空的叶子节点，会不会比较浪费存储空间呢?

一张图给你，立马明白：

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

1.  为什么平衡的二叉树（满二叉树或完全二叉树）的高度大约是 log2n？？

**时间复杂度其实都跟树的高度成正比，也就是 O(height)**。既然这样，现在问题就转变成另外一个了，也就是，**如何求一棵包含 n 个节点的完全二叉树的高度？**

树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示。从图中可以看出，包含 n 个节点的完全二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 2^(K-1)。

不过，对于完全二叉树来说，最后一层的节点个数有点儿不遵守上面的规律了。它包含的节点个数在 1 个到 2^(L-1) 个之间（**我们假设最大层数是 L**）。如果我们把每一层的节点个数加起来就是总的节点个数 n。也就是说，如果节点的个数是 n，那么 n 满足这样一个关系：

n >= 1+2+4+8+...+2^(L-2)+1
    n <= 1+2+4+8+...+2^(L-2)+2^(L-1)

借助等比数列的求和公式，我们可以计算出，L 的范围是 \[log2(n+1), log2n +1\]。完全二叉树的层数小于等于 log2n +1，也就是说，完全二叉树的高度小于等于 log2n。

[Link 1]: https://blog.csdn.net/liushengxi_root/article/details/81231172
[AVL]: https://blog.csdn.net/liushengxi_root/article/details/81660375
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70]: /images/20220329/c466aa92b1e84434965257d59e4513b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 1]: /images/20220329/498c91065bed4f0f8af00c923e1ade0a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 2]: /images/20220329/8260edeb35cd4629b9a6dd01ffd01f06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdXNoZW5neGlfcm9vdA_size_16_color_FFFFFF_t_70 3]: /images/20220329/e8a884ffa7f44b4e83af052a2a5d1dc2.png