算法之红黑树

拼搏现实的明天。 2022-06-15 01:15 261阅读 0赞

# 红黑树(一) 原理和算法详细介 #

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

1 R-B Tree简介

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

**红黑树的特性**:  
**（1）每个节点或者是黑色，或者是红色。  
（2）根节点是黑色。  
（3）每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]  
（4）如果一个节点是红色的，则它的子节点必须是黑色的。  
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。**

**注意**：  
(01) 特性(3)中的叶子节点，是只为空(NIL或null)的节点。  
(02) 特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

红黑树示意图如下：

![08113839-13765c7010af4a398d06ebee6a624030.png][]

**红黑树的应用**：

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。  
例如，[Java][]中的TreeSet和TreeMap，C++ STL中的set、map，以及[Linux][]虚拟内存的管理，都是通过红黑树去实现的。

这里大致介绍下，红黑树和AVL树的差异。AVL树也是特殊的二叉树，它的特性是“任何节点的左右子树的高度之差不超过1”。基本上，用到红黑树的地方都可以用AVL树(自平衡二叉查找树)去替换。但是一般情况下，在执行添加、删除节点时，AVL树比红黑树执行的操作更多一些，效率更低一些；而且红黑树也是相对平衡的二叉树(从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点)。因此，红黑树的效率会高更一点。

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

2 R-B Tree时间复杂度

**红黑树的时间复杂度为: O(lgn)**  
下面通过“*数学归纳法*”对红黑树的时间复杂度进行证明。

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

证明：  
    "一棵含有n个节点的红黑树的高度至多为2log(n+1)" 的**逆否命题**是 "高度为h的红黑树，它的包含的内节点个数至少为 2^\{h/2\}-1个"。  
    我们只需要证明逆否命题，即可证明原命题为真；即只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2^\{h/2\}-1个"。

从某个节点x出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度，记为bh(x)。  
    由红黑树的"特性(4)"可知 bh(x)>=h/2；进而，我们只需证明 "高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"即可。

到这里，我们将需要证明的定理已经由  
**"一棵含有n个节点的红黑树的高度至多为2log(n+1)"**   
    转变成只需要证明  
**"高度为h的红黑树，它的包含的内节点个数至少为 2^bh(x)-1个"。**

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

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

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

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

当树的高度为 h 时，  
    对于节点x(x为根节点)，其黑高度为bh(x)。  
    对于节点x的左右子树，它们黑高度为 bh(x) 或者 bh(x)-1。  
    根据(02)的已知条件，我们已知 "x的左右子树，即高度为 h-1 的节点，它包含的节点至少为 2^\{bh(x)-1\}-1 个"；

所以，节点x所包含的节点至少为 ( 2^\{bh(x)-1\}-1 ) + ( 2^\{bh(x)-1\}-1 ) + 1 = 2^\{bh(x)-1\}。即节点x所包含的节点至少为 2^\{bh(x)-1\} 。  
    因此，原命题成立。

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

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

3 R-B Tree基本操作

R-B Tree的基本操作是**添加**、**删除**。

添加和删除操作，都会用到两个基本的方法：**左旋** 和 **右旋**，统称为**旋转**。旋转是为了保持红黑树的特性而提供的辅助方法，因为当我们进行添加、删除节点时，可能改变红黑树的特性(例如，删除一个黑色节点之后，就不满足“从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点”这个特性)；这里，我们就需要旋转方法的辅助来让树保持红黑树的特性。

## 3.1 左旋 ##

![08114712-80d6d8afda8f4db58a8e1f0ed06e0537.jpg][]

上面是《[算法][Link 1]导论》中左旋的示意图。  
参考上面的示意图和下面的伪代码，理解“红黑树T的节点x进行左旋”是如何进行的。

LEFT-ROTATE(T, x)  
    
    01  y ← right[x]            // 前提：这里假设x的右孩子为y。下面开始正式操作
    
    02  right[x] ← left[y]      // 将 “y的左孩子” 设为 “x的右孩子”，即 将β设为x的右孩子
    
    03  p[left[y]] ← x          // 将 “x” 设为 “y的左孩子的父亲”，即 将β的父亲设为x
    
    04  p[y] ← p[x]             // 将 “x的父亲” 设为 “y的父亲”
    
    05  if p[x] = nil[T]       
    
    06  then root[T] ← y                 // 情况1：如果 “x的父亲” 是空节点，则将y设为根节点
    
    07  else if x = left[p[x]]  
    
    08            then left[p[x]] ← y    // 情况2：如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”
    
    09            else right[p[x]] ← y   // 情况3：(x是它父节点的右孩子) 将y设为“x的父节点的右孩子”
    
    10  left[y] ← x             // 将 “x” 设为 “y的左孩子”
    
    11  p[x] ← y                // 将 “x的父节点” 设为 “y”

理解上面的代码之后，下面以一个更鲜明的图对左旋转进行说明。理解左旋之后，下面的推理应该非常简单，这里就不过多说明。  
![08114857-b1d3d39660f5459f89337ed56724d3b1.jpg][]

## 3.2 右旋 ##

右旋和左旋是相对的，原理类似。理解左旋后，右旋也很容易理解了。

![08114914-0f13a52a4a87462ab4ed9b3c27e701a8.jpg][]

上面是《算法导论》中右旋的示意图。  
参考上面的示意图和下面的伪代码，理解“红黑树T的节点y进行右旋”是如何进行的。

RIGHT-ROTATE(T, y)  
    
    01  x ← left[y]             // 前提：这里假设y的左孩子为x。下面开始正式操作
    
    02  left[y] ← right[x]      // 将 “x的右孩子” 设为 “y的左孩子”，即 将β设为y的左孩子
    
    03  p[right[x]] ← y         // 将 “y” 设为 “x的右孩子的父亲”，即 将β的父亲设为y
    
    04  p[x] ← p[y]             // 将 “y的父亲” 设为 “x的父亲”
    
    05  if p[y] = nil[T]       
    
    06  then root[T] ← x                 // 情况1：如果 “y的父亲” 是空节点，则将x设为根节点
    
    07  else if y = right[p[y]]  
    
    08            then right[p[y]] ← x   // 情况2：如果 y是它父节点的右孩子，则将x设为“y的父节点的左孩子”
    
    09            else left[p[y]] ← x    // 情况3：(y是它父节点的左孩子) 将x设为“y的父节点的左孩子”
    
    10  right[x] ← y            // 将 “y” 设为 “x的右孩子”
    
    11  p[y] ← x                // 将 “y的父节点” 设为 “x”

理解上面的代码之后，下面以一个更鲜明的图对右旋转进行说明。

![08114955-d1623a80b0de4707bbad73109a607878.jpg][]

**旋转总结**：

(01) 左旋 和 右旋 是相对的两个概念，原理类似。理解一个也就理解了另一个。

(02) 下面谈谈如何区分 左旋 和 右旋。  
在实际应用中，若没有彻底理解 左旋 和 右旋，可能会将它们混淆。下面谈谈我对如何区分 左旋 和 右旋 的理解。

## 3.3 区分 左旋 和 右旋 ##

无论 左旋 或 右旋，它们都是以某一个**节点**为中心点。**注意：这里，我们理解成以节点(节点x)进行旋转，而不是以一个分支(分支xy轴 或 分支xz轴)进行旋转！！！**

我们以图来进行说明。

**左旋示例图**(以x为节点进行左旋)：

z
    
       x                          /                  
    
      / \      --(左旋)-->       x
    
     y   z                      /
    
                               y

对x进行左旋，意味着，将“x的右孩子”设为“x的父亲节点”；即，将 x变成了一个左节点(x成了为z的左孩子)！。 因此，**左旋中的“左”，意味着“被旋转的节点将变成一个左节点”**。

**右旋示例图**(以x为节点进行右旋)：

y
    
       x                            \                 
    
      / \      --(右旋)-->           x
    
     y   z                            \
    
                                       z

对x进行右旋，意味着，将“x的左孩子”设为“x的父亲节点”；即，将 x变成了一个右节点(x成了为y的右孩子)！ 因此，**右旋中的“右”，意味着“被旋转的节点将变成一个右节点”**。

## 3.4 添加操作 ##

向一颗含有n个节点的红黑树中插入一个节点，可以在时间O(lgn)内完成。

将节点z插入红黑树T内。需要执行的操作依次时：首先，将T当作一颗二叉树，将z插入；然后，将z着色为红色；最后，通过RB-INSERT-FIXUP来对节点重新着色并旋转，以此来保证删除节点后的树仍然是一颗红黑树。

**(01) 将T当作一颗二叉树，将z插入。**  
    因为红黑树本身就是一颗二叉树，所以，我们可以根据二叉树的性质将z插入。

**(02) 将z着色为红色。**  
  在介绍为什么将则着色为红色之前，我们重新温习一下红黑树的特性：  
**（1）每个节点或者是黑色，或者是红色。**  
**（2）根节点是黑色。**  
**（3）每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]**  
**（4）如果一个节点是红色的，则它的子节点必须是黑色的。**  
**（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。**

将插入的节点着色为红色，不会违背“特性(5)”；而若将插入的节点着色为黑色，会违背该特性。

**(03) 通过RB-INSERT-FIXUP来对节点重新着色并旋转。**  
  因为(02)中插入一个红色节点之后，虽然没有违背“特性(5)”，但是却可能违背了其它特性(例如，若被插入节点的父节点也是红色；插入后，则违背了“特性(4)”)。我们需要通过RB-INSERT-FIXUP进行节点颜色的调整以及旋转等工作，让树仍然是一颗红黑树。

下面是《算法导论》中 “向红黑树T中插入节点z”的伪代码

RB-INSERT(T, z)  
    
    01  y ← nil[T]                        // 新建节点“y”，将y设为空节点。
    
    02  x ← root[T]                       // 设“红黑树T”的根节点为“x”
    
    03  while x ≠ nil[T]                  // 找出要插入的节点“z”在二叉树T中的位置“y”
    
    04      do y ← x                      
    
    05         if key[z] < key[x]  
    
    06            then x ← left[x]  
    
    07            else x ← right[x]  
    
    08  p[z] ← y                          // 设置 “z的父亲” 为 “y”
    
    09  if y = nil[T]                     
    
    10     then root[T] ← z               // 情况1：若y是空节点，则将z设为根
    
    11     else if key[z] < key[y]        
    
    12             then left[y] ← z       // 情况2：若“z所包含的值” < “y所包含的值”，则将z设为“y的左孩子”
    
    13             else right[y] ← z      // 情况3：(“z所包含的值” >= “y所包含的值”)将z设为“y的右孩子” 
    
    14  left[z] ← nil[T]                  // z的左孩子设为空
    
    15  right[z] ← nil[T]                 // z的右孩子设为空。至此，已经完成将“节点z插入到二叉树”中了。
    
    16  color[z] ← RED                    // 将z着色为“红色”
    
    17  RB-INSERT-FIXUP(T, z)             // 通过RB-INSERT-FIXUP对红黑树的节点进行颜色修改以及旋转，让树T仍然是一颗红黑树

结合伪代码以及为代码上面的说明，先理解RB-INSERT。理解了RB-INSERT之后，我们接着对 RB-INSERT-FIXUP的伪代码进行说明

RB-INSERT-FIXUP(T, z)
    
    01 while color[p[z]] = RED                                                  // 若“当前节点(z)的父节点是红色”，则进行以下处理。
    
    02     do if p[z] = left[p[p[z]]]                                           // 若“z的父节点”是“z的祖父节点的左孩子”，则进行以下处理。
    
    03           then y ← right[p[p[z]]]                                        // 将y设置为“z的叔叔节点(z的祖父节点的右孩子)”
    
    04                if color[y] = RED                                         // Case 1条件：叔叔是红色
    
    05                   then color[p[z]] ← BLACK                    ? Case 1   //  (01) 将“父节点”设为黑色。
    
    06                        color[y] ← BLACK                       ? Case 1   //  (02) 将“叔叔节点”设为黑色。
    
    07                        color[p[p[z]]] ← RED                   ? Case 1   //  (03) 将“祖父节点”设为“红色”。
    
    08                        z ← p[p[z]]                            ? Case 1   //  (04) 将“祖父节点”设为“当前节点”(红色节点)
    
    09                   else if z = right[p[z]]                                // Case 2条件：叔叔是黑色，且当前节点是右孩子
    
    10                           then z ← p[z]                       ? Case 2   //  (01) 将“父节点”作为“新的当前节点”。
    
    11                                LEFT-ROTATE(T, z)              ? Case 2   //  (02) 以“新的当前节点”为支点进行左旋。
    
    12                           color[p[z]] ← BLACK                 ? Case 3   // Case 3条件：叔叔是黑色，且当前节点是左孩子。(01) 将“父节点”设为“黑色”。
    
    13                           color[p[p[z]]] ← RED                ? Case 3   //  (02) 将“祖父节点”设为“红色”。
    
    14                           RIGHT-ROTATE(T, p[p[z]])            ? Case 3   //  (03) 以“祖父节点”为支点进行右旋。
    
    15        else (same as then clause with "right" and "left" exchanged)      // 若“z的父节点”是“z的祖父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
    
    16 color[root[T]] ← BLACK

总的来说：当节点z被着色为红色节点，并插入二叉树时，有三种情况。

**情况一：被插入的节点是根节点。**  
    直接把此节点涂为黑色。

**情况二：被插入的节点的父节点是黑色。**  
    什么也不需要做。节点被插入后，仍然是红黑树。

**情况三：被插入的节点的父节点是红色。**  
    那么，该情况与红黑树的“特性(5)”相冲突。**情况三包含了“Case 1”、“Case 2” 和“Case 3”三种情况**，情况三的目的是恢复红黑树的特性，它的**处理思想**是：**将红色的节点移到根节点；然后，将根节点设为黑色。**下面介绍情况三的三种情况。

### Case 1：叔叔是红色 ###

Case 1 现象说明：当前节点的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。  
Case 1 处理策略：  
    (01) 将“父节点”设为黑色。  
    (02) 将“叔叔节点”设为黑色。  
    (03) 将“祖父节点”设为“红色”。  
    (04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。

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

Case 1 处理前\[当前节点是4\]：  
![08115538-f43813b9997642dbbe722bbe64f406b3.png][]

Case 1 处理后：

![08115625-1e385553813d4a208f86d1a0166647e3.png][]

### Case 2：叔叔是黑色，且当前节点是右孩子 ###

Case 2 现象说明：当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的右孩子  
Case 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)：将“父节点”作为“新的当前节点”。

Case 2 处理前\[当前节点是7\]：

![08115733-b24b6961240e4787907d4805d3ee616b.png][]

Case 2处理后：

![08115739-26c15117e01f42e29c3c3b45ca6191f4.png][]

### Case 3：叔叔是黑色，且当前节点是左孩子 ###

Case 3：叔叔是黑色，且当前节点是左孩子  
Case 3 现象说明：当前节点的父节点是红色，叔叔节点是黑色，且当前节点是其父节点的左孩子  
Case 3 处理策略：  
    (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为支点进行右旋”来解决。

Case 3 处理前\[当前节点是2\]：

![08115759-4914d01f680c45c1992251d7b0cb9533.png][]

Case 3 处理后：

![08115807-82464d36a5774998b171a8b57a78f2d2.png][]

## 3.5 删除操作 ##

将红黑树T内的节点z删除。需要执行的操作依次是：首先，将T当作一颗二叉树，将节点删除；然后，通过RB-DELETE-FIXUP来对节点重新着色并旋转，以此来保证删除节点后的树仍然是一颗红黑树。

**(01) 将T当作一颗二叉树，将节点删除。**

这和"删除常规二叉搜索树中删除节点的方法是一样的"。分3种情况：  
    第一种，被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。  
    第二种，被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。  
    第三种，被删除节点有两个儿子。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。

这里有两点需要说明：第一步中复制时，仅仅复制内容，即将“它的后继节点的内容”复制给“该节点的内容”。    这相当于用“该节点的后继节点”取代“该节点”，之后就删除“该节点的后继节点”即可，而不需要删除“该节点”(因为“该节点”已经被“它的后继节点”所取代)。  
                                       第二步中删除“该节点的后继节点”时，需要注意：“该节点的后继节点”不可能是双子非空，这个根据二叉树的特性可知。 既然“该节点的后继节点”不可能双子都非空，就意味着“该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按“第一种”种的办法进行处理；若只有一个儿子，则按“第二种”中的办法进行处理。

**(02) 通过RB-DELETE-FIXUP来对节点重新着色并旋转，以此来保证删除节点后的树仍然是一颗红黑树。**

因为(01)中删除节点之后，可能会违背红黑树的特性。所以需要，通过RB-DELETE-FIXUP来重新校正，为当前树保持红黑树的特性。

下面是《算法导论》中 “从红黑树T中删除节点z”的伪代码

RB-DELETE(T, z)
    
    01 if left[z] = nil[T] or right[z] = nil[T]         
    
    02    then y ← z                                  // 若“z的左孩子” 或 “z的右孩子”为空，则将“z”赋值给 “y”；
    
    03    else y ← TREE-SUCCESSOR(z)                  // 否则，将“z的后继节点”赋值给 “y”。
    
    04 if left[y] ≠ nil[T]
    
    05    then x ← left[y]                            // 若“y的左孩子” 不为空，则将“y的左孩子” 赋值给 “x”；
    
    06    else x ← right[y]                           // 否则，“y的右孩子” 赋值给 “x”。
    
    07 p[x] ← p[y]                                    // 将“y的父节点” 设置为 “x的父节点”
    
    08 if p[y] = nil[T]                               
    
    09    then root[T] ← x                            // 情况1：若“y的父节点” 为空，则设置“x” 为 “根节点”。
    
    10    else if y = left[p[y]]                    
    
    11            then left[p[y]] ← x                 // 情况2：若“y是它父节点的左孩子”，则设置“x” 为 “y的父节点的左孩子”
    
    12            else right[p[y]] ← x                // 情况3：若“y是它父节点的右孩子”，则设置“x” 为 “y的父节点的右孩子”
    
    13 if y ≠ z                                    
    
    14    then key[z] ← key[y]                        // 若“y的值” 赋值给 “z”。注意：这里只拷贝z的值给y，而没有拷贝z的颜色！！！
    
    15         copy y's satellite data into z         
    
    16 if color[y] = BLACK                            
    
    17    then RB-DELETE-FIXUP(T, x)                  // 若“y为黑节点”，则调用
    
    18 return y

结合伪代码以及为代码上面的说明，先理解RB-DELETE。理解了RB-DELETE之后，接着对 RB-DELETE-FIXUP的伪代码进行说明

RB-DELETE-FIXUP(T, x)
    
    01 while x ≠ root[T] and color[x] = BLACK  
    
    02     do if x = left[p[x]]      
    
    03           then w ← right[p[x]]                                             // 若 “x”是“它父节点的左孩子”，则设置 “w”为“x的叔叔”(即x为它父节点的右孩子)                                          
    
    04                if color[w] = RED                                           // Case 1: x是“黑+黑”节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。
    
    05                   then color[w] ← BLACK                        ?  Case 1   //   (01) 将x的兄弟节点设为“黑色”。
    
    06                        color[p[x]] ← RED                       ?  Case 1   //   (02) 将x的父节点设为“红色”。
    
    07                        LEFT-ROTATE(T, p[x])                    ?  Case 1   //   (03) 对x的父节点进行左旋。
    
    08                        w ← right[p[x]]                         ?  Case 1   //   (04) 左旋后，重新设置x的兄弟节点。
    
    09                if color[left[w]] = BLACK and color[right[w]] = BLACK       // Case 2: x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。
    
    10                   then color[w] ← RED                          ?  Case 2   //   (01) 将x的兄弟节点设为“红色”。
    
    11                        x ←  p[x]                               ?  Case 2   //   (02) 设置“x的父节点”为“新的x节点”。
    
    12                   else if color[right[w]] = BLACK                          // Case 3: x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。
    
    13                           then color[left[w]] ← BLACK          ?  Case 3   //   (01) 将x兄弟节点的左孩子设为“黑色”。
    
    14                                color[w] ← RED                  ?  Case 3   //   (02) 将x兄弟节点设为“红色”。
    
    15                                RIGHT-ROTATE(T, w)              ?  Case 3   //   (03) 对x的兄弟节点进行右旋。
    
    16                                w ← right[p[x]]                 ?  Case 3   //   (04) 右旋后，重新设置x的兄弟节点。
    
    17                         color[w] ← color[p[x]]                 ?  Case 4   // Case 4: x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的。(01) 将x父节点颜色 赋值给 x的兄弟节点。
    
    18                         color[p[x]] ← BLACK                    ?  Case 4   //   (02) 将x父节点设为“黑色”。
    
    19                         color[right[w]] ← BLACK                ?  Case 4   //   (03) 将x兄弟节点的右子节设为“黑色”。
    
    20                         LEFT-ROTATE(T, p[x])                   ?  Case 4   //   (04) 对x的父节点进行左旋。
    
    21                         x ← root[T]                            ?  Case 4   //   (05) 设置“x”为“根节点”。
    
    22        else (same as then clause with "right" and "left" exchanged)        // 若 “x”是“它父节点的右孩子”，将上面的操作中“right”和“left”交换位置，然后依次执行。
    
    23 color[x] ← BLACK

在开始说明RB-DELETE-FIXUP之前，我们再次温习一下红黑树的几个特性：  
**（1）每个节点或者是黑色，或者是红色。**  
**（2）根节点是黑色。**  
**（3）每个叶子节点（NIL）是黑色。 \[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！\]**  
**（4）如果一个节点是红色的，则它的子节点必须是黑色的。**  
**（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。**

在RB-DELETE中，若被删除的节点y是黑色的，则会产生三个问题。  
问题一：如y是根节点，而删除y后，它的红色孩子成了新的根节点，则违反了“特性(2)”。  
问题二：如x和“y的父节点”都是红色，则违反了“特性(4)”。因为删除y之后，“y的父节点”和“x”是父子关系。  
问题三：删除y，意味着删除了一个黑色节点，那么“之前所有包含y的路径上的黑节点总数减少了1”，这违反了“特性(5)”。  
    **合计起来，违反了“特性(2)、(4)、(5)”三个特性。**

RB-DELETE-FIXUP需要解决上面的三个问题，进而保持红黑树的全部特性。  
    为了便于分析，我们假设“x包含一个额外的黑色”(x原本的颜色还存在)，这样就不会违反“特性(5)”。为什么呢？  
    通过RB-DELETE算法，我们知道：删除节点y之后，x占据了原来节点y的位置。 既然删除y(y是黑色)，意味着减少一个黑色节点；那么，再在该位置上增加一个黑色即可。这样，当我们假设“x包含一个额外的黑色”，就正好弥补了“删除y所丢失的黑色节点”，也就不会违反“特性(5)”。 因此，假设“x包含一个额外的黑色”(x原本的颜色还存在)，这样就不会违反“特性(5)”。  
    现在，x不仅包含它原本的颜色属性，x还包含一个额外的黑色。即x的颜色属性是“红+黑”或“黑+黑”，它违反了“特性(1)”。

**现在，我们面临的问题，由解决“违反了特性(2)、(4)、(5)三个特性”转换成了“解决违反特性(1)、(2)、(4)三个特性”。**  
    RB-DELETE-FIXUP就是通过算法恢复红黑树的特性(1)、(2)、(4)。**RB-DELETE-FIXUP的思想**是：**将x所包含的额外的黑色不断沿树上移(向根方向移动)**，直到：  
(01) x指向一个“红+黑”节点。此时，将x设为一个“黑”节点即可。  
(02) x指向根。此时，将x设为一个“黑”节点即可。  
(03) 做必要的旋转和颜色修改。

将上面的思想，可以概括为3种情况。

**情况一：x是“红+黑”节点。**  
    直接把x设为黑色，结束。此时红黑树性质全部恢复。

**情况二：x是“黑+黑”节点，且x是根。**  
    什么都不做，结束。此时红黑树性质全部恢复。

**情况三：x是“黑+黑”节点，且x不是根。这又可以划分了4种情况：Case 1、Case 2、Case 3、Case 4。**

### Case 1 ###

Case 1 现象说明：x是“黑+黑”节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。  
Case 1 处理策略：  
    (01) 将x的兄弟节点设为“黑色”。  
    (02) 将x的父节点设为“红色”。  
    (03) 对x的父节点进行左旋。  
    (04) 左旋后，重新设置x的兄弟节点。

下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)  
    这样做的目的是将“Case 1”转换为“Case 2”、“Case 3”或“Case 4”，从而进行进一步的处理。对x的父节点进行左旋；左旋后，为了保持红黑树特性，就需要在左旋前“将x的兄弟节点设为黑色”，同时“将x的父节点设为红色”；左旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。

Case 1 处理前\[当前节点是A\]：

![08120332-0292ed7aa62f4b3cb22c55df5ebab72c.jpg][]

Case 1 处理后：

![08120347-480dac6fb19b45e2849239a444d18129.jpg][]

### Case 2 ###

Case 2 现象说明：x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。  
Case 2 处理策略：  
    (01) 将x的兄弟节点设为“红色”。  
    (02) 设置“x的父节点”为“新的x节点”。

下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)  
    这个情况的处理思想：是**将“x中多余的一个黑色属性上移(往根方向移动)”**。  x是“黑+黑”节点，我们将x由“黑+黑”节点 变成 “黑”节点，多余的一个“黑”属性移到x的父节点中，即x的父节点多出了一个黑属性(若x的父节点原先是“黑”，则此时变成了“黑+黑”；若x的父节点原先时“红”，则此时变成了“红+黑”)。 此时，需要注意的是：所有经过x的分支中黑节点个数没变化；但是，所有经过x的兄弟节点的分支中黑色节点的个数增加了1(因为x的父节点多了一个黑色属性)！为了解决这个问题，我们需要将“所有经过x的兄弟节点的分支中黑色节点的个数减1”即可，那么就可以通过“将x的兄弟节点由黑色变成红色”来实现。  
    经过上面的步骤(将x的兄弟节点设为红色)，多余的一个颜色属性(黑色)已经跑到x的父节点中。我们需要将x的父节点设为“新的x节点”进行处理。若“新的x节点”是“黑+红”，直接将“新的x节点”设为黑色，即可完全解决该问题；若“新的x节点”是“黑+黑”，则需要对“新的x节点”进行进一步处理。

Case 2 处理前\[当前节点是A\]：

![08120356-13bd40de04564cd08eb3ea191807b30c.jpg][]

Case 2 处理后：

![08120403-e48e7bc7e30f41ab8c0be93dd71dab4f.jpg][]

### Case 3 ###

Case 3 现象说明：x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。  
Case 3 处理策略：  
    (01) 将x兄弟节点的左孩子设为“黑色”。  
    (02) 将x兄弟节点设为“红色”。  
    (03) 对x的兄弟节点进行右旋。  
    (04) 右旋后，重新设置x的兄弟节点。

下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)  
    我们处理“Case 3”的目的是**为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理**。转换的方式是对x的兄弟节点进行右旋；为了保证右旋后，它仍然是红黑树，就需要在右旋前“将x的兄弟节点的左孩子设为黑色”，同时“将x的兄弟节点设为红色”；右旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。

Case 3 处理前\[当前节点是A\]：

![08120415-ff69ed38ec19490cb07e2b69266c45f1.jpg][]

Case 3 处理后：

![08120430-ae90d6480d0340dea2dcbb2f8e5742ff.jpg][]

### Case 4 ###

Case 4 现象说明：x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。  
Case 4 现象说明：x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的。  
Case 4 处理策略：  
    (01) 将x父节点颜色 赋值给 x的兄弟节点。  
    (02) 将x父节点设为“黑色”。  
    (03) 将x兄弟节点的右子节设为“黑色”。  
    (04) 对x的父节点进行左旋。  
    (05) 设置“x”为“根节点”。

下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)  
    我们处理“Case 4”的目的是：**去掉x中额外的黑色，将x变成单独的黑色**。处理的方式是“：***进行颜色修改，然后对x的父节点进行左旋***。下面，我们来分析是如何实现的。  
    为了便于说明，我们设置“当前节点”为S(Original Son)，“兄弟节点”为B(Brother)，“兄弟节点的左孩子”为BLS(Brother's Left Son)，“兄弟节点的右孩子”为BRS(Brother's Right Son)，“父节点”为F(Father)。  
    我们要对F进行左旋。但在**左旋前**，我们需要**调换F和B的颜色**，并**设置BRS为黑色**。为什么需要这里处理呢？因为左旋后，F和BLS是父子关系，而我们已知BL是红色，如果F是红色，则违背了“特性(4)”；为了解决这一问题，我们将“F设置为黑色”。 但是，F设置为黑色之后，为了保证满足“特性(5)”，即为了保证左旋之后：  
        第一，“同时经过根节点和S的分支的黑色节点个数不变”。  
              若满足“第一”，只需要S丢弃它多余的颜色即可。因为S的颜色是“黑+黑”，而左旋后“同时经过根节点和S的分支的黑色节点个数”增加了1；现在，只需将S由“黑+黑”变成单独的“黑”节点，即可满足“第一”。  
        第二，“同时经过根节点和BLS的分支的黑色节点数不变”。  
              若满足“第二”，只需要将“F的原始颜色”赋值给B即可。之前，我们已经将“F设置为黑色”(即，将B的颜色"黑色"，赋值给了F)。至此，我们算是调换了F和B的颜色。  
        第三，“同时经过根节点和BRS的分支的黑色节点数不变”。  
             在“第二”已经满足的情况下，若要满足“第三”，只需要将BRS设置为“黑色”即可。  
        经过，上面的处理之后。红黑树的特性全部得到的满足！接着，我们将x设为根节点，就可以跳出while循环(参考伪代码)；即完成了全部处理。

至此，我们就完成了Case 4的处理。理解Case 4的核心，是了解如何“去掉当前节点额外的黑色”。

Case 4 处理前\[当前节点是A\]：  
![08120450-dec5feba491d420faec13303125c3a09.jpg][]

Case 4 处理后：

![08120506-406365b35b6a4389b1b2fb5beb434937.jpg][]

OK！至此，红黑树的理论知识差不多讲完了。后续再更新红黑树的实现代码！

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

# 参考文献 #

1, 《算法导论》

2,  教你透彻了解红黑树

[08113839-13765c7010af4a398d06ebee6a624030.png]: /images/20220615/a26c9c73a06243fcabe00329fa5f9c8d.png
[Java]: http://lib.csdn.net/base/javase
[Linux]: http://lib.csdn.net/base/linux
[08114712-80d6d8afda8f4db58a8e1f0ed06e0537.jpg]: /images/20220615/e6bd7830b7be4a30869af143097cbd42.png
[Link 1]: http://lib.csdn.net/base/datastructure
[08114857-b1d3d39660f5459f89337ed56724d3b1.jpg]: /images/20220615/751aee438dfc44c69c82723346c88bbe.png
[08114914-0f13a52a4a87462ab4ed9b3c27e701a8.jpg]: /images/20220615/275b088f3b7d4839a99d484c63694229.png
[08114955-d1623a80b0de4707bbad73109a607878.jpg]: /images/20220615/a4222367c8d84626995d5c07cb5e33a5.png
[08115538-f43813b9997642dbbe722bbe64f406b3.png]: /images/20220615/5daff730209c46b7a0c38eebcb2265a0.png
[08115625-1e385553813d4a208f86d1a0166647e3.png]: /images/20220615/316d0257921d4b4998bdded7ac9996c5.png
[08115733-b24b6961240e4787907d4805d3ee616b.png]: /images/20220615/783c27a25c4f4ef39440ccd8cdb0f204.png
[08115739-26c15117e01f42e29c3c3b45ca6191f4.png]: /images/20220615/bbb14d6d1e624d768a52b2a8bd3adabf.png
[08115759-4914d01f680c45c1992251d7b0cb9533.png]: /images/20220615/e07db32e8da44128888c8c0712c8ca49.png
[08115807-82464d36a5774998b171a8b57a78f2d2.png]: /images/20220615/088a3e0012604ba3aa4fe5e1ce07094c.png
[08120332-0292ed7aa62f4b3cb22c55df5ebab72c.jpg]: /images/20220615/efcc6d67a58c48ee989ec94def013002.png
[08120347-480dac6fb19b45e2849239a444d18129.jpg]: /images/20220615/f8ebdb34b7f043858be8d6be599fa64d.png
[08120356-13bd40de04564cd08eb3ea191807b30c.jpg]: /images/20220615/dc951da578d141869846d7fbc21c6970.png
[08120403-e48e7bc7e30f41ab8c0be93dd71dab4f.jpg]: /images/20220615/d077042970994526ae4908206717a169.png
[08120415-ff69ed38ec19490cb07e2b69266c45f1.jpg]: /images/20220615/97f85886f6454c8ab40556151dcca585.png
[08120430-ae90d6480d0340dea2dcbb2f8e5742ff.jpg]: /images/20220615/6c93439e1baf4b4aae326dee1d340c79.png
[08120450-dec5feba491d420faec13303125c3a09.jpg]: /images/20220615/b745d5ecbaa441eab6bdf341d3990ad4.png
[08120506-406365b35b6a4389b1b2fb5beb434937.jpg]: /images/20220615/6332e730de29416fa36ae6961c6fc06c.png