前段時間，程序員小灰發布了紅黑樹相關的文章，分成上下篇來講解。

這一次，小灰把兩篇文章做了整合，并且修正了紅黑樹刪除部分的圖片錯誤，感謝大家的指正。

—————? 第二天? —————

————————————

二叉查找樹（BST）具備什么特性呢？

1.左子樹上所有結點的值均小于或等于它的根結點的值。

2.右子樹上所有結點的值均大于或等于它的根結點的值。

3.左、右子樹也分別為二叉排序樹。

下圖中這棵樹，就是一顆典型的二叉查找樹：

1.查看根結點9：

2.根據二叉查找樹左子樹小、右子樹大的特性，10 > 9，因此值為10的結點只可能在根結點的右子樹當中，我們查看右孩子結點13：

3.由于10 < 13，因此查看左孩子11：

4.由于10 < 11，因此查看左孩子10，發現10正是要查找的結點：

假設初始的二叉查找樹只有三個結點，根結點值為9，左孩子值為8，右孩子值為12：

接下來我們依次插入如下五個結點：7,6,5,4,3。依照二叉查找樹的特性，結果會變成什么樣呢？

1.結點是紅色或黑色。

2.根結點是黑色。

3.每個葉子結點都是黑色的空結點（NIL結點）。

4 每個紅色結點的兩個子結點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色結點)

5.從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。

下圖中這棵樹，就是一顆典型的紅黑樹：

什么情況下會破壞紅黑樹的規則，什么情況下不會破壞規則呢？我們舉兩個簡單的例子：

1.向原紅黑樹插入值為14的新結點：

由于父結點15是黑色結點，因此這種情況并不會破壞紅黑樹的規則，無需做任何調整。

2.向原紅黑樹插入值為21的新結點：

由于父結點22是紅色結點，因此這種情況打破了紅黑樹的規則4（每個紅色結點的兩個子結點都是黑色），必須進行調整，使之重新符合紅黑樹的規則。

變色：

為了重新符合紅黑樹的規則，嘗試把紅色結點變為黑色，或者把黑色結點變為紅色。

下圖所表示的是紅黑樹的一部分（子樹），新插入的結點Y是紅色結點，它的父親結點X也是紅色的，不符合規則4，因此我們可以把結點X從紅色變成黑色：

但是，僅僅把一個結點變色，會導致相關路徑憑空多出一個黑色結點，這樣就打破了規則5。因此，我們需要對其他結點做進一步的調整，后文會詳細說明。

左旋轉：

逆時針旋轉紅黑樹的兩個結點，使得父結點被自己的右孩子取代，而自己成為自己的左孩子。說起來很怪異，大家看下圖：

圖中，身為右孩子的Y取代了X的位置，而X變成了自己的左孩子。此為左旋轉。

右旋轉：

順時針旋轉紅黑樹的兩個結點，使得父結點被自己的左孩子取代，而自己成為自己的右孩子。大家看下圖：

圖中，身為左孩子的Y取代了X的位置，而X變成了自己的右孩子。此為右旋轉。

局面1：新結點（A）位于樹根，沒有父結點。

(空心三角形代表結點下面的子樹)

這種局面，直接讓新結點變色為黑色，規則2得到滿足。同時，黑色的根結點使得每條路徑上的黑色結點數目都增加了1，所以并沒有打破規則5。

局面2：新結點（B）的父結點是黑色。

這種局面，新插入的紅色結點B并沒有打破紅黑樹的規則，所以不需要做任何調整。

局面3：新結點（D）的父結點和叔叔結點都是紅色。

這種局面，兩個紅色結點B和D連續，違反了規則4。因此我們先讓結點B變為黑色：

這樣一來，結點B所在路徑憑空多了一個黑色結點，打破了規則5。因此我們讓結點A變為紅色：

這時候，結點A和C又成為了連續的紅色結點，我們再讓結點C變為黑色：

經過上面的調整，這一局部重新符合了紅黑樹的規則。

局面4：新結點（D）的父結點是紅色，叔叔結點是黑色或者沒有叔叔，且新結點是父結點的右孩子，父結點（B）是祖父結點的左孩子。

我們以結點B為軸，做一次左旋轉，使得新結點D成為父結點，原來的父結點B成為D的左孩子：

這樣一來，進入了局面5。

局面5：新結點（D）的父結點是紅色，叔叔結點是黑色或者沒有叔叔，且新結點是父結點的左孩子，父結點（B）是祖父結點的左孩子。

我們以結點A為軸，做一次右旋轉，使得結點B成為祖父結點，結點A成為結點B的右孩子：

接下來，我們讓結點B變為黑色，結點A變為紅色：

經過上面的調整，這一局部重新符合了紅黑樹的規則。

以上就是紅黑樹插入操作所涉及的5種局面。

或許有人會問，如果局面4和局面5當中的父結點B是祖父結點A的右孩子該怎么辦呢？

很簡單，如果局面4中的父結點B是右孩子，則成為了局面5的鏡像，原本的右旋操作改為左旋；如果局面5中的父結點B是右孩子，則成為了局面4的鏡像，原本的左旋操作改為右旋。

給定下面這顆紅黑樹，新插入的結點是21：

顯然，新結點21和它的父結點22是連續的紅色結點，違背了規則4，我們應該如何調整呢？

讓我們回顧一下剛才講的5種局面，當前的情況符合局面3：

“新結點的父結點和叔叔結點都是紅色。”

于是我們經過三次變色，22變為黑色，25變為紅色，27變為黑色：

經過上面的調整，以結點25為根的子樹符合了紅黑樹規則，但結點25和結點17成為了連續的紅色結點，違背規則4。

于是，我們把結點25看做一個新結點，正好符合局面5的鏡像：

“新結點的父結點是紅色，叔叔結點是黑色或者沒有叔叔，且新結點是父結點的右孩子，父結點是祖父結點的右孩子”

于是我們以根結點13為軸進行左旋轉，使得結點17成為了新的根結點：

接下來，讓結點17變為黑色，結點13變為紅色：

如此一來，我們的紅黑樹變得重新符合規則。

二叉查找樹是如何進行刪除操作的呢？可以分成三種情況。

情況1，待刪除的結點沒有子結點：

上圖中，待刪除的結點12是葉子結點，沒有孩子，因此直接刪除即可：

情況2，待刪除的結點有一個孩子：

上圖中，待刪除的結點13只有左孩子，于是我們讓左孩子結點11取代被刪除的結點，結點11以下的結點關系無需變動：

情況3，待刪除的結點有兩個孩子：

上圖中，待刪除的結點5有兩個孩子，這種情況比較復雜。此時，我們需要選擇與待刪除結點最接近的結點來取代它。

上面的例子中，結點3僅小于結點5，結點6僅大于結點5，兩者都是合適的選擇。但習慣上我們選擇僅大于待刪除結點的結點，也就是結點6來取代它。

于是我們復制結點6到原來結點5的位置：

被選中的結點6，僅大于結點5，因此一定沒有左孩子。所以我們按照情況1或情況2的方式，刪除多余的結點6:

紅黑樹的特性（規則）如下：

1.結點是紅色或黑色。

2.根結點是黑色。

3.每個葉子結點都是黑色的空結點（NIL結點）。

4.每個紅色結點的兩個子結點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色結點)

5.從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。

下面我們通過一個例子，來看一看刪除紅黑樹的結點會對規則產生怎樣的影響：

上圖的這顆紅黑樹，待刪除的是黑色結點1，有一個右孩子。根據二叉查找樹的刪除流程，我們讓右孩子結點6直接取代結點1：

顯然，這顆新的二叉樹打破了兩個規則：

規則4. 每個紅色結點的兩個子結點都是黑色。

規則5. 從任一結點到其每個葉子的所有路徑都包含相同數目的黑色結點。

第一步：如果待刪除結點有兩個非空的孩子結點，轉化成待刪除結點只有一個孩子（或沒有孩子）的情況。

上面例子是一顆紅黑樹的局部，標數字的三角形代表任意形態的子樹，假設結點8是待刪除結點。

根據上文講解的二叉查找樹刪除流程，由于結點8有兩個孩子，我們選擇僅大于8的結點10復制到8的位置，結點顏色變成待刪除結點的顏色：

接下來我們需要刪除紅色的結點10：

紅色結點10能成為僅大于8的結點，必定沒有左孩子結點，所以問題轉換成了待刪除結點只有一個右孩子（或沒有孩子）的情況。接下來我們進入第二步。

第二步：根據待刪除結點和其唯一子結點的顏色，分情況處理。

情況1，自身是紅色，子結點是黑色：

這種情況最簡單，按照二叉查找樹的刪除操作，刪除結點1即可：

情況2，自身是黑色，子結點是紅色：

這種情況也很簡單，首先按照二叉查找樹的刪除操作，刪除結點1：

此時，這條路徑憑空減少了一個黑色結點，那么我們把結點2變成黑色即可：

情況3，自身是黑色，子結點也是黑色，或者子結點是空葉子結點：

這種情況最復雜，涉及到很多變化。首先我們還是按照二叉查找樹的刪除操作，刪除結點1：

顯然，這條路徑上減少了一個黑色結點，而且結點2再怎么變色也解決不了。

這時候我們進入第三步，專門解決父子雙黑的情況。

第三步：遇到雙黑結點，在子結點頂替父結點之后，分成6種子情況處理。

子情況1，結點2是紅黑樹的根結點：

此時所有路徑都減少了一個黑色結點，并未打破規則，不需要調整。

子情況2，結點2的父親、兄弟、侄子結點都是黑色：

此時，我們直接把結點2的兄弟結點B改為紅色：

這樣一來，原本結點2所在的路徑少了一個黑色結點，現在結點B所在的路徑也少了一個黑色結點，兩邊“扯平”了。

可是，結點A以下的每一條路徑都減少了一個黑色結點，與結點A之外的其他路徑又造成了新的不平衡啊？

沒關系，我們讓結點A扮演原先結點2的角色，進行遞歸操作，重新判斷各種情況。

子情況3，結點2的兄弟結點是紅色：

首先以結點2的父結點A為軸，進行左旋：

然后結點A變成紅色、結點B變成黑色：

這樣的意義是什么呢？結點2所在的路徑仍然少一個黑色結點呀？

別急，這樣的變化有可能轉換成子情況4、5、6中的任意一種，在子情況4、5、6當中會進一步解決。

子情況4，結點2的父結點是紅色，兄弟和侄子結點是黑色：

這種情況，我們直接讓結點2的父結點A變成黑色，兄弟結點B變成紅色：

這樣一來，結點2的路徑補充了黑色結點，而結點B的路徑并沒有減少黑色結點，重新符合了紅黑樹的規則。

子情況5，結點2的父結點隨意，兄弟結點B是黑色右孩子，左侄子結點是紅色，右侄子結點是黑色：

這種情況下，首先以結點2的兄弟結點B為軸進行右旋：

接下來結點B變為紅色，結點C變為黑色：

這樣的變化轉換成了子情況6。

子情況6，結點2的父結點隨意，兄弟結點B是黑色右孩子，右侄子結點是紅色：

首先以結點2的父結點A為軸左旋：

接下來讓結點A和結點B的顏色交換，并且結點D變為黑色：

這樣是否解決了問題呢？

經過結點2的路徑由（隨意+黑）變成了（隨意+黑+黑），補充了一個黑色結點；

經過結點D的路徑由（隨意+黑+紅）變成了（隨意+黑），黑色結點并沒有減少。

所以，這時候重新符合了紅黑樹的規則。

以上就是紅黑樹刪除的全過程。

給定下面這顆紅黑樹，待刪除的是結點17：

第一步，由于結點17有兩個孩子，子樹當中僅大于17的結點是25，所以把結點25復制到17位置，保持黑色：

接下來，我們需要刪除原本的結點25：

這個情況正好對應于第二步的情況三，即待刪除結點是黑色，子結點是空葉子結點。

于是我們刪除框框中結點25，進入第三步：

此時，框框中的結點雖然是空葉子結點，但仍然可以用于判斷局面，當前局面符合子情況5的鏡像：

于是我們通過左旋和變色，把子樹轉換成情況6的鏡像：

再經過右旋、變色，子樹最終成為了下面的樣子：

這樣一來，整顆二叉樹又重新符合了紅黑樹的規則。

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯AI基礎下載（pdf更新到25集）機器學習的數學基礎專輯本站qq群1003271085，加入微信群請回復“加群”獲取一折本站知識星球優惠券，復制鏈接直接打開：https://t.zsxq.com/yFQV7am喜歡文章，點個在看

總結

以上是生活随笔為你收集整理的【算法漫画】：什么是红黑树？（整合版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。