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

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

 原文地址：http://www.cnblogs.com/skywang12345/p/3245399.html

概要

目录

1 红黑树的介绍

2 红黑树的应用

3 红黑树的时间复杂度和相关证明

4 红黑树的基本操作(一) 左旋和右旋

5 红黑树的基本操作(二) 添加

6 红黑树的基本操作(三) 删除

     作者：Sky Wang    于 2013-08-08                          

     概述：R-B Tree，又称为“红黑树”。本文参考了《算法导论》中红黑树相关知识，加之自己的理解，然后以图文的形式对红黑树进行说明。本文的主要内容包括：红黑树的特性，红黑树的时间复杂度和它的证明，红黑树的左旋、右旋、插入、删除等操作。

     请尊重版权，转载注明出处：http://www.cnblogs.com/skywang12345/p/3245399.html

更多内容: 数据结构与算法系列 目录 

(01) 红黑树(一)之 原理和算法详细介绍

(02) 红黑树(二)之 C语言的实现

(03) 红黑树(三)之 Linux内核中红黑树的经典实现

(04) 红黑树(四)之 C++的实现 

(05) 红黑树(五)之 Java的实现

(06) 红黑树(六)之 参考资料

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)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

红黑树示意图如下：

红黑树的应用

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是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个"。

(01) 当树的高度h=0时，

    内节点个数是0，bh(x) 为0，2bh(x)-1 也为 0。显然，原命题成立。

(02) 当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。

    根据(02)的已知条件，我们已知 "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。

    因此，原命题成立。

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

    因此，“一棵含有n个节点的红黑树的高度至多为2log(n+1)”。

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

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

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

1. 左旋

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

左旋的伪代码《算法导论》：参考上面的示意图和下面的伪代码，理解“红黑树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”      

理解左旋之后，看看下面一个更鲜明的例子。你可以先不看右边的结果，自己尝试一下。

2. 右旋

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

右旋的伪代码《算法导论》：参考上面的示意图和下面的伪代码，理解“红黑树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”      

理解右旋之后，看看下面一个更鲜明的例子。你可以先不看右边的结果，自己尝试一下。

旋转总结：

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

(02) 下面谈谈如何区分 左旋 和 右旋。

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

3. 区分 左旋 和 右旋

仔细观察上面"左旋"和"右旋"的示意图。我们能清晰的发现，它们是对称的。无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。

左旋示例图(以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的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。

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

将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一颗红黑树。详细描述如下：

第一步: 将红黑树当作一颗二叉查找树，将节点插入。

       红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。

       好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！

第二步：将插入的节点着色为"红色"。

       为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：

(1) 每个节点或者是黑色，或者是红色。

(2) 根节点是黑色。

(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]

(4) 如果一个节点是红色的，则它的子节点必须是黑色的。

(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

       将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。o(∩∩)o...哈哈

第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。

       第二步中，将插入节点着色为"红色"之后，不会违背"特性(5)"。那它到底会违背哪些特性呢？

       对于"特性(1)"，显然不会违背了。因为我们已经将它涂成红色了。

       对于"特性(2)"，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。

       对于"特性(3)"，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。

       对于"特性(4)"，是有可能违背的！

       那接下来，想办法使之"满足特性(4)"，就可以将树重新构造成红黑树了。

下面看看代码到底是怎样实现这三步的。

添加操作的伪代码《算法导论》

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)”相冲突。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据"叔叔节点的情况"，将这种情况进一步划分为3种情况(Case)。

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

上面三种情况(Case)处理问题的核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色。下面对它们详细进行介绍。

1. (Case 1)叔叔是红色

1.1 现象说明

当前节点(即，被插入节点)的父节点是红色，且当前节点的祖父节点的另一个子节点（叔叔节点）也是红色。

1.2 处理策略

(01) 将“父节点”设为黑色。

(02) 将“叔叔节点”设为黑色。

(03) 将“祖父节点”设为“红色”。

(04) 将“祖父节点”设为“当前节点”(红色节点)；即，之后继续对“当前节点”进行操作。

    下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)

    “当前节点”和“父节点”都是红色，违背“特性(4)”。所以，将“父节点”设置“黑色”以解决这个问题。

    但是，将“父节点”由“红色”变成“黑色”之后，违背了“特性(5)”：因为，包含“父节点”的分支的黑色节点的总数增加了1。  解决这个问题的办法是：将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”。关于这里，说明几点：第一，为什么“祖父节点”之前是黑色？这个应该很容易想明白，因为在变换操作之前，该树是红黑树，“父节点”是红色，那么“祖父节点”一定是黑色。 第二，为什么将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；能解决“包含‘父节点’的分支的黑色节点的总数增加了1”的问题。这个道理也很简单。“包含‘父节点’的分支的黑色节点的总数增加了1” 同时也意味着 “包含‘祖父节点’的分支的黑色节点的总数增加了1”，既然这样，我们通过将“祖父节点”由“黑色”变成“红色”以解决“包含‘祖父节点’的分支的黑色节点的总数增加了1”的问题； 但是，这样处理之后又会引起另一个问题“包含‘叔叔’节点的分支的黑色节点的总数减少了1”，现在我们已知“叔叔节点”是“红色”，将“叔叔节点”设为“黑色”就能解决这个问题。 所以，将“祖父节点”由“黑色”变成红色，同时，将“叔叔节点”由“红色”变成“黑色”；就解决了该问题。

    按照上面的步骤处理之后：当前节点、父节点、叔叔节点之间都不会违背红黑树特性，但祖父节点却不一定。若此时，祖父节点是根节点，直接将祖父节点设为“黑色”，那就完全解决这个问题了；若祖父节点不是根节点，那我们需要将“祖父节点”设为“新的当前节点”，接着对“新的当前节点”进行分析。

1.3 示意图

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 示意图

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为支点进行右旋”来解决。

2.3 示意图

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

红黑树的基本操作(三) 删除

将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：

第一步：将红黑树当作一颗二叉查找树，将节点删除。

       这和"删除常规二叉查找树中删除节点的方法是一样的"。分3种情况：

       ① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。

       ② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。

       ③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给"被删除节点"之后，再将后继节点删除。这样就巧妙的将问题转换为"删除后继节点"的情况了，下面就考虑后继节点。 在"被删除节点"有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然"的后继节点"不可能双子都非空，就意味着"该节点的后继节点"要么没有儿子，要么只有一个儿子。若没有儿子，则按"情况① "进行处理；若只有一个儿子，则按"情况② "进行处理。

第二步：通过"旋转和重新着色"等一系列来修正该树，使之重新成为一棵红黑树。

       因为"第一步"中删除节点之后，可能会违背红黑树的特性。所以需要通过"旋转和重新着色"来修正该树，使之重新成为一棵红黑树。

删除操作的伪代码《算法导论》

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         

下面对删除函数进行分析。在分析之前，我们再次温习一下红黑树的几个特性：

(1) 每个节点或者是黑色，或者是红色。

(2) 根节点是黑色。

(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]

(4) 如果一个节点是红色的，则它的子节点必须是黑色的。

(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

      前面我们将"删除红黑树中的节点"大致分为两步，在第一步中"将红黑树当作一颗二叉查找树，将节点删除"后，可能违反"特性(2)、(4)、(5)"三个特性。第二步需要解决上面的三个问题，进而保持红黑树的全部特性。

      为了便于分析，我们假设"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所包含的额外的黑色不断沿树上移(向根方向移动)，直到出现下面的姿态：

a) x指向一个"红+黑"节点。此时，将x设为一个"黑"节点即可。

b) x指向根。此时，将x设为一个"黑"节点即可。

c) 非前面两种姿态。

将上面的姿态，可以概括为3种情况。

① 情况说明：x是“红+黑”节点。

    处理方法：直接把x设为黑色，结束。此时红黑树性质全部恢复。

② 情况说明：x是“黑+黑”节点，且x是根。

    处理方法：什么都不做，结束。此时红黑树性质全部恢复。

③ 情况说明：x是“黑+黑”节点，且x不是根。

    处理方法：这种情况又可以划分为4种子情况。这4种子情况如下表所示：

现象说明	处理策略
Case 1	x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。	(01) 将x的兄弟节点设为“黑色”。 (02) 将x的父节点设为“红色”。 (03) 对x的父节点进行左旋。 (04) 左旋后，重新设置x的兄弟节点。
Case 2	x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。	(01) 将x的兄弟节点设为“红色”。 (02) 设置“x的父节点”为“新的x节点”。
Case 3	x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。	(01) 将x兄弟节点的左孩子设为“黑色”。 (02) 将x兄弟节点设为“红色”。 (03) 对x的兄弟节点进行右旋。 (04) 右旋后，重新设置x的兄弟节点。
Case 4	x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。	(01) 将x父节点颜色 赋值给 x的兄弟节点。 (02) 将x父节点设为“黑色”。 (03) 将x兄弟节点的右子节设为“黑色”。 (04) 对x的父节点进行左旋。 (05) 设置“x”为“根节点”。

1. (Case 1)x是"黑+黑"节点，x的兄弟节点是红色

1.1 现象说明

x是"黑+黑"节点，x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

1.2 处理策略

(01) 将x的兄弟节点设为“黑色”。

(02) 将x的父节点设为“红色”。

(03) 对x的父节点进行左旋。

(04) 左旋后，重新设置x的兄弟节点。

      下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)

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

1.3 示意图

2. (Case 2) x是"黑+黑"节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色

2.1 现象说明

x是“黑+黑”节点，x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。

2.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节点”进行进一步处理。

2.3 示意图

3. (Case 3)x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的

3.1 现象说明

x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的左孩子是红色，右孩子是黑色的。

3.2 处理策略

(01) 将x兄弟节点的左孩子设为“黑色”。

(02) 将x兄弟节点设为“红色”。

(03) 对x的兄弟节点进行右旋。

(04) 右旋后，重新设置x的兄弟节点。

       下面谈谈为什么要这样处理。(建议理解的时候，通过下面的图进行对比)

       我们处理“Case 3”的目的是为了将“Case 3”进行转换，转换成“Case 4”,从而进行进一步的处理。转换的方式是对x的兄弟节点进行右旋；为了保证右旋后，它仍然是红黑树，就需要在右旋前“将x的兄弟节点的左孩子设为黑色”，同时“将x的兄弟节点设为红色”；右旋后，由于x的兄弟节点发生了变化，需要更新x的兄弟节点，从而进行后续处理。

3.3 示意图

4. (Case 4)x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色

4.1 现象说明

x是“黑+黑”节点，x的兄弟节点是黑色；x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色。

4.2 处理策略

(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的核心，是了解如何“去掉当前节点额外的黑色”。

4.3 示意图

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

参考文献

1, 《算法导论》

2,  教你透彻了解红黑树

----------------------------------------------代码附带说明------------------------------------------------------

版权声明：本文为Young++原创文章，未经Young++允许不得转载。

目录(?)[-]

1. 一 基础知识
2. 二查找
3. 三 插入
   1. 1 叔结点为红
   2. 2 叔结点为黑致变结点是父结点的右孩子
   3. 3 叔叔结点为黑致变结点是父结点的左孩子
4. 四 删除
   1. 1 兄弟结点为红
   2. 2 兄弟结点为黑兄弟的两个孩子均为黑
   3. 3 兄弟节点为黑兄弟的左孩子为红右孩子为黑
   4. 4 兄弟节点为黑兄弟的右孩子为红
   5. 5 小思考情形2 VS 情形4

本文我引入了一个概念，力图有条理地讲清楚红黑树的增、删、查，同时给出参考的Java实现。若发现bug，或有更好的改进，可联系告知。话不说多，走起！完整的源代码在文末提供了下载链接。

一、 基础知识

红黑树是基于二叉查找树基础上的自平衡二叉树，其目的是在二叉查找树的基础上， 

通过给结点上色，旋转等操作，来维持树的相对平衡，使得树的高度不要太大。 

其5条性质如下：

• 每个结点有一个表示颜色的数据域，非红即黑
• 根结点为黑
• 叶结点（nil结点）为黑
• 若结点为红，其子结点为黑
• 对于任意某个结点，其到叶结点（nil结点）的每条路径包含相同数目的黑结点

关于红黑树的性质背后的基本思想，为什么这5条性质可以确保红黑树的查找、插入、删除操作的在O(log n)时间内完成，可以参考我之前的博文————红黑树性质背后的基本思想

首先给出红黑树结点的类定义。

package com.thomas.datastructure.redblack;

    public class RBTreeNode
    {
        //nil结点的data为这个常量
        public static final int NULL_DATA = Integer.MIN_VALUE;
        public static final RBTreeNode NULL_NODE = new 
                RBTreeNode(NULL_DATA, Color.BLACK, null, null, null);

        public enum Color
        {
            RED("red"),
            BLACK("black");

            private String color;
            private Color(String color)
            {
                this.color = color;
            }

            @Override
            public String toString()
            {
                return color;
            }
        }

        private int data;
        private Color color;
        private RBTreeNode leftChild;
        private RBTreeNode rightChild;
        private RBTreeNode parent;

        public Color getColor() {
            return color;
        }

        public void setColor(Color color) {
            this.color = color;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public RBTreeNode getLeftChild() {
            return leftChild;
        }

        public void setLeftChild(RBTreeNode leftChild) {
            this.leftChild = leftChild;
        }

        public RBTreeNode getRightChild() {
            return rightChild;
        }

        public void setRightChild(RBTreeNode rightChild) {
            this.rightChild = rightChild;
        }

        public RBTreeNode getParent() {
            return parent;
        }

        public void setParent(RBTreeNode parent) {
            this.parent = parent;
        }

        public RBTreeNode(int data, Color color, RBTreeNode leftChild,
                RBTreeNode rightChild, RBTreeNode parent) {
            this.data = data;
            this.color = color;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.parent = parent;
        }

        //创建一个结点，左右孩子均为nil结点
        public RBTreeNode(int data)
        {
            RBTreeNode leftChild = createNullNode();
            RBTreeNode rightChild = createNullNode();

            this.data = data;
            color = Color.RED;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.parent = null;
            this.leftChild.parent = this;
            this.rightChild.parent = this;
        }

        //创建nil结点
        public static RBTreeNode createNullNode()
        {
            return new RBTreeNode(NULL_DATA, Color.BLACK, null, null, null);
        }

        //左旋
        //右孩子的左孩子 -> 新右孩子
        //原右孩子 -> 父结点
        public void leftRotate()
        {
            RBTreeNode originParent = parent;
            RBTreeNode originRight = rightChild;
            rightChild = rightChild.leftChild;
            originRight.leftChild = this;

            if(this == originParent.getLeftChild())
                originParent.setLeftChild(originRight);
            else    originParent.setRightChild(originRight);
            originRight.setParent(originParent);
            parent = originRight;
            rightChild.parent = this;
        }

        //右旋
        //左孩子的右孩子 -> 新左孩子
        //原左孩子 -> 父结点
        public void rightRotate()
        {
            RBTreeNode originParent = parent;
            RBTreeNode originLeft = leftChild;
            leftChild = leftChild.rightChild;
            originLeft.rightChild = this;

            if(this == originParent.getLeftChild())
                originParent.setLeftChild(originLeft);
            else    originParent.setRightChild(originLeft);
            originLeft.setParent(originParent);
            parent = originLeft;
            leftChild.parent = this;
        }

        @Override
        public String toString() {
            return data + " ---> " + color;
        }

        //判断是否为nil结点
        public boolean isNull()
        {
            return data == NULL_DATA;
        }

    }
           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106
• 107
• 108
• 109
• 110
• 111
• 112
• 113
• 114
• 115
• 116
• 117
• 118
• 119
• 120
• 121
• 122
• 123
• 124
• 125
• 126
• 127
• 128
• 129
• 130
• 131
• 132
• 133
• 134
• 135
• 136
• 137
• 138
• 139
• 140
• 141
• 142
• 143
• 144
• 145
• 146
• 147
• 148
• 149
• 150
• 151
• 152
• 153

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106
• 107
• 108
• 109
• 110
• 111
• 112
• 113
• 114
• 115
• 116
• 117
• 118
• 119
• 120
• 121
• 122
• 123
• 124
• 125
• 126
• 127
• 128
• 129
• 130
• 131
• 132
• 133
• 134
• 135
• 136
• 137
• 138
• 139
• 140
• 141
• 142
• 143
• 144
• 145
• 146
• 147
• 148
• 149
• 150
• 151
• 152
• 153

这个类定义中，即使是nil结点，也不会是Java中的null。如果把nil结点，即红黑树中的叶结点，直接用Java中的null来表示，那么在后续红黑树的很多操作中，都要注意很多边界条件，要判断是否为null，否则会抛NullPointerException，十分麻烦。

开始探讨前，我先确立一个名词，在后面会用到。我觉得通过这个名词来理解会较好。 

插入/删除操作的修复过程中，可能会破坏红黑树性质，导致红黑树结构的变化的结点，称之为致变结点。（原谅我词汇缺乏@_@）

另外，还有一个概念是在算法导论中提到的——黑高度。黑高度是指，从某个结点出发，到nil结点的路径中，黑结点的数目。

二、查找

红黑树结点的查找与二叉查找树的查找操作是完成一样的，因为查找并不会导致红黑树结构的变化，自然不会破坏红黑树的性质。

二叉查找树的定义的递归性，决定了查找操作可以通过递归来实现，当然也可以不使用递归而使用普通的循环。查找操作的参考Java实现如下：

• 递归查找

protected RBTreeNode recursiveSearch(RBTreeNode node, int data)
    {
        //子树为空（空结点），即找不到匹配的结点
        //返回parent是为了方便进行插入操作，因为插入一个结点要先search
        if(node.isNull())
            return node.getParent();
        int _data = node.getData();
        if(_data == data)
            return node;
        //左子树或右子树递归查找
        if(data < _data)
            return recursiveSearch(node.getLeftChild(), data);
        return recursiveSearch(node.getRightChild(), data);
    }
           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16

• 非递归查找

protected RBTreeNode normalSearch(RBTreeNode node, int data)
    {
        RBTreeNode parent = RBTreeNode.NULL_NODE;
        while(!node.isNull())
        {
            int _data = node.getData();
            if(_data == data)
                return node;
            parent = node;
            if(data < _data)
                node = node.getLeftChild();
            else
                node = node.getRightChild();
        }
        return parent;
    }
           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18

三、 插入

所有结点被插入到红黑树之前，其颜色初始为红。 

红黑树结点的插入可细分为5种，其实应该是8种。 

我将之分为简单的2种情况，和复杂的3种情况。复杂的3种情况有左3种、右3种，故细分起来为8种。

最简单的两种情况如下（先记住，后面会提到）：

• 原树为空，致变结点为根结点，破坏了红黑树的性质2，直接涂黑即可
• 致变结点的父结点为黑，不会违反任何性质，无须做任何操作

然后是复杂情况。复杂情况的大前提是致变结点的父结点为红，因为父为黑，那就是上面的简单情况2，无须任何操作。 

首先，如果父结点是祖父结点的左孩子，则细分为：

• 叔结点为红
• 叔结点为黑，致变结点是父结点的右孩子
• 叔结点为黑，致变结点是父结点的左孩子

对称过来，如果致变结点的父结点是祖父结点的右孩子，同样分为上述3种情况。

以父结点是祖父结点的左孩子为例，3种情况如下：

3.1 叔结点为红

致变结点为x，违反了性质4，最直觉的解决方式自然是重新上色。因为上色永远是最容易执行的操作。

做法： 

将父结点p与叔结点u涂黑，祖父结点g涂红，则g结点以下的部分遵循红黑树性质，但此时g变红可能使上面的节点违反了性质。故以g为新的致变结点，继续沿上层推进、检查、修复。

3.2 叔结点为黑，致变结点是父结点的右孩子

这种情形是算法导论中所说的zig zag——x与p两个红结点构成一个之字形。需要将之转变成zig zig，即两个红结点成一条直线。

做法： 

以父结点p为轴点，左旋。左旋后，x变成了父结点，而p变成了左孩子，但其实问题还没解决。此时以p结点为新的致变结点。

3.3 叔叔结点为黑，致变结点是父结点的左孩子

做法： 

父节点变黑，祖父变红，以祖父结点为新的致变结点，然后以新的致变结点为轴心右旋。

这三种情况不断交替出现，把导致红黑树性质改变的致变结点不断向上推移，同时不断修复红黑树，直至满足如下条件：

• 致变结点是根——等同于上述简单情况1。只可能违反性质2，直接把根涂黑即可。
• 致变结点的父结点为黑——即上述简单情况2。不会违反任何性质，无需再修复。

以上的3种复杂情况，都是针对致变结点的父结点是祖父结点的左孩子而言的。如果其父结点是祖父结点的右孩子，又会出现对称的3种复杂情况，其解决方法与上述完全对称，把左孩子改成右孩子，右孩子改成左孩子，左旋改右旋，右旋改左旋即可，不再赘述。

Java实现参考代码如下：

public boolean insert(int data)
    {
        RBTreeNode resultTree = search(data);

        //空树
        if(resultTree.isNull())
        {
            RBTreeNode root = new RBTreeNode(data);
            fakeRoot.setLeftChild(root);
            root.setParent(fakeRoot);
            //红黑树中根结点为黑
            root.setColor(Color.BLACK);
            return true;
        }

        //原树中已经有该数据项，不必插入
        int _data = resultTree.getData();
        if(data == _data)    return false;

        //非空树
        RBTreeNode newTree = new RBTreeNode(data);
        if(data < _data)
            resultTree.setLeftChild(newTree);
        else    resultTree.setRightChild(newTree);
        newTree.setParent(resultTree);

        //调整红黑树使之平衡
        insertRebalance(newTree);

        //树结构变化，中序缓存清空
        midOrderVisitList.clear();
        return true;
    }

    private void insertRebalance(RBTreeNode node)
    {
        RBTreeNode parent = node.getParent();
        while(parent != fakeRoot && parent.getColor() == Color.RED)
        {
            RBTreeNode grandpa = parent.getParent();
            RBTreeNode uncle;
            //父结点是祖父结点的左孩子
            if(parent == grandpa.getLeftChild())
            {
                uncle = grandpa.getRightChild();
                //case1——叔结点为红
                if(isRed(uncle))
                {
                    uncle.setColor(Color.BLACK);
                    parent.setColor(Color.BLACK);
                    grandpa.setColor(Color.RED);
                    node = grandpa;
                }
                //case2——叔结点为黑，且当前结点是其父结点的右孩子
                else if(node == parent.getRightChild())
                {
                    node = parent;
                    node.leftRotate();
                }
                //case 3——叔结点为黑，且当前结点是其父结点的左孩子
                else if(node == parent.getLeftChild())
                {
                    parent.setColor(Color.BLACK);
                    grandpa.setColor(Color.RED);
                    node = grandpa;
                    node.rightRotate();
                }
            }
            //父结点是祖父结点的右孩子
            else
            {
                uncle = grandpa.getLeftChild();
                //case1——叔结点为红
                if(isRed(uncle))
                {
                    uncle.setColor(Color.BLACK);
                    parent.setColor(Color.BLACK);
                    grandpa.setColor(Color.RED);
                    node = grandpa;
                }
                //case2——叔结点为黑，且当前结点是其父结点的左孩子
                else if(node == parent.getLeftChild())
                {
                    node = parent;
                    node.rightRotate();
                }
                //case 3——叔结点为黑，且当前结点是其父结点的右孩子
                else if(node == parent.getRightChild())
                {
                    parent.setColor(Color.BLACK);
                    grandpa.setColor(Color.RED);
                    node = grandpa;
                    node.leftRotate();
                }
            }
            parent = node.getParent();
        }
        getRoot().setColor(Color.BLACK);
    }
           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101

由上述代码可看出，修复的过程粗略地分为两种：

• 简单情况——不会执行while循环，O(1)操作后修复
• 复杂情况——3种情况不断转换来转换去，直到变成简单情况。

简单情况就是循环退出的条件。

四、 删除

红黑树的删除比较复杂。首先，明确是什么可能引起红黑树的变化。 

回想二叉查找树的删除，在删除某个结点后，会寻找被删除结点的某个替补/后继，来补上被删除结点原先的位置。 

就是这个替补结点，可能引起红黑树的变化。同样，将之称为致变结点。

红黑树的删除操作在二叉树的基础上，进行修复工作。 

Java代码实现如下：

public boolean delete(int data)
    {
        //空树
        if(isEmpty())    return false;

        RBTreeNode target = search(data);
        //树中不存在该数据，无法删除
        int targetData = target.getData();
        if(targetData != data)    return false;

        final RBTreeNode parent = target.getParent();
        final RBTreeNode left = target.getLeftChild();
        final RBTreeNode right = target.getRightChild();
        //保存用于替代被删除结点的那个结点
        RBTreeNode replacement;
        Color originalColor = target.getColor();

        //右子树空（包含两种情况：1、左右子树均空  2、仅有左子树）
        //只需重接左子树
        if(right.isNull())
        {
            if(target == parent.getLeftChild())
                parent.setLeftChild(left);
            else    parent.setRightChild(left);
            left.setParent(parent);
            replacement = left;
        }
        //左子树空
        //只需重接右子树
        else if(left.isNull())
        {
            if(target == parent.getLeftChild())
                parent.setLeftChild(right);
            else    parent.setRightChild(right);
            right.setParent(parent);
            replacement = right;
        }
        //左右子树均非空
        else
        {
            //找到欲删除结点的左子树的右分支尽头的叶结点
            //以之替换欲删除的结点的位置
            RBTreeNode temp = target.getLeftChild();
            while(!temp.getRightChild().isNull())
                temp = temp.getRightChild();

            //这里用了一个trick，把temp的data赋给target
            //最终不会删除target，而是删除temp结点
            target.setData(temp.getData());

            RBTreeNode tempLeftChild = temp.getLeftChild();
            RBTreeNode tempParent = temp.getParent();
            //temp的父结点仍等于target结点
            //说明循环并没有执行，即target的左子树并没有右分支
            if(tempParent == target)
                tempParent.setLeftChild(tempLeftChild);
            else
                tempParent.setRightChild(tempLeftChild);
            tempLeftChild.setParent(tempParent);

            //用于替补temp位置的，就是tempLeftChild
            replacement = tempLeftChild;
            //因为删除的是temp，所以originColor要修改成temp的颜色
            originalColor = temp.getColor();
        }
        //树结构变化，中序缓存清空
        midOrderVisitList.clear();
        //被删除的结点为黑才可能引起红黑树不平衡
        if(originalColor == Color.BLACK)
            deleteRebalance(replacement);
        return true;
    }
           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73

可看出，在二叉查找树的删除操作上，多了两个额外工作：

• 删除结点之后，记录下被删除结点的颜色，以及替补，即致变节点
• 如果被删除结点为黑，则根据致变节点进行修复工作

第1点中，在记录颜色以及替补时，要小心的是else分支，即被删除结点左右子树均非空的情况。上述注解里我已经写得很清楚了。

左右子树均非空时，先找出要删除的那个结点target，找到target的左子树的右分支尽头的结点temp（也可以找到target的右子树的左分支尽头的结点，随你！！对于二叉查找树不了解的，请先补充二叉查找树的基础知识）。

接下来，直觉思维应该是删除target，想方设法把temp挪到target原先的位置，并调整相关结点的关系。但直觉也告诉我们这个工作很繁琐。所以这里用了一个trick，把temp的data赋给target，相当于此时target就是temp结点了，然后temp已经没用了，安心地去吧。此时一下子转变成删除temp结点，而temp结点是右分支尽头结点，也就是说temp没有右孩子，此时就只需重接左子树，方便了许多。

第2点中，被删除结点如果为红，不会违反红黑树的性质，因为黑高度并不会改变。只有删除了一个黑结点，导致黑高度变化，才需要进行修复。

删除修复分为2种简单情况，与对称的左右分别各4种的复杂情况。

2种简单情况如下（与插入操作类似，简单情况就是循环终止的条件）：

• 致变结点为根——只可能违反性质2，直接将之涂黑即可。
• 致变结点为红——删除了一个黑的，替补的是红，直接把红的涂黑。

接下来，以致变结点是否为其父结点的左孩子，分两大类，每类各4种复杂情况，完全对称。 

注意在复杂情况中，致变结点都是黑的，被删除的那个结点也是黑的。如下：

• 兄弟节点为红
• 兄弟节点为黑，兄弟的两个孩子均为黑
• 兄弟节点为黑，兄弟的左孩子为红，右孩子为黑
• 兄弟节点为黑，兄弟的右孩子为红（左孩子无所谓，可红可黑）

以致变结点为其父结点的左孩子为例（下列各图中，x均指替补结点，即致变结点）

4.1 兄弟结点为红

s若为红，根据红黑树性质，p必为黑。p的左子树被删除了一个黑结点，导致左边的黑高度少1。

做法：反转兄弟结点s与父结点p的颜色，再以p为轴心左旋，更新x的兄弟结点。

目的：使兄弟变黑

情形转移：case 1 —> case 2/3/4

兄弟节点变成了sl，且因为原兄弟结点s为红，则s1必为黑。但此时问题并没有解决，只不过由该情形转换为情形2/3/4/中的某一种。

4.2 兄弟结点为黑，兄弟的两个孩子均为黑

PS：父结点可红可黑（以渐变结点表示）

做法：兄弟s涂红，致变结点向上转移至p

目的：使p的左右黑高度相等，局部修复p子树

情形转移：case 2 —> 所有情形皆有可能（包括两种简单情况在内）

4.3 兄弟节点为黑，兄弟的左孩子为红，右孩子为黑

PS：父结点可红可黑

做法：反转兄弟与兄弟左孩子的颜色，以兄弟结点为轴心右旋。更新x的兄弟结点（此时变成sl）

目的：使x的兄弟结点(此时为sl)的右孩子(原先的s)变为红，即变成情形4

情形转移：case 3 —> case 4

4.4 兄弟节点为黑，兄弟的右孩子为红

PS：父结点可红可黑，sl也可红可黑（以渐变色表示）

做法：交换父结点p与兄弟结点s的颜色，把兄弟的右孩子涂黑，以父结点为轴心左旋

目的：保持父结点(此时为s)的黑高度相等，且不变（最重要的是这一点），修复完成。

情形转移：修复完成

4.5 小思考——情形2 VS 情形4

有童鞋可能会疑惑，情形2局部修复了子树，情形4也是局部修复了子树，那凭什么判定情形4整体也随之修复，但情形2还不一定修复了整体呢？

回头再看一下上面的几个图，就会发现，情形2把兄弟结点涂红，使右子树的黑高度减1，从而使左右子树黑高度相等，以此达到局部修复。然后，致变结点变为p。如果p为根，或p为红，则变成simple1和simple2情形，涂黑p即修复完成。 

但如果p为黑，且不是根结点，即不是simple1/simple2，设p的父结点为g。局部修复使得g到p这一边的路径的黑高度全部减了1，但g到另一棵子树(p的兄弟)的黑高度并没有减少，也就是说，此时对于g来说，仍是不平衡的，所以仍需修复。

对于情形4，可以发现在修复前后，子树的黑高度并没有变化。也就是说，删除结点后，情形4通过上色、旋转等操作，使得黑高度与删除前一样，因此，更高层的子树的黑高度不会变化。同时，局部修复后，新的父结点是s，s与原先p的颜色是一样的，在颜色方面也不会与更高层的结点冲突。因此，对于情形4，只要局部修复了，就代表整体修复了。

删除修复的Java实现参考如下：

public void deleteRebalance(RBTreeNode node)
    {
        while(node != getRoot() && node.getColor() == Color.BLACK)
        {
            RBTreeNode parent = node.getParent();
            RBTreeNode brother, brotherLeftChild, brotherRightChild;

            //左孩子
            if(node == parent.getLeftChild())
            {
                brother = parent.getRightChild();
                brotherLeftChild = brother.getLeftChild();
                brotherRightChild = brother.getRightChild();
                //case 1——兄弟节点为红
                //则反转兄弟结点与父结点的颜色
                //以父结点为轴心左旋
                //更新兄弟结点为原父结点在左旋后的新右孩子
                //因为这个新的右孩子是原兄弟结点的孩子
                //而原兄弟结点为红，其孩子必为黑
                //因此case 1最终会转换成case 2/3/4中的某一种
                if(isRed(brother))
                {
                    brother.setColor(Color.BLACK);
                    parent.setColor(Color.RED);
                    parent.leftRotate();
                    brother = parent.getRightChild();
                }
                //case 2——兄弟为黑，且兄弟的两个孩子为黑
                //兄弟变红，欲修复结点上移一层至父结点
                //只有case 2会导致修复点上移
                //上移后的情形不确定，可能是case 1/2/3/4，也可能修复完成
                //修复完成的情况有两种：
                //1、上移后的结点为红，此时跳出循环，并将node置黑
                //2、上移后到达根结点，同样跳出循环，并将node置黑
                else if(!isRed(brotherLeftChild) && !isRed(brotherRightChild))
                {
                    brother.setColor(Color.RED);
                    node = parent;
                }
                //case 3——兄弟为黑，且兄弟的左孩子为红, 右孩子为黑
                //交换兄弟和其左孩子的颜色
                //再以兄弟为轴点右旋
                //更新兄弟结点为原父结点在右旋后的新右孩子
                //右旋后，变成第4种情况
                else if(!isRed(brotherRightChild))
                {
                    brother.setColor(Color.RED);
                    brotherLeftChild.setColor(Color.BLACK);
                    brother.rightRotate();
                    brother = parent.getRightChild();
                }
                //case 4——兄弟为黑，且兄弟的右孩子为红（左孩子红或黑）
                //兄弟结点的颜色改成父结点颜色
                //随后父结点与兄弟的右孩子都涂成黑
                //以父结点为轴心左旋，此时修复完成
                else if(isRed(brotherRightChild))
                {
                    brother.setColor(parent.getColor());
                    parent.setColor(Color.BLACK);
                    brotherRightChild.setColor(Color.BLACK);
                    parent.leftRotate();
                    node = getRoot();//修复完成，结束循环
                }
            }
            //右孩子
            else
            {
                brother = parent.getLeftChild();
                brotherLeftChild = brother.getLeftChild();
                brotherRightChild = brother.getRightChild();
                //case 1——兄弟节点为红
                if(isRed(brother))
                {
                    brother.setColor(Color.BLACK);
                    parent.setColor(Color.RED);
                    parent.rightRotate();
                    brother = parent.getLeftChild();
                }
                //case 2——兄弟为黑，且兄弟的两个孩子为黑
                else if(!isRed(brotherLeftChild) && !isRed(brotherRightChild))
                {
                    brother.setColor(Color.RED);
                    node = parent;
                }
                //case 3——兄弟为黑，且兄弟的右孩子为红, 左孩子为黑
                else if(!isRed(brotherLeftChild))
                {
                    brother.setColor(Color.RED);
                    brotherRightChild.setColor(Color.RED);
                    brother.rightRotate();
                    brother = parent.getLeftChild();
                }
                //case 4——兄弟为黑，且兄弟的左孩子为红（右孩子红或黑）
                else if(isRed(brotherLeftChild))
                {
                    brother.setColor(parent.getColor());
                    parent.setColor(Color.BLACK);
                    brotherLeftChild.setColor(Color.BLACK);
                    parent.rightRotate();
                    node = getRoot();//修复完成，结束循环
                }
            }
        }
        node.setColor(Color.BLACK);
    }
           

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101
• 102
• 103
• 104
• 105
• 106

删除修复小各情形的转换：

• 1 —> 2 / 3 / 4
• 2 —> 1 / 2 / 3 / 4 / simple1 / simple2
• 3 —> 4
• 4 —> done

也就是说，可以完成修复的是情形2及情形4。其中情形4不会转换成简单情况，情况2可能转换成简单情况（只是可能）。 

这里，复杂情况与简单情况的转换与插入操作中有很大的不同。

java代码地址（maven工程）：http://download.csdn.net/detail/a925907195/9703288