上周，我們初步介紹了紅黑樹存在的意義，以及紅黑樹的插入操作，沒看過的小夥伴可以點選下面連結：
漫畫：什麼是紅黑樹？
今天，我們來繼續介紹紅黑樹的删除操作，以及紅黑樹和其他平衡二叉樹的比較。
二叉查找樹是如何進行删除操作的呢？可以分成三種情況。
情況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的鏡像：
再經過右旋、變色，子樹最終成為了下面的樣子：
這樣一來，整顆二叉樹又重新符合了紅黑樹的規則。