红黑树(一) 原理和算法介绍

墨蓝 2021-10-12 23:44 173阅读 0赞

阅读：[https://blog.csdn.net/qq\_39344902/article/details/81605850?tdsourcetag=s\_pctim\_aiomsg][https_blog.csdn.net_qq_39344902_article_details_81605850_tdsourcetag_s_pctim_aiomsg]

## 一、简介 ##

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构。

红黑树的特性:

（1）每个节点或者是黑色，或者是红色。  
（2）根节点是黑色。  
（3）每个为空的叶子节点（NIL或NULL）是黑色。  
（4）如果一个节点是红色的，则它的子节点必须是黑色的。  
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

**注：**

特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

红黑树示意图如下：

![1269700-20180530204257973-2034786443.png][]

## 二、红黑树的应用 ##

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。

例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。

## 三、红黑树的时间复杂度和相关证明 ##

红黑树的时间复杂度为: O(lgn)

定理：一棵含有n个节点的红黑树的高度至多为2log(n+1)

下面通过“数学归纳法”对红黑树的时间复杂度进行证明。

证明：

"一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的逆否命题是 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。

我们只需要证明逆否命题，即可证明原命题为真；即只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2h/2-1个"。

从某个节点x出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x's black height)，记为bh(x)。关于bh(x)有两点需要说明：

第1点：根据红黑树的"特性(5) ，即从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点"可知，从节点x出发到达的所有的叶节点具有相同数目的黑节点。这也就意味着，bh(x)的值是唯一的！

第2点：根据红黑色的"特性(4)，即如果一个节点是红色的，则它的子节点必须是黑色的"可知，从节点x出发达到叶节点"所经历的黑节点数目">= "所经历的红节点的数目"。假设x是根节点，则可以得出结论"bh(x) >= h/2"。进而，我们只需证明 "高度为h的红黑树，它的包含的黑节点个数至少为 2bh(x)-1个"即可。

到这里，我们将需要证明的定理已经由

"一棵含有n个节点的红黑树的高度至多为2log(n+1)"

转变成只需要证明

"高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。

下面通过"数学归纳法"开始论证高度为h的红黑树，它的包含的内节点个数至少为 2bh(x)-1个"。

(1) 当树的高度h=0时，节点个数是0，bh(x) 为0，2bh(x)-1 也为 0。显然，原命题成立。

2) 当h>0，且树的高度为 h-1 时，它包含的节点个数至少为 2bh(x)-1-1。这个是根据(01)推断出来的！

下面，由树的高度为 h-1 的已知条件推出“树的高度为 h 时，它所包含的节点树为 2bh(x)-1”。

当树的高度为 h 时，对于节点x(x为根节点)，其黑高度为bh(x)。

对于节点x的左右子树，它们黑高度为 bh(x) 或者 bh(x)-1。

根据(2)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2bh(x)-1-1 个"；

所以，节点x所包含的节点至少为 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 ) + 1 = 2^bh(x)-1。即节点x所包含的节点至少为 2bh(x)-1。

因此，原命题成立。

由(1)、(2)得出，"高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

## 四、红黑树的基本操作(一) 左旋和右旋 ##

红黑树的基本操作是添加、删除。在对红黑树进行添加或删除之后，都会用到旋转方法。为什么呢？道理很简单，添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树。简单点说，旋转的目的是让树保持红黑树的特性。

旋转包括两种：左旋 和 右旋。下面分别对它们进行介绍。

我们先明确一下各节点的叫法

![1269700-20180530205739191-1817277641.png][]

**左旋**

![1269700-20180530210048121-318495437.png][]

对x进行左旋，意味着"将x变成一个左节点"。

**右旋**

![1269700-20180530210443265-1641107935.png][]

## 五、红黑树的基本操作(二) 添加 ##

将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。详细描述如下：  
**第一步**: 将红黑树当作一颗二叉查找树，将节点插入。 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。  
那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！  
**第二步**：将插入的节点着色为"红色"。  
为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：  
(1) 每个节点或者是黑色，或者是红色。  
(2) 根节点是黑色。  
(3) 每个叶子节点是黑色。 \[注意：这里叶子节点，是指为空的叶子节点！\]  
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。  
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。  
将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。  
**第三步**: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。  
第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？  
对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。  
对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。  
对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。  
对于"特性(4)"，是有可能违背的！  
那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。

根据被插入节点的父节点的情况，可以将"当节点被着色为红色节点，并插入二叉树"划分为三种情况来处理。  
① 情况说明：被插入的节点是根节点。  
处理方法：直接把此节点涂为黑色。  
② 情况说明：被插入的节点的父节点是黑色。  
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。  
③ 情况说明：被插入的节点的父节点是红色。 处理方法：那么，该情况与红黑树的“特性(5)”相冲突。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。

1. (Case 1)叔叔是红色  
1.1 现象说明  
当前节点(即，被插入节点)的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。  
1.2 处理策略  
(01) 将“父节点”设为黑色。  
(02) 将“叔叔节点”设为黑色。  
(03) 将“祖父节点”设为“红色”。  
(04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。  
下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)  
“当前节点”和“父节点”都是红色，违背“特性(4)”。所以，将“父节点”设置“黑色”以解决这个问题。  
但是，将“父节点”由“红色”变成“黑色”之后，违背了“特性(5)”：因为，包含“父节点”的分支的黑色节点的总数增加了1。 解决这个问题的办法是：将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”。关于这里，说明几点：第一，为什么“祖父节点”之前是黑色？这个应该很容易想明白，因为在变换操作之前，该树是红黑树，“父节点”是红色，那么“祖父节点”一定是黑色。 第二，为什么将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”，既然这样，我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题； 但是，这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”，现在我们已知“叔叔节点”是“红色”，将“叔叔节点”设为“黑色”就能解决这个问题。 所以，将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；就解决了该问题。  
按照上面的步骤处理之后：当前节点、父节点、叔叔节点之间都不会违背红黑树特性，但祖父节点却不一定。若此时，祖父节点是根节点，直接将祖父节点设为“黑色”，那就完全解决这个问题了；若祖父节点不是根节点，那我们需要将“祖父节点”设为“新的当前节点”，接着对“新的当前节点”进行分析。  
1.3 示意图

![1269700-20180530211540943-142043999.png][]

2. (Case 2)叔叔是黑色，且当前节点是右孩子  
2.1 现象说明  
当前节点(即，被插入节点)的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子  
2.2 处理策略  
(01) 将“父节点”作为“新的当前节点”。  
(02) 以“新的当前节点”为支点进行左旋。  
下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)  
首先，将“父节点”作为“新的当前节点”；接着，以“新的当前节点”为支点进行左旋。 为了便于理解，我们先说明第(02)步，再说明第(01)步；为了便于说明，我们设置“父节点”的代号为F(Father)，“当前节点”的代号为S(Son)。  
为什么要“以F为支点进行左旋”呢？根据已知条件可知：S是F的右孩子。而之前我们说过，我们处理红黑树的核心思想：将红色的节点移到根节点；然后，将根节点设为黑色。既然是“将红色的节点移到根节点”，那就是说要不断的将破坏红黑树特性的红色节点上移(即向根方向移动)。 而S又是一个右孩子，因此，我们可以通过“左旋”来将S上移！  
按照上面的步骤(以F为支点进行左旋)处理之后：若S变成了根节点，那么直接将其设为“黑色”，就完全解决问题了；若S不是根节点，那我们需要执行步骤(01)，即“将F设为‘新的当前节点’”。那为什么不继续以S为新的当前节点继续处理，而需要以F为新的当前节点来进行处理呢？这是因为“左旋”之后，F变成了S的“子节点”，即S变成了F的父节点；而我们处理问题的时候，需要从下至上(由叶到根)方向进行处理；也就是说，必须先解决“孩子”的问题，再解决“父亲”的问题；所以，我们执行步骤(01)：将“父节点”作为“新的当前节点”。  
2.2 示意图

![1269700-20180530211600981-2016215715.png][]

3. (Case 3)叔叔是黑色，且当前节点是左孩子  
3.1 现象说明  
当前节点(即，被插入节点)的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子  
3.2 处理策略  
(01) 将“父节点”设为“黑色”。  
(02) 将“祖父节点”设为“红色”。  
(03) 以“祖父节点”为支点进行右旋。  
下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)  
为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，“叔叔节点”为U(Uncle)，“父节点”为F(Father)，祖父节点为G(Grand-Father)。  
S和F都是红色，违背了红黑树的“特性(4)”，我们可以将F由“红色”变为“黑色”，就解决了“违背‘特性(4)’”的问题；但却引起了其它问题：违背特性(5)，因为将F由红色改为黑色之后，所有经过F的分支的黑色节点的个数增加了1。那我们如何解决“所有经过F的分支的黑色节点的个数增加了1”的问题呢？ 我们可以通过“将G由黑色变成红色”，同时“以G为支点进行右旋”来解决。  
3.3 示意图

![1269700-20180530211620997-884976786.png][]

上面的进行Case 3处理之后，再将节点"120"当作当前节点，就变成了Case 2的情况。

[https_blog.csdn.net_qq_39344902_article_details_81605850_tdsourcetag_s_pctim_aiomsg]: https://blog.csdn.net/qq_39344902/article/details/81605850?tdsourcetag=s_pctim_aiomsg
[1269700-20180530204257973-2034786443.png]: /images/20211013/ced71eca73b849dca3c79bf6899bdc26.png
[1269700-20180530205739191-1817277641.png]: /images/20211013/7c273260786f467fba29a3c2e33957f2.png
[1269700-20180530210048121-318495437.png]: /images/20211013/dba382f738bc4a61b82a5054bcd3596d.png
[1269700-20180530210443265-1641107935.png]: /images/20211013/4882c649047243139eb3eaf81bd1e5b4.png
[1269700-20180530211540943-142043999.png]: /images/20211013/b50df1c0a2d2498288d0dbd262aa611f.png
[1269700-20180530211600981-2016215715.png]: /images/20211013/bf1e2296087a4b238793960f05c7e787.png
[1269700-20180530211620997-884976786.png]: /images/20211013/d2e180425e21421bacd7595ba69bf068.png