紅黑樹(一)之 原理和算法詳細介紹

紅黑樹(一)之 原理和算法詳細介紹

 原文位址：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