70 張圖帶你徹底掌握這個數(shù)據(jù)結(jié)構(gòu)！！

前言

紅黑樹是工程中一種非常重要的數(shù)據(jù)結(jié)構(gòu)，大家熟悉的 HashMap 在 Java 8 就引入了紅黑樹的數(shù)據(jù)結(jié)構(gòu)，不過實話實說，紅黑樹確實不容易掌握，左旋，右旋等概念讓人頭發(fā)發(fā)麻，本文用圖文并茂的形式以期讓讀者徹底掌握紅黑樹，希望大家看了有收獲，這篇文章肝了十多天，非常不易，希望大家不要白嫖，三連走起，多謝支持!

開篇我們先來聊一聊和樹相關(guān)的一些概念，來一步一步引入為什么要使用紅黑樹。這樣能夠讓大家知其然而知其所以然，最后你會發(fā)現(xiàn)，紅黑樹的處理情況也就那幾種，甚至可以說就固定那幾種情況，多看看我的分析就能拿下了。話不多話，我們先從樹的概念開始。

友情提示：本文篇幅比較長，但是總體而言簡單易懂，還請各位坐穩(wěn)。

1、樹

樹的定義如下

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限節(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。它具有以下的特點：

1.每個節(jié)點有零個或多個子節(jié)點；

2.沒有父節(jié)點的節(jié)點稱為根節(jié)點；

3.每一個非根節(jié)點有且只有一個父節(jié)點；

4.除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹

樹的一些重要的名詞解釋

1.?高度：當(dāng)前節(jié)點到葉子節(jié)點的最長路徑?
2.?深度：根節(jié)點到當(dāng)前節(jié)點經(jīng)過的邊數(shù)?
3.?層數(shù)：節(jié)點的深度+1 樹的高度：即根節(jié)點的高度（就是根節(jié)點到葉子節(jié)點的最長路徑）?
4.?父節(jié)點：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點?
5.?子節(jié)點：一個節(jié)點包含的子樹節(jié)點?
6.?兄弟節(jié)點：具有相同父節(jié)點的節(jié)點稱為兄弟節(jié)點?
7.?葉節(jié)點：沒有子節(jié)點的節(jié)點（也叫頁子節(jié)點）?以上是關(guān)于樹的一些常見的概念

（其他的一些概念不是很重要就不一一列出來了。）

來結(jié)合一張圖來更直觀的理解下上面的各個名詞的好含義

2、二叉樹

二叉樹的定義:樹的每個節(jié)點最多有兩個子節(jié)點

雖然 H 節(jié)點只有一個子節(jié)點，但是它也是一個二叉樹，因為滿足最多只有個兩個子節(jié)點

3、二叉搜索樹

二叉搜索樹其實就是二叉樹，只不過又有一些額外的條件限制。其額外條件如下：

① 若它的左子樹不為空，那么左子樹上面的所有節(jié)點的值均小于它的根節(jié)點的值

② 若它的右子樹不為空，那么右子樹上面的所有的節(jié)點的值均大于它的根節(jié)點的值

③ 它的左右的樹葉分別為二叉排序樹

其中重點強調(diào)下二叉搜索樹的中序遍歷（因為這是最常見的）。中序遍歷的規(guī)則是：先遍歷左子樹，再遍歷根節(jié)點，然后遍歷右子樹

例如下面這個二叉搜索樹的遍歷的結(jié)果：D-H-B-E-A-F-C-G

如果從A的上面使用一個光源往下照，那么整個樹的節(jié)點在地面上的投影其實就是中序遍歷的結(jié)果。二叉搜索樹的時間復(fù)雜度是 O（logn）

下面我們再來一起看下二叉搜索樹的查找某個節(jié)點的算法（詳細(xì)步驟全部使用注釋寫清楚了，因為紅黑樹就是基于二分查找樹的，所以這里就多提一筆）

public?class?BinaryTreeDemo?{
????public?static?void?main(String[]?args)?{
????????//前提這必須是一個有序的數(shù)組，否則是無法使用二分查找的
????????Integer[]?searchArr?=?{1,?2,?3,?5,?6,?7,?9,?11,?23,?45,?67,?89};
????????//假設(shè)要查找?3?這個數(shù)據(jù)
????????Integer?index?=?binarySearchTree(searchArr,?3);
????????System.out.println("index?=?"?+?index);
????}

????private?static?Integer?binarySearchTree(Integer[]?searchArr,?int?searchData)?{
????????//定義數(shù)組的低位的索引
????????int?lowBit?=?0;
????????//定義數(shù)組的高位的索引
????????int?heightBit?=?searchArr.length?-?1;
????????//(heightBit?-?lowBit)?/?2?得到的是兩個位置的中間位置，再加上?low?就是實際的?heightBit?和?lowBit?的中間位置
????????//不懂的不用太糾結(jié)，重點是紅黑樹
????????while?(lowBit?<=?heightBit)?{
????????????//這里為什么這么定義中間位置
????????????//因為?（heightBit?-?lowBit）/2?結(jié)果是兩者的相對中間點，再加上lowBit?其實就是高位和低位的中間位置
????????????//這里如果實在想不明白就去畫畫圖，記住，不能寫成（heightBit?+?lowBit）/2
????????????int?midBit?=?lowBit?+?(heightBit?-?lowBit)?/?2;
????????????//開始二分查找
????????????//如果被查找的數(shù)據(jù)組的中間位置的值?小于?要搜索的值
????????????//說明?searchData?在中間位置的右邊
????????????if?(searchArr[midBit]?????????????????//這里為什么要?+ 1 ？
????????????????//?因為midBit?位置已經(jīng)確定比?searchData?小了，所以需要從midBit的下一個索引位置開始繼續(xù)找
????????????????//?也就是說?將?midBit?及?midBit?的左邊的部分砍掉
????????????????lowBit?=?midBit?+?1;
????????????}?else?if?(searchArr[midBit]?==?searchData)?{
????????????????return?midBit;
????????????}?else?{
????????????????//這里的作用和?第一個?if中的類似
????????????????//因為要查找的?searchData?
????????????????//也就是說?直接將?midBit?及?midBit?右邊的部分砍掉
????????????????heightBit?=?midBit?-?1;
????????????}
????????}
????????return?null;
????}
}

二分查找樹的最大的缺點是依賴有序數(shù)組，而數(shù)組的缺點就是不能擴(kuò)容，還有就是在添加和刪除元素的時候需要移動數(shù)組，性能不理想。上面我們還說過一個問題，就是二叉樹的特點就是每個節(jié)點的最多只有兩個子節(jié)點，結(jié)合二叉搜索樹的特點就是 左子節(jié)點 < 根節(jié)點 < 右子節(jié)點，那么在極端情況下，可能會出現(xiàn)下面這樣的情況

在這種極端的情況下，可能會出現(xiàn)這種線性樹結(jié)構(gòu)，基本退化成鏈表了，那時間復(fù)雜度就變成了 O(n)。這個時間復(fù)雜度也太不穩(wěn)定了，這種不穩(wěn)定的東西在系統(tǒng)中就是定時炸彈。所以二叉搜索樹被進(jìn)一步的優(yōu)化成 AVL 樹

4、AVL 樹

#?AVL?樹的定義（AVL?是兩個人的名字的簡稱，是這兩個人發(fā)明的）
具有二叉搜索樹的全部特點，并且沒有節(jié)點的左右節(jié)點的高度相差至多等于1（高度相差不能大于1這個就嚴(yán)格限制死了?AVL?樹，導(dǎo)致其實際應(yīng)用場景并不是很多）

AVL 樹也叫平衡二叉樹，他的時間復(fù)雜度是 O(logn)

AVL 的左右樹的高度差也叫平衡因子（平衡因子就是從某個節(jié)點開始，他的左右子樹的節(jié)點數(shù)差），即平衡因子不大于 1。

但實際情況是根本不可能插入的數(shù)據(jù)這么巧的剛好一大一小的在左右樹插入，所以 AVL 樹在插入數(shù)據(jù)的時候會不斷地調(diào)整，因為高度相差不大于 1 真的太嚴(yán)格了。那這樣在頻繁插入的時候必然需要一直調(diào)整樹的結(jié)構(gòu)，讓其保持平衡。如下圖（假設(shè)現(xiàn)在插入的不平衡的節(jié)點在左側(cè)）

此時這種情況稱之為左失衡，所以很顯然需要進(jìn)行右旋轉(zhuǎn)（具體旋轉(zhuǎn)會在紅黑樹中在介紹），右失衡的情況和此類似?？上攵粩嗟卣{(diào)整會導(dǎo)致性能低下。

說到這里，是不是機智的你也發(fā)現(xiàn)了樹為啥會一步一步的進(jìn)化演變，主要還是因為已有的功能無法滿足新的需求，才會開始尋找新的解決辦法。這就像架構(gòu)一樣，一開始是單體應(yīng)用，隨著業(yè)務(wù)量的提升，逐漸演變?yōu)榱宋⒎?wù)架構(gòu)。結(jié)合當(dāng)前業(yè)務(wù)不斷優(yōu)化現(xiàn)有技術(shù)棧，才是架構(gòu)的本質(zhì)

5、2-3樹

有的小伙伴可能已經(jīng)不耐煩了，怎么說好的紅黑樹，說半天還沒到紅黑樹，難不成你是在摸魚？

事實上如果上來就是紅黑樹我估計我自己看的都發(fā)懵，之所以一個又一個的鋪墊，主要目的還是想讓小伙伴們能有一次性拿下紅黑樹（手動滑稽）。好了，我們來繼續(xù)說 2-3 樹，2-3 樹的特點是什么？它能夠維持絕對的平衡，下面我們來演示下 2-3 樹添加節(jié)點的過程

#?2-3?樹的特點
1.?2-3樹?是平衡樹?
2.?2?叉節(jié)點，有兩個分樹，節(jié)點中有一個元素，左樹元素更小，右樹元素節(jié)點更大?
3.?3?叉節(jié)點，有三個子樹，節(jié)點中有兩個元素，左樹元素更小，右樹元素更大，中間樹介于兩個父元素之間

① 假設(shè)現(xiàn)在有一個節(jié)點 40，那啥也別說了，第一個節(jié)點啥都不做，老實呆著就行；

② 下一個節(jié)點 35 ，先從根節(jié)點開始，發(fā)現(xiàn) 40 > 35 ，此時理論上 35 應(yīng)該添加到 40 的左子樹上，但是對于 2-3 樹，并不是你想的那樣子，記住核心的一句話對于 2-3 樹的添加，永遠(yuǎn)不會添加到一個空的節(jié)點去，只會跟最后找到的葉子節(jié)點做融合（不明白也沒事，先把這個過程看完），那添加到哪里？實際上他們會這樣存儲：

現(xiàn)在這個變成了一個 3 節(jié)點。此時這顆樹依舊是平衡的。

#?怎么理解這個?3?節(jié)點
因為接下來的數(shù)據(jù)可能是小于 35 ，可能是在 35 到 40?之間，也可能是大于 40?的，所以這個節(jié)點能放三個節(jié)點，這就是 3 節(jié)點的含義

③ 下一個節(jié)點是 12 ，按照我們上面解釋的 3 節(jié)點的含義，那既然 12 < 35 那是不是就是這樣子的呢？

很顯然不是，不要忘記了上面的那句核心的話（對于 2-3 樹的添加，永遠(yuǎn)不會添加到一個空的節(jié)點去，只會跟最后找到的葉子節(jié)點做融合），因為此時 35 的左子節(jié)點是空，所以 12 是不可能添加進(jìn)去的，實際上他是這么添加的

那這個時候按照 3 節(jié)點的定義，那這個豈不是 4 節(jié)點了？其實這個時候答案已經(jīng)很明顯了，就是此時該樹會分裂成一個正常的二叉樹，也就是這樣子的，這棵樹依舊是覺得平衡

④ 繼續(xù)添加節(jié)點 18 ，自己能腦補下該怎么添加嗎？這時候就很簡單了，18 < 35 ，就添加到左子節(jié)點，此時左子節(jié)點不為空，那么就可以繼續(xù)添加，而 18 > 12，理論上應(yīng)該是添加到 12 的右子節(jié)點，但是由于對于 2-3 樹的添加，永遠(yuǎn)不會添加到一個空的節(jié)點去，只會跟最后找到的葉子節(jié)點做融合。這個的理論指導(dǎo)，又因為此時 12 是一個 2 節(jié)點，所以即可進(jìn)行融合，實際上它是這樣子的

⑤ 繼續(xù)添加 10 ，10 < 35， 到左子樹查找，10 < 12 但是12 的左子樹為空，所以 10 先臨時和 12 做一個融合

但是這個時候 12 節(jié)點已經(jīng)變成了 4 節(jié)點，所以需要拆解，理論上是這樣拆解的

但是這樣的話 2-3 樹就不是一顆絕對平衡的樹了，顯然不能這樣拆解，或者是需要做其他操作來保持其絕對平衡。此時我們看上面的圖，12 節(jié)點實際上是 10 和 18 的根節(jié)點了，接著往上查找，12 的父節(jié)點是 35 而其是一個 2 節(jié)點，所以 12 就順理成章的和 35 融合起來，也就是下面這樣子的

此時它又是一顆絕對平衡的 2-3 樹了

⑥ 繼續(xù)添加 11 ，那就很簡單了，就不再一步一步解釋了，添加后應(yīng)該是這樣子的

⑦ 別急，還沒完，再來一個節(jié)點 8，那肯定就先是這樣子的（一步一步畫其轉(zhuǎn)變的過程）

然后分裂，成這樣子

但是很顯然，此時的樹已經(jīng)失去平衡了，那就繼續(xù)轉(zhuǎn)換， 10 ?節(jié)點向上和根節(jié)點融合，但是此時 10 的父節(jié)點已經(jīng)是一個 3 節(jié)點的樹了，先融合進(jìn)去再說

此時是 4 節(jié)點，已經(jīng)不是 2-3 樹了，所以下一步是這樣演變的，直接將中間的（為什么是中間的？因為這個依舊符合二叉搜索樹的特性，也就是左小右大）12 節(jié)點向上分裂，也就是最終是這樣子的

到此，我忍不住喊了一聲

2-3 樹的時間復(fù)雜度是Ologn，實際上紅黑樹就是由 2-3 樹推導(dǎo)出來的，2-3 樹和紅黑樹的關(guān)系是：2-3 樹的插入和刪除過程也可以對應(yīng)到紅黑樹的旋轉(zhuǎn)與顏色變換過程（至于紅黑樹的旋轉(zhuǎn)和變色在紅黑樹中會重點討論）。

那既然 2-3 樹這么厲害，干嘛還要費那么大勁研究紅黑樹呢？那是因為對于 2-3 樹我們需要維護(hù)兩種不同類型的節(jié)點，查找和插入操作的實現(xiàn)需要大量的代碼，而且它們所產(chǎn)生的額外開銷可能會使算法比標(biāo)準(zhǔn)的二叉查找樹更慢。所以這才有個紅黑樹。

6、紅黑樹

上面為什么不常見的 2-3 樹說了那么多？因為 2-3樹的插入和刪除過程也可以對應(yīng)到紅黑樹的旋轉(zhuǎn)與顏色變換過程。下面我們先來了解下什么叫紅黑樹

#?紅黑樹的定義（特性）
1.?根節(jié)點是【黑色】
2.?每個節(jié)點要么是【黑色】要么是【紅色】
3.?每個【紅色】節(jié)點的兩個子節(jié)點一定都是【黑色】
4.?每個葉子節(jié)點（NIL）都是【黑色】
5.?任意一個節(jié)點的路徑到葉子節(jié)點所包含的【黑色】節(jié)點的數(shù)量是相同的---這個也稱之為【黑色完美平衡】
6.?新插入的節(jié)點必須是【紅色】->為什么？如果新插入的節(jié)點是【黑色】，那不管是在插入到那里，一定會破壞黑色完美平衡的，因為任意一個節(jié)點的路徑到葉子節(jié)點的黑色節(jié)點的數(shù)量肯定不一樣了（第 6 點我自己加的，實際特性的定義是前 5 個）

紅黑樹的最大高度是 2logn，這看起來查找的效率并不是 AVL 樹要好，紅黑樹的的添加和刪除元素的時間復(fù)雜度是O(logn)，因為他不會退化成想二叉搜索樹的鏈表的結(jié)構(gòu)

相信看完定義你一定一臉懵逼，別急，一步一步來，首先來畫個圖幫助大家理解

好，看到這里，小伙伴們一定是一頭霧水，光說定義（網(wǎng)上到處都是）其實根本就無法解釋清楚叫紅黑樹。

也就是說紅黑樹是一種平衡的檢索樹，上面的 AVL 樹我們剛剛說了因為需要頻繁的進(jìn)行自平衡，所以在添加和刪除節(jié)點的情況下性能是嚴(yán)重下降的，我們先來看下紅黑樹和 AVL 樹的比較

#?紅黑樹與AVL樹的比較
1.?AVL樹的時間復(fù)雜度優(yōu)于紅黑樹，但是對于現(xiàn)在的計算機，這種差別可以忽略
2.?紅黑樹的插入刪除比AVL樹更便于控制操作。
3.?紅黑樹整體性能略優(yōu)于AVL樹。（紅黑樹旋轉(zhuǎn)情況少于AVL樹）。這點是非常重要的
4.?如果是在查詢很多增刪少的情況下?AVL?樹還是優(yōu)于紅黑樹的，如果增刪比較頻繁，那紅黑樹絕對是完美的一種選擇

那紅黑樹在添加和刪除節(jié)點的時候是靠什么來維持平衡的呢？那就是左旋、右旋加變色

下面分別先來看下左旋、右旋加變色的定義

左旋:以某個節(jié)點作為固定支撐點（圍繞該節(jié)點旋轉(zhuǎn)）,其右子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的父節(jié)點，右子節(jié)點的左子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的右子節(jié)點，左子節(jié)點保持不變

右旋:?以某個節(jié)點作為固定支撐點（圍繞該節(jié)點旋轉(zhuǎn)），其左子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的父節(jié)點，左子節(jié)點的右子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的左子節(jié)點，右子節(jié)點保持不變
?
變色:節(jié)點的顏色由紅色變成黑色，或者是由黑色變成紅色

下圖分別通過畫圖來拆解各個步驟（在演示旋轉(zhuǎn)的時候我們先屏蔽掉顏色的干擾，單純來看旋轉(zhuǎn)的特性）

6.1、左旋

R 表示旋轉(zhuǎn)節(jié)點，沒有別的特殊的含義，以下的節(jié)點都是沒有任何實際意義的

假設(shè)這是一個帶旋轉(zhuǎn)的樹，假設(shè)以 R 點為旋轉(zhuǎn)節(jié)點，根據(jù)左旋特性第一點：旋轉(zhuǎn)節(jié)點的右子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的父節(jié)點

以上的圖應(yīng)該不難想象，先啥也不管，不是要左旋嗎？那就直接找到旋轉(zhuǎn)節(jié)點，然后將旋轉(zhuǎn)節(jié)點的右子節(jié)點設(shè)置成旋轉(zhuǎn)節(jié)點的父節(jié)點。下一步，將旋轉(zhuǎn)節(jié)點的右子節(jié)點的左子節(jié)點設(shè)置為旋轉(zhuǎn)節(jié)點的右子節(jié)點，再看下圖

這就完事了，左旋的概念我們在一起加深下（因為這個對于紅黑樹的平衡起到核心作用）。左旋：以某個節(jié)點作為固定支撐點（圍繞該節(jié)點旋轉(zhuǎn)）,其右子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的父節(jié)點，右子節(jié)點的左子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的右子節(jié)點，左子節(jié)點保持不變

6.2、右旋

右旋：以某個節(jié)點作為固定支撐點（圍繞該節(jié)點旋轉(zhuǎn)），其左子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的父節(jié)點，左子節(jié)點的右子節(jié)點變?yōu)樾D(zhuǎn)節(jié)點的左子節(jié)點，右子節(jié)點保持不變。還是來看圖

還是假設(shè)以 R 為旋轉(zhuǎn)節(jié)點進(jìn)行右旋，首先將 R 節(jié)點的左子節(jié)點 L 設(shè)置成 R 的父節(jié)點，完事后是下面這樣子的

接著是第二小點，將 R 的左節(jié)點（L）的右子節(jié)點（LR）設(shè)置成 R 的左子節(jié)點，那根據(jù)上圖應(yīng)該直接就能想象出來了，那就是下面這樣子的

就這？還頭皮發(fā)麻不。

到此，這僅僅算是熱身吧，這是萬里長征的第一步，因為以下的所有的講解都是在左旋右旋和變色的基礎(chǔ)上討論的（變色你不是還沒介紹嗎？黑色變紅色，紅色變黑色，介紹完了）

6.3、節(jié)點的查找

牢記一個原則，紅黑樹是基于二叉搜索樹的，所以查找的特性和其是類似的，這個也不是重點，重點是紅黑樹的節(jié)點的添加，但是這里為啥非得提一嘴捏，因為插入節(jié)點的時候肯定要先查找定位嘛。

6.4、節(jié)點的添加

先回顧下紅黑樹的性質(zhì)，為了不讓各位來回翻頁，小弟直接將其復(fù)制過來

#?紅黑樹的定義（特性）
1.?根節(jié)點是【黑色】
2.?每個節(jié)點要么是【黑色】要么是【紅色】
3.?每個【紅色】節(jié)點的兩個子節(jié)點一定都是【黑色】
4.?每個葉子節(jié)點（NIL）都是【黑色】
5.?任意一個節(jié)點的路徑到葉子節(jié)點所包含的【黑色】節(jié)點的數(shù)量是相同的---這個也稱之為【黑色完美平衡】
6.?新插入的節(jié)點必須是【紅色】->為什么？如果新插入的節(jié)點是【黑色】，那不管是在插入到那里，一定會破壞黑色完美平衡的，因為任意一個節(jié)點的路徑到葉子節(jié)點的黑色節(jié)點的數(shù)量肯定不一樣了（第 6 點我自己加的，實際特性的定義是前 5 個）

添加實際上順帶了查找，所以在添加節(jié)點之前，必然要進(jìn)行查找節(jié)點的位置，然后再插入節(jié)點，最后再自平衡。其中注意上面我自己添加的第 6 點，那就是新插入的節(jié)點一定是紅色的（上面的第 6 點已經(jīng)說的很清楚了，主要是為了防止一插入節(jié)點就破壞黑色完美平衡），不管后面怎么處理，新插入的節(jié)點只能是紅色節(jié)點。

另外，我們還需要做如下的約定，假設(shè)新添加的節(jié)點為 I，I 的父節(jié)點為 P ，P 的兄弟節(jié)點為 U，P 父親節(jié)點為（也就是 I 節(jié)點的爺爺節(jié)點） G，那這個結(jié)構(gòu)是這樣子的 （下圖不要管字母的順序，僅僅是表示一個節(jié)點的關(guān)系）

接下來是最難堅持的各種自平衡常見的分析了

下面開始進(jìn)行各種情況的分析

• 第 1 種情況：紅黑樹為空樹

那這還不好辦嘛，插入的節(jié)點 I 就是根節(jié)點如下圖：

咦？插入節(jié)點是紅色節(jié)點沒毛病，但是這個也是根節(jié)點啊？那就變色唄，所以當(dāng)紅黑樹為空的時候新插入的節(jié)點直接變色即可。so easy~

• 第 2 種情況：插入的節(jié)點已經(jīng)存在

還是畫圖來說，這樣更直觀

然后替換已有的 I 節(jié)點，如下圖

此時很顯然已經(jīng)破壞了黑色完美平衡了，這個也好說，直接將 I 變色即可。第二種情況也不過如此嘛。

• 第 3 種情況：插入節(jié)點的父節(jié)點為黑色

假設(shè)待插入的節(jié)點為 Q ，那實際上應(yīng)該是這樣子的

完事了，為啥？因為這個樹本來就是黑色完美平衡了，再新插入一個新的節(jié)點紅色節(jié)點，并不會破壞樹的平衡以及紅黑樹的特性（不要去研究為什么?？茖W(xué)家研究了好幾年的東西，咱就不要再去深挖了）

• 第 4 種情況：插入節(jié)點的父節(jié)點為紅色

萬變不離其宗，繼續(xù)回顧紅黑樹性質(zhì)，插入的節(jié)點為紅色，根節(jié)點為黑色，那既然插入的節(jié)點的父節(jié)點為紅色節(jié)點，而紅色節(jié)點一定不可能為根節(jié)點，所以可以推斷出新插入節(jié)點的父節(jié)點一定還有父節(jié)點，也就是新插入的節(jié)點一定有爺爺節(jié)點。這里為什么這么強調(diào)，因為以后的平衡可能會涉及到類似的遞歸的自旋，直到平衡。類似這樣子（不要關(guān)心字母的順序，僅僅表示一個關(guān)系）

那現(xiàn)在很顯然違反了上面的特性 3 ?每個【紅色】節(jié)點的兩個子節(jié)點一定都是【黑色】,而現(xiàn)在是兩個紅色節(jié)點相連了，這個該怎么處理？此時又繼續(xù)拆分不同的情況了

• 第 4-1 種情況：插入節(jié)點的叔叔節(jié)點存在，且為紅色

此時又可以推斷出來叔叔節(jié)點的父節(jié)點一定是黑色，因為不能有兩個紅色節(jié)點相連（該特性和每個【紅色】節(jié)點的兩個子節(jié)點一定都是【黑色】是一個意思 ），所以這個時候你看的樹大致是這樣子的結(jié)構(gòu)

以下的處理方式是固定的。只要是這種場景（我們以插入節(jié)點和插入節(jié)點的父節(jié)點以及插入節(jié)點的爺爺節(jié)點作為一個自旋整體），那么就按照這么處理：

① 將 P 和 U 變成黑色；② 將 PP 變成 紅色。如下圖：

那既然 PP 是根節(jié)點，那肯定不可能為紅色了，接下來就是將 PP 當(dāng)作是當(dāng)前節(jié)點，然后繼續(xù)判斷處理。

先記住這個步驟，下面還會再說到，因為這個就是紅色樹的特性，既然性質(zhì)都限制死了，那其實處理的方式也就那么幾種。我們繼續(xù)往下看

• 第 4-2 種情況：叔叔節(jié)點不存在或者為黑色，且插入節(jié)點的【父節(jié)點】是插入節(jié)點爺爺節(jié)點的【左子節(jié)點】

說了再多不如一張圖搞定（不要忘記第四種情況的大前提，插入節(jié)點的父節(jié)點為紅色）

實際上上圖是稍微有點不合理的，因為這樣子的話就破壞了黑色完美平衡了，也就是說叔叔節(jié)點如果不是紅色，那肯定也不可能是黑色的，那剩下的只能是 NULL，下面這張圖才是比較合適的表達(dá) 4-2 的情況。

等等，為啥說是比較合適的？因為插入的節(jié)點可能為其父節(jié)點的左子節(jié)點，也可能是其父節(jié)點的右子節(jié)點。下面這樣圖才是完美的

那既然不確定是左子節(jié)點還是右子節(jié)點，那肯定是要繼續(xù)分情況了唄，沒錯

• 第 4-2-1 種情況：插入節(jié)點為其父節(jié)點的左子節(jié)點，也即 LL 雙紅色的情況（第一個 L 表示插入節(jié)點的父節(jié)點，第二個 L 表示插入節(jié)點）

那這種情況肯定就是這樣子的了

這個怎么搞了？我說接下來更簡單你可能會不信，其實就像我剛剛上面說的，步驟都是固定的，接下來為了平衡，步驟為：

① 將 P 節(jié)點變成黑色，將 PP 節(jié)點變成 紅色

② 對 PP 節(jié)點進(jìn)行右旋（以 PP 節(jié)點為旋轉(zhuǎn)節(jié)點，進(jìn)行右旋）

右旋的特點還記得不？右旋：旋轉(zhuǎn)節(jié)點的左子節(jié)點變成其父節(jié)點，旋轉(zhuǎn)節(jié)點的左子節(jié)點的右子節(jié)點變成旋轉(zhuǎn)節(jié)點的左子節(jié)點，那這個旋轉(zhuǎn)節(jié)點的左子節(jié)點的右子節(jié)點不是為 NULL 嘛？那就不管唄，所以，以 PP 為旋轉(zhuǎn)節(jié)點的旋轉(zhuǎn)后的結(jié)果是：

其完整的變換流程如下：

• 第 4-2-2 種情況：插入節(jié)點為其父節(jié)點的右子節(jié)點，也即 LR 雙紅色的情況

這個時候處理方式依舊是固定的，就是將其變成 LL 雙紅的情況，然后按照 LL 雙紅的情況去處理。那么問題來了，該如何才能變成 LL 雙紅的情況呢？依舊是固定的套路，直接按照以下的步驟操作：

① 將 P 節(jié)點作為旋轉(zhuǎn)節(jié)點，進(jìn)行左旋，其結(jié)果是這樣子的

② 這個時候就變成了了熟悉的味道了，接下來就按照 LL 雙紅的情況來處理：① 將 I 變成黑色，將 PP 變成紅色，② 然后以 PP 為旋轉(zhuǎn)節(jié)點，進(jìn)行右旋

其完成的變換流程如下：

• 第 4-3 種情況：叔叔節(jié)點不存在或者為黑色，且插入節(jié)點的【父節(jié)點】是插入節(jié)點爺爺節(jié)點的【右子節(jié)點】

4-3 這種情況和 4-2 剛好反過來，但是我還是會一步一步來介紹的

這種情況依舊是繼續(xù)區(qū)分插入節(jié)點是其父節(jié)點的左子節(jié)點還是右子節(jié)點

• 第 4-3-1 種情況：插入節(jié)點為其父節(jié)點的右子節(jié)點，也即 RR 雙紅色的情況（第一個 R 是插入節(jié)點的父節(jié)點，第二個 R 是插入節(jié)點）

也就是下面這樣子的

處理步驟如下：

① 將 P 設(shè)置為 黑色，將 PP 設(shè)置為紅色

② 以 PP 節(jié)點為旋轉(zhuǎn)節(jié)點，進(jìn)行左旋

其整個轉(zhuǎn)換流程是這樣的

• 第 4-3-2 種情況：插入節(jié)點為其父節(jié)點的左子節(jié)點，也即 RL 雙紅色的情況

你是不是覺得對于這種情況那不就是應(yīng)該先將 RL 轉(zhuǎn)換成 RR 這種情況嗎？沒錯，就是這樣，我發(fā)現(xiàn)你都開始學(xué)會搶答了。

這個時候處理的步驟是這樣子的：首先以 P 節(jié)點為旋轉(zhuǎn)節(jié)點，進(jìn)行右旋，結(jié)果是這樣子的

然后將 I 設(shè)置為 黑色，將 PP 設(shè)置為紅色

然后以 PP 為旋轉(zhuǎn)節(jié)點，進(jìn)行左旋

其完整的轉(zhuǎn)換流程是這樣子的：

好了，我們趕緊做個總結(jié)，相信很多小伙伴看了上面的各種情況基本已經(jīng)凌亂了，甚至都沒看到這里就撤了。。下面我們將各個情況總結(jié)如下

6.5、結(jié)束語

最后我們再來對紅黑樹自平衡的各個情況做個總結(jié)：

紅黑樹性質(zhì)：
????根節(jié)點為黑色
????節(jié)點不是紅色就是黑色
????每個葉子節(jié)點NIL為黑色
????紅色節(jié)點的兩個子節(jié)點一定都是黑色
????任意一個節(jié)點到葉子節(jié)點的路徑都包含相同數(shù)量的黑色節(jié)點，俗稱：黑高
????（如果一個節(jié)點的存在黑子節(jié)點，那么該節(jié)點肯定有兩個子節(jié)點）

當(dāng)前節(jié)點為I，父節(jié)點為P，P節(jié)點的兄弟節(jié)點為U，P的父節(jié)點為PP（祖父節(jié)點）
1、當(dāng)前節(jié)點為空，直接插入即可
2、插入的節(jié)點已經(jīng)存在，直接替換即可
3、插入節(jié)點的父節(jié)點為【黑色節(jié)點】，找到父節(jié)點，直接插入即可。不會影響完美黑平衡
4、插入節(jié)點的父節(jié)點為【紅色節(jié)點】
??? 4.1、叔叔節(jié)點存在，且為【紅色節(jié)點】
????由紅黑樹的性質(zhì)可知：紅色節(jié)點不能相連，=》祖父節(jié)點肯定為黑色節(jié)點
????此時紅黑層數(shù)情況是【黑紅紅】，最簡單的處理方式就是改成【紅黑紅】
????處理方式：
????????將P和U改為黑色
????????PP改為紅色
????????將PP節(jié)點設(shè)置為當(dāng)前節(jié)點，進(jìn)行后續(xù)處理
????4.2、叔叔節(jié)點不存在或者叔叔節(jié)點是【黑色節(jié)點】且插入節(jié)點的父節(jié)點是祖父節(jié)點的左子節(jié)點
??????? 4.2.1、插入節(jié)點為其父節(jié)點的左子節(jié)點（這個時候是LL雙紅的情況：當(dāng)前節(jié)點為紅色，當(dāng)前節(jié)點的父節(jié)點為紅色，當(dāng)前節(jié)點為其父節(jié)點的左子節(jié)點）
????????處理方式：
????????????????變顏色：將P節(jié)點設(shè)置為黑色，將PP節(jié)點設(shè)置為紅色
????????????????對PP節(jié)點進(jìn)行右旋
??????? 4.2.2、插入節(jié)點為其父節(jié)點的右子節(jié)點（這個時候是LR雙紅的情況：當(dāng)前節(jié)點為紅色，當(dāng)前節(jié)點的父節(jié)點為紅色，當(dāng)前節(jié)點為其父節(jié)點的右子節(jié)點）
????????處理方式：
????????????對P節(jié)點進(jìn)行左旋，這個時候就會變成LL雙紅
????????????此時按照4.2.1的處理方式處理
????4.3、叔叔節(jié)點不存在或者叔叔節(jié)點是【黑色節(jié)點】且插入節(jié)點的父節(jié)點為祖父節(jié)點的右子節(jié)點
??????? 4.3.1、插入節(jié)點為其父節(jié)點的右子節(jié)點（這個時候是RR雙紅的情況：當(dāng)前節(jié)點為紅色，當(dāng)前節(jié)點的父節(jié)點為紅色，當(dāng)前節(jié)點為其父節(jié)點的右子節(jié)點）
????????處理方式：
????????????變顏色：將P節(jié)點設(shè)置為黑色，將PP節(jié)點設(shè)置為紅色
????????????對PP節(jié)點進(jìn)行左旋
??????? 4.3.2、插入節(jié)點為其父節(jié)點的左子節(jié)點（這個時候是RL雙紅的情況：當(dāng)前節(jié)點為紅色，當(dāng)前節(jié)點的父節(jié)點為紅色，當(dāng)前節(jié)點為其父節(jié)點的左子節(jié)點）
????????處理方式：
????????????對P節(jié)點進(jìn)行右旋，這個時候變成RR雙紅
????????????此時按照4.3.1的方式進(jìn)行處理