【超詳細】萬字長文,我畫了近百張圖來理解紅黑樹
來源：掘金（已獲得作者授權，禁止二次轉載）
作者：JasonGaoH
整理：帥地
之前在公司組內分享了紅黑樹的工作原理，今天把它整理下發(fā)出來，希望能對大家有所幫助，對自己也算是一個知識點的總結。
這篇文章算是我寫博客寫公眾號以來畫圖最多的一篇文章了，沒有之一，我希望盡可能多地用圖片來形象地描述紅黑樹的各種操作的前后變換原理，幫助大家來理解紅黑樹的工作原理，下面，多圖預警開始了。
在講紅黑樹之前，我們首先來了解下下面幾個概念：二叉樹，排序二叉樹以及平衡二叉樹。
一、二叉樹
二叉樹指的是每個節(jié)點最多只能有兩個字數(shù)的有序樹。通常左邊的子樹稱為左子樹 ，右邊的子樹稱為右子樹 。這里說的有序樹強調的是二叉樹的左子樹和右子樹的次序不能隨意顛倒。
二叉樹簡單的示意圖如下：
代碼定義：
class?Node?{
????T?data;
????Node?left;
????Node?right;
}
二、排序二叉樹
所謂排序二叉樹，顧名思義，排序二叉樹是有順序的，它是一種特殊結構的二叉樹，我們可以對樹中所有節(jié)點進行排序和檢索。
性質
若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；
若她的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；
具有遞歸性，排序二叉樹的左子樹、右子樹也是排序二叉樹。
排序二叉樹簡單示意圖：
排序二叉樹三、排序二叉樹退化成鏈表
排序二叉樹的左子樹上所有節(jié)點的值小于根節(jié)點的值，右子樹上所有節(jié)點的值大于根節(jié)點的值，當我們插入一組元素正好是有序的時候，這時會讓排序二叉樹退化成鏈表。
正常情況下，排序二叉樹是如下圖這樣的：
但是，當插入的一組元素正好是有序的時候，排序二叉樹就變成了下邊這樣了，就變成了普通的鏈表結構，如下圖所示:
正常情況下的排序二叉樹檢索效率類似于二分查找，二分查找的時間復雜度為 O(log n)，但是如果排序二叉樹退化成鏈表結構，那么檢索效率就變成了線性的 O(n) 的，這樣相對于 O(log n) 來說，檢索效率肯定是要差不少的。
思考，二分查找和正常的排序二叉樹的時間復雜度都是 O(log n)，那么為什么是O(log n) ？
關于 O(log n) 的分析下面這篇文章講解的非常好，感興趣的可以看下這篇文章 二分查找的時間復雜度，文章是拿二分查找來舉例的，二分查找和平衡二叉樹的時間復雜度是一樣的，理解了二分查找的時間復雜度，再來理解平衡二叉樹就不難了，這里就不贅述了。
繼續(xù)回到我們的主題上，為了解決排序二叉樹在特殊情況下會退化成鏈表的問題（鏈表的檢索效率是 O(n) 相對正常二叉樹來說要差不少），所以有人發(fā)明了平衡二叉樹和紅黑樹類似的平衡樹。
四、平衡二叉樹
平衡二叉數(shù)又被稱為 AVL 樹，AVL 樹的名字來源于它的發(fā)明作者 G.M. Adelson-Velsky 和 E.M. Landis，取自兩人名字的首字母。
官方定義：它或者是一顆空樹，或者具有以下性質的排序二叉樹：它的左子樹和右子樹的深度之差(平衡因子)的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。
兩個條件：
平衡二叉樹必須是排序二叉樹，也就是說平衡二叉樹他的左子樹所有節(jié)點的值必須小于根節(jié)點的值，它的右子樹上所有節(jié)點的值必須大于它的根節(jié)點的值。
左子樹和右子樹的深度之差的絕對值不超過1。
五、紅黑樹
講了這么多概念，接下來主角紅黑樹終于要上場了。
為什么有紅黑樹？
其實紅黑樹和上面的平衡二叉樹類似，本質上都是為了解決排序二叉樹在極端情況下退化成鏈表導致檢索效率大大降低的問題，紅黑樹最早是由 Rudolf Bayer 于 1972 年發(fā)明的。
紅黑樹首先肯定是一個排序二叉樹，它在每個節(jié)點上增加了一個存儲位來表示節(jié)點的顏色，可以是 RED 或 BLACK 。
Java 中實現(xiàn)紅黑樹大概結構圖如下所示：
1、紅黑樹的特性
性質1：每個節(jié)點要么是紅色，要么是黑色。
性質2：根節(jié)點永遠是黑色的。
性質3：所有的葉子節(jié)點都是空節(jié)點（即null），并且是黑色的。
性質4：每個紅色節(jié)點的兩個子節(jié)點都是黑色。（從每個葉子到根的路徑上不會有兩個連續(xù)的紅色節(jié)點。）
性質5：從任一節(jié)點到其子樹中每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點。
針對上面的 5 種性質，我們簡單理解下，對于性質 1 和性質 2 ，相當于是對紅黑樹每個節(jié)點的約束，根節(jié)點是黑色，其他的節(jié)點要么是紅色，要么是黑色。
對于性質 3 中指定紅黑樹的每個葉子節(jié)點都是空節(jié)點，而且葉子節(jié)點都是黑色，但 Java 實現(xiàn)的紅黑樹會使用 null 來代表空節(jié)點，因此我們在遍歷 Java里的紅黑樹的時候會看不到葉子節(jié)點，而看到的是每個葉子節(jié)點都是紅色的，這一點需要注意。
對于性質 5，這里我們需要注意的是，這里的描述是從任一節(jié)點，從任一節(jié)點到它的子樹的每個葉子節(jié)點黑色節(jié)點的數(shù)量都是相同的，這個數(shù)量被稱為這個節(jié)點的黑高。
如果我們從根節(jié)點出發(fā)到每個葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點，這個黑色節(jié)點的數(shù)量被稱為樹的黑色高度。樹的黑色高度和節(jié)點的黑色高度是不一樣的，這里要注意區(qū)分。
其實到這里有人可能會問了，紅黑樹的性質說了一大堆，那是不是說只要保證紅黑樹的節(jié)點是紅黑交替就能保證樹是平衡的呢？
其實不是這樣的，我們可以看來看下面這張圖：
左邊的子樹都是黑色節(jié)點，但是這個紅黑樹依然是平衡的，5 條性質它都滿足。
這個樹的黑色高度為 3，從根節(jié)點到葉子節(jié)點的最短路徑長度是 2，該路徑上全是黑色節(jié)點，包括葉子節(jié)點，從根節(jié)點到葉子節(jié)點最長路徑為 4，每個黑色節(jié)點之間會插入紅色節(jié)點。
通過上面的性質 4 和性質 5，其實上保證了沒有任何一條路徑會比其他路徑長出兩倍，所以這樣的紅黑樹是平衡的。
其實這算是一個推論，紅黑樹在最差情況下，最長的路徑都不會比最短的路徑長出兩倍。其實紅黑樹并不是真正的平衡二叉樹，它只能保證大致是平衡的，因為紅黑樹的高度不會無限增高，在實際應用用，紅黑樹的統(tǒng)計性能要高于平衡二叉樹，但極端性能略差。
2、紅黑樹的插入
想要徹底理解紅黑樹，除了上面說到的理解紅黑樹的性質以外，就是理解紅黑樹的插入操作了。
紅黑樹的插入和普通排序二叉樹的插入基本一致，排序二叉樹的要求是左子樹上的所有節(jié)點都要比根節(jié)點小，右子樹上的所有節(jié)點都要比跟節(jié)點大，當插入一個新的節(jié)點的時候，首先要找到當前要插入的節(jié)點適合放在排序二叉樹哪個位置，然后插入當前節(jié)點即可。紅黑樹和排序二叉樹不同的是，紅黑樹需要在插入節(jié)點調整樹的結構來讓樹保持平衡。
一般情況下，紅黑樹中新插入的節(jié)點都是紅色的，那么，為什么說新加入到紅黑樹中的節(jié)點要是紅色的呢？
這個問題可以這樣理解，我們從性質5中知道，當前紅黑樹中從根節(jié)點到每個葉子節(jié)點的黑色節(jié)點數(shù)量是一樣的，此時假如新的黑色節(jié)點的話，必然破壞規(guī)則，但加入紅色節(jié)點卻不一定，除非其父節(jié)點就是紅色節(jié)點，因此加入紅色節(jié)點，破壞規(guī)則的可能性小一些。
接下來我們重點來講紅黑樹插入新節(jié)點后是如何保持平衡的。
給定下面這樣一顆紅黑樹：
當我們插入值為66的節(jié)點的時候，示意圖如下：
很明顯，這個時候結構依然遵循著上述5大特性，無需啟動自動平衡機制調整節(jié)點平衡狀態(tài)。
如果再向里面插入值為51的節(jié)點呢，這個時候紅黑樹變成了這樣。
這樣的結構實際上是不滿足性質4的，紅色兩個子節(jié)點必須是黑色的，而這里49這個紅色節(jié)點現(xiàn)在有個51的紅色節(jié)點與其相連。
這個時候我們需要調整這個樹的結構來保證紅黑樹的平衡。
首先嘗試將49這個節(jié)點設置為黑色，如下示意圖。
這個時候我們發(fā)現(xiàn)黑高是不對的，其中 60-56-45-49-51-null 這條路徑有 4 個黑節(jié)點，其他路徑的黑色節(jié)點是 3 個。
接著調整紅黑樹，我們再次嘗試把45這個節(jié)點設置為紅色的，如下圖所示：
這個時候我們發(fā)現(xiàn)問題又來了，56-45-43 都是紅色節(jié)點的，出現(xiàn)了紅色節(jié)點相連的問題。
于是我們需要再把 56 和 43 設置為黑色的，如下圖所示。
于是我們把 68 這個紅色節(jié)點設置為黑色的。
對于這種紅黑樹插入節(jié)點的情況下，我們可以只需要通過變色就可以保持樹的平衡了。但是并不是每次都是這么幸運的，當變色行不通的時候，我們需要考慮另一個手段就是旋轉了。
例如下面這種情況，同樣還是拿這顆紅黑樹舉例。
現(xiàn)在這顆紅黑樹，我們現(xiàn)在插入節(jié)點65。
我們嘗試把 66 這個節(jié)點設置為黑色，如下圖所示。
這樣操作之后黑高又出現(xiàn)不一致的情況了，60-68-64-null 有 3 個黑色節(jié)點，而60-68-64-66-null 這條路徑有 4 個黑色節(jié)點，這樣的結構是不平衡的。
或者我們把 68 設置為黑色，把 64 設置為紅色，如下圖所示：
但是，同樣的問題，上面這顆紅黑樹的黑色高度還是不一致，60-68-64-null 和 60-68-64-66-null 這兩條路徑黑色高度還是不一致。
這種情況如果只通過變色的情況是不能保持紅黑樹的平衡的。
3、紅黑樹的旋轉
接下來我們講講紅黑樹的旋轉，旋轉分為左旋和右旋。
（1）、左旋
文字描述：逆時針旋轉兩個節(jié)點，讓一個節(jié)點被其右子節(jié)點取代，而該節(jié)點成為右子節(jié)點的左子節(jié)點。
文字描述太抽象，接下來看下圖片展示。
首先斷開節(jié)點PL與右子節(jié)點G的關系，同時將其右子節(jié)點的引用指向節(jié)點C2；然后斷開節(jié)點G與左子節(jié)點C2的關系，同時將G的左子節(jié)點的應用指向節(jié)點PL。
接下來再放下 gif 圖，希望能幫助大家更好地理解左旋，圖片來自網絡。
（2）右旋
文字描述：順時針旋轉兩個節(jié)點，讓一個節(jié)點被其左子節(jié)點取代，而該節(jié)點成為左子節(jié)點的右子節(jié)點。
右旋的圖片展示：
首先斷開節(jié)點G與左子節(jié)點PL的關系，同時將其左子節(jié)點的引用指向節(jié)點C2；然后斷開節(jié)點PL與右子節(jié)點C2的關系，同時將PL的右子節(jié)點的應用指向節(jié)點G。
右旋的gif展示（圖片來自網絡）:
介紹完了左旋和右旋基本操作，我們來詳細介紹下紅黑樹的幾種旋轉場景。
左左節(jié)點旋轉（插入節(jié)點的父節(jié)點是左節(jié)點，插入節(jié)點也是左節(jié)點）
如下圖所示的紅黑樹，我們插入節(jié)點是65。
操作步驟如下可以圍繞祖父節(jié)點 69 右旋，再結合變色，步驟如下所示：
左右節(jié)點旋轉（插入節(jié)點的父節(jié)點是左節(jié)點，插入節(jié)點是右節(jié)點）
還是上面這顆紅黑樹，我們再插入節(jié)點 67。
這種情況我們可以這樣操作，先圍繞父節(jié)點 66 左旋，然后再圍繞祖父節(jié)點 69 右旋，最后再將 67 設置為黑色，把 69 設置為紅色，如下圖所示。
右左節(jié)點旋轉（插入節(jié)點的父節(jié)點是右節(jié)點，插入節(jié)點左節(jié)點）
如下圖這種情況，我們要插入節(jié)點68。
這種情況，我們可以先圍繞父節(jié)點 69 右旋，接著再圍繞祖父節(jié)點 66 左旋，最后把 68 節(jié)點設置為黑色，把 66 設置為紅色，我們的具體操作步驟如下所示。
右右節(jié)點旋轉（插入節(jié)點的父節(jié)點是右節(jié)點，插入節(jié)點也是右節(jié)點）
還是來上面的圖來舉例，我們在這顆紅黑樹上插入節(jié)點 70 。
我們可以這樣操作圍繞祖父節(jié)點 66 左旋，再把旋轉后的根節(jié)點 69 設置為黑色，把 66 這個節(jié)點設置為紅色。具體可以參看下圖：
六、紅黑樹的代碼實現(xiàn)以及代碼詳解（Java）
苦逼的碼農注：看不懂代碼的可以看下面的詳解
Java 中的紅黑樹實現(xiàn)類是 TreeMap ，接下來我們嘗試從源碼角度來逐行解釋 TreeMap 這一套機制是如何運作的。
//?TreeMap中使用Entry來描述每個節(jié)點
?static?final?class?Entry<K,V>?implements?Map.Entry<K,V>?{
????????K?key;
????????V?value;
????????Entry?left;
????????Entry?right;
????????Entry?parent;
????????boolean?color?=?BLACK;
????????...
?}
TreeMap 的put方法。
?public?V?put(K?key,?V?value)?{
????????//先以t保存鏈表的root節(jié)點
????????Entry?t?=?root;
????????//如果t=null,表明是一個空鏈表，即該TreeMap里沒有任何Entry作為root
????????if?(t?==?null)?{
????????????compare(key,?key);?//?type?(and?possibly?null)?check
????????????//將新的key-value創(chuàng)建一個Entry，并將該Entry作為root
????????????root?=?new?Entry<>(key,?value,?null);
????????????size?=?1;
????????????//記錄修改次數(shù)加1
????????????modCount++;
????????????return?null;
????????}
????????int?cmp;
????????Entry?parent;
????????//?split?comparator?and?comparable?paths
????????Comparator?super?K>?cpr?=?comparator;
????????//如果比較器cpr不為null，即表明采用定制排序
????????if?(cpr?!=?null)?{
????????????do?{
????????????????//使用parent上次循環(huán)后的t所引用的Entry
????????????????parent?=?t;
?????????????????//將新插入的key和t的key進行比較
????????????????cmp?=?cpr.compare(key,?t.key);
????????????????//如果新插入的key小于t的key，t等于t的左邊節(jié)點
????????????????if?(cmp?0)
????????????????????t?=?t.left;
????????????????//如果新插入的key大于t的key，t等于t的右邊節(jié)點????
????????????????else?if?(cmp?>?0)
????????????????????t?=?t.right;
????????????????else
????????????????//如果兩個key相等，新value覆蓋原有的value，并返回原有的value
????????????????????return?t.setValue(value);
????????????}?while?(t?!=?null);
????????}
????????else?{
????????????if?(key?==?null)
????????????????throw?new?NullPointerException();
????????????@SuppressWarnings("unchecked")
????????????????Comparable?super?K>?k?=?(Comparable?super?K>)?key;
????????????do?{
????????????????parent?=?t;
????????????????cmp?=?k.compareTo(t.key);
????????????????if?(cmp?0)
????????????????????t?=?t.left;
????????????????else?if?(cmp?>?0)
????????????????????t?=?t.right;
????????????????else
????????????????????return?t.setValue(value);
????????????}?while?(t?!=?null);
????????}
????????//將新插入的節(jié)點作為parent節(jié)點的子節(jié)點
????????Entry?e?=?new?Entry<>(key,?value,?parent);
????????//如果新插入key小于parent的key,則e作為parent的左子節(jié)點
????????if?(cmp?0 )
????????????parent.left?=?e;
????????//如果新插入key小于parent的key，則e作為parent的右子節(jié)點
????????else
????????????parent.right?=?e;
????????//修復紅黑樹
????????fixAfterInsertion(e);
????????size++;
????????modCount++;
????????return?null;
????}
//插入節(jié)點后修復紅黑樹
private?void?fixAfterInsertion(Entry?x )?{
????x.color?=?RED;
????//直到x節(jié)點的父節(jié)點不是根，且x的父節(jié)點是紅色
????while?(x?!=?null?&&?x?!=?root?&&?x.parent.color?==?RED)?{
????????//如果x的父節(jié)點是其父節(jié)點的左子節(jié)點
????????if?(parentOf(x)?==?leftOf(parentOf(parentOf(x))))?{
????????????//獲取x的父節(jié)點的兄弟節(jié)點
????????????Entry?y?=?rightOf(parentOf(parentOf(x)));
????????????//如果x的父節(jié)點的兄弟節(jié)點是紅色
????????????if?(colorOf(y)?==?RED)?{?????
????????????????//將x的父節(jié)點設置為黑色
????????????????setColor(parentOf(x),?BLACK);
????????????????//將x的父節(jié)點的兄弟節(jié)點設置為黑色
????????????????setColor(y,?BLACK);
????????????????//將x的父節(jié)點的父節(jié)點設為紅色
????????????????setColor(parentOf(parentOf(x)),?RED);
????????????????x?=?parentOf(parentOf(x));
????????????}
????????????//如果x的父節(jié)點的兄弟節(jié)點是黑色
????????????else?{???
????????????????//TODO?對應情況第二種，左右節(jié)點旋轉
????????????????//如果x是其父節(jié)點的右子節(jié)點
????????????????if?(x?==?rightOf(parentOf(x)))?{
????????????????????//將x的父節(jié)點設為x
????????????????????x?=?parentOf(x);
????????????????????//右旋轉
????????????????????rotateLeft(x);
????????????????}
????????????????//把x的父節(jié)點設置為黑色
????????????????setColor(parentOf(x),?BLACK);
????????????????//把x的父節(jié)點父節(jié)點設為紅色
????????????????setColor(parentOf(parentOf(x)),?RED);
????????????????rotateRight(parentOf(parentOf(x)));
????????????}
????????}
????????//如果x的父節(jié)點是其父節(jié)點的右子節(jié)點
????????else?{
????????????//獲取x的父節(jié)點的兄弟節(jié)點
????????????Entry?y?=?leftOf(parentOf(parentOf(x)));
????????????//只著色的情況對應的是最開始例子，沒有旋轉操作，但是要對應多次變換
????????????//如果x的父節(jié)點的兄弟節(jié)點是紅色??
????????????if?(colorOf(y)?==?RED)?{
????????????????//將x的父節(jié)點設置為黑色
????????????????setColor(parentOf(x),?BLACK);
????????????????//將x的父節(jié)點的兄弟節(jié)點設為黑色
????????????????setColor(y,?BLACK);
????????????????//將X的父節(jié)點的父節(jié)點（G）設置紅色
????????????????setColor(parentOf(parentOf(x)),?RED);
????????????????//將x設為x的父節(jié)點的節(jié)點
????????????????x?=?parentOf(parentOf(x));
????????????}
????????????//如果x的父節(jié)點的兄弟節(jié)點是黑色
????????????else?{
????????????????//如果x是其父節(jié)點的左子節(jié)點
????????????????if?(x?==?leftOf(parentOf(x)))?{
????????????????????//將x的父節(jié)點設為x
????????????????????x?=?parentOf(x);
????????????????????//右旋轉
????????????????????rotateRight(x);
????????????????}
????????????????//將x的父節(jié)點設為黑色
????????????????setColor(parentOf(x),?BLACK);
????????????????//把x的父節(jié)點的父節(jié)點設為紅色
????????????????setColor(parentOf(parentOf(x)),?RED);
????????????????rotateLeft(parentOf(parentOf(x)));
????????????}
????????}
????}
????//將根節(jié)點強制設置為黑色
????root.color?=?BLACK;
}
TreeMap的插入節(jié)點和普通的排序二叉樹沒啥區(qū)別，唯一不同的是，在TreeMap 插入節(jié)點后會調用方法fixAfterInsertion(e)來重新調整紅黑樹的結構來讓紅黑樹保持平衡。
我們重點關注下紅黑樹的fixAfterInsertion(e)方法，接下來我們來分別介紹兩種場景來演示fixAfterInsertion(e)方法的執(zhí)行流程。
1、第一種場景：只需變色即可平衡
同樣是拿這顆紅黑樹舉例，現(xiàn)在我們插入節(jié)點 51。
當我們需要插入節(jié)點51的時候，這個時候TreeMap 的 put 方法執(zhí)行后會得到下面這張圖。
接著調用fixAfterInsertion(e)方法，如下代碼流程所示。
當?shù)谝淮芜M入循環(huán)后，執(zhí)行后會得到下面的紅黑樹結構。
在把 x 重新賦值后，重新進入 while 循環(huán)，此時的 x 節(jié)點為 45 。
執(zhí)行上述流程后，得到下面所示的紅黑樹結構。
這個時候x被重新賦值為60，因為60是根節(jié)點，所以會退出 while 循環(huán)。在退出循序后，會再次把根節(jié)點設置為黑色，得到最終的結構如下圖所示。
最后經過兩次執(zhí)行while循環(huán)后，我們的紅黑樹會調整成現(xiàn)在這樣的結構，這樣的紅黑樹結構是平衡的，所以路徑的黑高一致，并且沒有紅色節(jié)點相連的情況。
2、第二種場景 旋轉搭配變色來保持平衡
接下來我們再來演示第二種場景，需要結合變色和旋轉一起來保持平衡。
給定下面這樣一顆紅黑樹：
現(xiàn)在我們插入節(jié)點66，得到如下樹結構。
同樣地，我們進入fixAfterInsertion(e)方法。
最終我們得到的紅黑樹結構如下圖所示：
調整成這樣的結構我們的紅黑樹又再次保持平衡了。
演示 TreeMap 的流程就拿這兩種場景舉例了，其他的就不一一舉例了。
3、紅黑樹的刪除
因為之前的分享只整理了紅黑樹的插入部分，本來想著紅黑樹的刪除就不整理了，有人跟我反饋說紅黑樹的刪除相對更復雜，于是索性還是把紅黑樹的刪除再整理下。
刪除相對插入來說，的確是要復雜一點，但是復雜的地方是因為在刪除節(jié)點的這個操作情況有很多種，但是插入不一樣，插入節(jié)點的時候實際上這個節(jié)點的位置是確定的，在節(jié)點插入成功后只需要調整紅黑樹的平衡就可以了。
但是刪除不一樣的是，刪除節(jié)點的時候我們不能簡單地把這個節(jié)點設置為null，因為如果這個節(jié)點有子節(jié)點的情況下，不能簡單地把當前刪除的節(jié)點設置為null，這個被刪除的節(jié)點的位置需要有新的節(jié)點來填補。這樣一來，需要分多種情況來處理了。
（1）、刪除節(jié)點是根節(jié)點
直接刪除根節(jié)點即可。
（2）、刪掉節(jié)點的左子節(jié)點和右子節(jié)點都是為空
直接刪除當前節(jié)點即可。
（3）、刪除節(jié)點有一個子節(jié)點不為空
這個時候需要使用子節(jié)點來代替當前需要刪除的節(jié)點，然后再把子節(jié)點刪除即可。
給定下面這棵樹，當我們需要刪除節(jié)點69的時候。
首先用子節(jié)點代替當前待刪除節(jié)點，然后再把子節(jié)點刪除。
最終的紅黑樹結構如下面所示，這個結構的紅黑樹我們是不需要通過變色+旋轉來保持紅黑樹的平衡了，因為將子節(jié)點刪除后樹已經是平衡的了。
還有一種場景是當我們待刪除節(jié)點是黑色的，黑色的節(jié)點被刪除后，樹的黑高就會出現(xiàn)不一致的情況，這個時候就需要重新調整結構。
還是拿上面這顆刪除節(jié)點后的紅黑樹舉例，我們現(xiàn)在需要刪除節(jié)點67。
因為67 這個節(jié)點的兩個子節(jié)點都是null，所以直接刪除,得到如下圖所示結構：
這個時候我們樹的黑高是不一致的，左邊黑高是3，右邊是2，所以我們需要把64節(jié)點設置為紅色來保持平衡。
（4）、刪除節(jié)點兩個子節(jié)點都不為空
刪除節(jié)點兩個子節(jié)點都不為空的情況下，跟上面有一個節(jié)點不為空的情況下也是有點類似，同樣是需要找能替代當前節(jié)點的節(jié)點，找到后，把能替代刪除節(jié)點值復制過來，然后再把替代節(jié)點刪除掉。
先找到替代節(jié)點，也就是前驅節(jié)點或者后繼節(jié)點
然后把前驅節(jié)點或者后繼節(jié)點復制到當前待刪除節(jié)點的位置，然后在刪除前驅節(jié)點或者后繼節(jié)點。
那么什么叫做前驅，什么叫做后繼呢？
前驅是左子樹中最大的節(jié)點，后繼則是右子樹中最小的節(jié)點。
前驅或者后繼都是最接近當前節(jié)點的節(jié)點，當我們需要刪除當前節(jié)點的時候，也就是找到能替代當前節(jié)點的節(jié)點，能夠替代當前節(jié)點肯定是最接近當前節(jié)點。
在當前刪除節(jié)點兩個子節(jié)點不為空的場景下，我們需要再進行細分，主要分為以下三種情況。
第一種，前驅節(jié)點為黑色節(jié)點，同時有一個非空節(jié)點
如下面這樣一棵樹，我們需要刪除節(jié)點64：
首先找到前驅節(jié)點，把前驅節(jié)點復制到當前節(jié)點：
接著刪除前驅節(jié)點。
這個時候63和60這個節(jié)點都是紅色的，我們嘗試把60這個節(jié)點設置為紅色即可使整個紅黑樹達到平衡。
第二種，前驅節(jié)點為黑色節(jié)點，同時子節(jié)點都為空
前驅節(jié)點是黑色的，子節(jié)點都為空，這個時候操作步驟與上面基本類似。
如下操作步驟：
因為要刪除節(jié)點64，接著找到前驅節(jié)點63，把63節(jié)點復制到當前位置，然后將前驅節(jié)點63刪除掉，變色后出現(xiàn)黑高不一致的情況下，最后把63節(jié)點設置為黑色，把65節(jié)點設置為紅色，這樣就能保證紅黑樹的平衡。
第三種，前驅節(jié)點為紅色節(jié)點，同時子節(jié)點都為空
給定下面這顆紅黑樹，我們需要刪除節(jié)點64的時候。
同樣地，我們找到64的前驅節(jié)點63，接著把63賦值到64這個位置。
然后刪除前驅節(jié)點。
刪除節(jié)點后不需要變色也不需要旋轉即可保持樹的平衡。
終于把紅黑樹的基本原理部分寫完了，用了很多示意圖，這篇文章是在之前分享的 ppt 上再整理出來，我覺得自己應該算是把基本操作講明白了，整理這篇文章前前后后用了近一周左右，因為平時上班，基本上只有周末有時間才有時間整理，如有問題請留言討論。
如果您覺得寫得還可以，請您幫忙點個好看，您的點贊真的是對我最大的支持，也是我能繼續(xù)寫下去的動力，感謝。
文章中很多參考了下面文章的一些示意圖，非常感謝以下文章。
1、What does the time complexity O(log n) actually mean?：https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf
2、Java提高篇--TreeMap：https://blog.csdn.net/chenssy/article/details/26668941
推薦閱讀
全部文章詳細分類與整理（算法+數(shù)據結構+計算機基礎）