那些年，面試被虐過的紅黑樹

背景

上週，一位同學去面試了，過程大致如下：

面試官：java 開發，三年了，熟悉哪些 java 集合？

同學：ArrayList、HashMap、TreeMap、LinkedList.....（回答了挺多的）。

面試官：說說 HashMap 在 JDK7 和 JDK8 的區別。

同學：主要區別有四點：

1、實現方式：JDK7 中使用數組 + 鏈表來實現，JDK8 使用的數組 + 鏈表 + 紅黑樹

2、新節點插入到鏈表的順序不同：JDK7 插入在頭部，JDK8 插入在尾部

3、JDK8 的 hash 算法有所簡化

4、擴容機制有所優化

（此時，同學的心裏想，幸好我背過老田的面試小抄 java 集合部分）

面試官：既然，你知道 JDK8 引入了紅黑樹，我這裏有黑筆和紅筆，你在這個牆壁上收畫一顆紅黑樹（小會議室是玻璃牆）。

同學：（尼瑪，這個我不會呀，他肯定還會問紅黑的特點，紅黑樹和平和二叉樹有什麼區別，紅黑旋轉，增加、刪除...，嚥了咽口水說）額.... 這個不太會。

世間都是套路，還以爲問完區別就差不多了，或者頂多再問問 HashMap 爲什麼線程不安全、HashMap 如何擴容之類的問題。你有過類似的經歷嗎？

今天我們就來研究研究面試官難爲這位同學的紅黑樹。其實，說到紅黑樹，我們搞 java 開發的多多少少還是知道些，對很大部分朋友來說是熟悉而又陌生的傢伙。熟悉是因爲很多人可能學過，也看過不少紅黑樹的文章，同時我們都直接或者間接的使用過。陌生是因爲紅黑樹，在設計和實現上的複雜性讓很多人望而生畏，就和 Spring 源碼一樣。

其實，總得來說，紅黑樹的定義還是比較簡單，但你必須知道一些基本的知識，比如什麼是樹？樹怎麼遍歷？二叉樹？平衡二叉樹？...

紅黑樹無非就是在插入和刪除的過程中自平衡規則多了點，不過也不是想象中的那麼可怕，今天我們就來搞定它。

樹

生活中的樹

數據結構中的樹

樹結構是一種非線性存儲結構，存儲的是具有 “一對多” 關係的數據元素的集合。

可以看出，和我們生活中的樹就是一毛一樣的，只是看起來一個是正着一個是倒着。倒着知識爲了便於理解。

上圖中的樹是使用樹結構存儲的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意圖。對於數據 A 來說，和數據 B、C、D 有關係；對於數據 B 來說，和 E、F 有關係。這就是 “一對多” 的關係。

樹的節點

「結點」：使用樹結構存儲的每一個數據元素都被稱爲 “結點”。例如，圖中，數據元素 A 就是一個結點；

「父結點（雙親結點）、子結點和兄弟結點」：對於圖中的結點 A、B、C、D 來說，A 是 B、C、D 結點的父結點（也稱爲 “雙親結點”），而 B、C、D 都是 A 結點的子結點（也稱 “孩子結點”）。對於 B、C、D 來說，它們都有相同的父結點，所以它們互爲兄弟結點。

「樹根結點」（簡稱 “「根結點」”）：每一個非空樹都有且只有一個被稱爲根的結點。圖中，結點 A 就是整棵樹的根結點。

「葉子結點」：如果結點沒有任何子結點，那麼此結點稱爲葉子結點（葉結點）。例如圖中，結點 K、L、F、G、M、I、J 都是這棵樹的葉子結點。

樹根的判斷依據：如果一個結點沒有父結點，那麼這個結點就是整棵樹的根結點。

子樹

子樹：如圖中，整棵樹的根結點爲結點 A，而如果單看結點 B、E、F、K、L 組成的部分來說，也是棵樹，而且節點 B 爲這棵樹的根結點。所以稱 B、E、F、K、L 這幾個結點組成的樹爲整棵樹的子樹；同樣，結點 E、K、L 構成的也是一棵子樹，根結點爲 E。

注意：單個結點也是一棵樹，只不過根結點就是它本身。圖 1 中，結點 K、L、F 等都是樹，且都是整棵樹的子樹。

知道了子樹的概念後，樹也可以這樣定義：樹是由根結點和若干棵子樹構成的。

空樹

空樹：如果集合本身爲空，那麼構成的樹就被稱爲空樹。空樹中沒有結點。

二叉樹

二叉樹指的是每個節點最多隻能有兩個子數的有序樹。通常左邊的子樹稱爲左子樹，右邊的子樹稱爲右子樹。

二叉樹簡單的示意圖如下：

左子樹與右子樹

通常左邊的子樹稱爲左子樹，右邊的子樹稱爲右子樹。這裏說的有序樹強調的是二叉樹的左子樹和右子樹的次序不能隨意顛倒。

java 中的定義

public class Node {
    T data;
    Node left;
    Node right;
}

C++ 中的定義

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

排序二叉樹

所謂排序二叉樹，顧名思義，排序二叉樹是有順序的，它是一種特殊結構的二叉樹，我們可以對樹中所有節點進行排序和檢索。

性質

排序二叉樹簡單示意圖：

排序二叉樹退化成鏈表

排序二叉樹的左子樹上所有節點的值小於根節點的值，右子樹上所有節點的值大於根節點的值，當我們插入一組元素正好是有序的時候，這時會讓排序二叉樹退化成鏈表。

正常情況下，排序二叉樹是如下圖這樣的：

但是，當插入的一組元素正好是有序的時候，排序二叉樹就變成了下邊這樣了，就變成了普通的鏈表結構，如下圖所示:

正常情況下的排序二叉樹檢索效率類似於二分查找，二分查找的時間複雜度爲 O(log n)，但是如果排序二叉樹退化成鏈表結構，那麼檢索效率就變成了線性的 O(n) 的，這樣相對於 O(log n) 來說，檢索效率肯定是要差不少的。

思考，二分查找和正常的排序二叉樹的時間複雜度都是 O(log n)，那麼爲什麼是 O(log n) ？

爲了解決排序二叉樹在特殊情況下會退化成鏈表的問題（鏈表的檢索效率是 O(n) 相對正常二叉樹來說要差不少），所以有人發明了平衡二叉樹和紅黑樹類似的平衡樹。

平衡二叉樹

平衡二叉樹，又被稱爲 AVL（Adelson-Velsky and Landis）樹。

定義：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過 1，並且左右兩個子樹都是一棵平衡二叉樹。

兩個條件：

平衡二叉樹必須是排序二叉樹，也就是說平衡二叉樹他的左子樹所有節點的值必須小於根節點的值，它的右子樹上所有節點的值必須大於它的根節點的值。
左子樹和右子樹的深度之差的絕對值不超過 1。

紅黑樹

哈哈哈，這回，終於輪我倒了。

紅黑樹（如上圖，引用自維基百科）是一種自平衡的二叉樹，所謂的自平衡是指在插入和刪除的過程中，紅黑樹會採取一定的策略對樹的組織形式進行調整，以儘可能的減少樹的高度，從而節省查找的時間。

紅黑樹的特性如下：

結點是紅色或黑色
根結點始終是黑色
葉子結點（NIL 結點）都是黑色
紅色結點的兩個直接孩子結點都是黑色（即從葉子到根的所有路徑上不存在兩個連續的紅色結點）
從任一結點到每個葉子的所有簡單路徑都包含相同數目的黑色結點

很多人，估計也就是在面試抱佛 jio 的時候，背背紅黑樹的這五個特性罷了。

以上性質保證了紅黑樹在滿足平衡二叉樹特徵的前提下，還可以做到從根到葉子的最長路徑最多不會超過最短路徑的兩倍，這主要是考慮兩個極端的情況，由性質 4 和 5 我們可以知道在一棵紅黑樹上從根到葉子的最短路徑全部由黑色結點構成，而最長結點則由紅黑結點交錯構成（始終按照一紅一黑的順序組織），又因爲最短路徑和最長路徑的黑色結點數目是一致的，所以最長路徑上的結點數是最短路徑的兩倍。

自平衡策略

對於一棵紅黑樹的操作最基本的無外乎增刪改查，其中查和改都不會改變樹的結構，所以與普通平衡二叉樹操作無異。剩下的就是增刪操作，插入和刪除都會破壞樹的結構，不過藉助一定的平衡策略能夠讓樹重新滿足定義。平衡策略可以簡單概括爲三種：左旋轉、右旋轉，以及變色。在插入或刪除結點之後，只要我們沿着結點到根的路徑上執行這三種操作，就可以最終讓樹重新滿足定義。

「左旋轉」

對於當前結點而言，如果右子結點爲紅色，左子結點爲黑色，則執行左旋轉，如下圖：

「右旋轉」

對於當前結點而言，如果左子、左孫子結點均爲紅色，則執行右旋轉，如下圖：

「變色」

對於當前結點而言，如果左、右子結點均爲紅色，則執行變色，如下圖：

插入操作

紅黑樹作爲平衡二叉樹的一種，同樣需要藉助於查找操作定位插入點，不過紅黑樹約定新插入的結點一律爲紅色，這主要也是爲了簡化樹的自平衡過程。對於一棵空樹而言，插入結點爲紅色會增加一次變色操作，但是對於其餘的情況，如果插入的結點是一個黑色結點，那麼必然會破壞性質 5，而插入一個紅色結點有可能會破壞性質 4，但是此時我們可以通過簡單的策略對樹進行調整以重新滿足定義。

我們約定 X 爲插入的結點，P 爲 X 的父結點，G 爲 X 的祖父結點，U 爲 X 的叔叔結點。

下面遵從上述策略分場景對插入過程進行探討：

新插入結點 X 是根結點。

此時新插入結點爲紅色，違背性質 2，只需將其變爲黑色即可。

新插入結點 X 的父結點 P 是黑色

此時需要依據新插入結點 X 值相對於父結點 P 的大小分爲兩種情況，如果小於則將 X 簡單插入到 P 的左子位置即可（下圖左），如果 X 的值大於 P，則需要將 X 插入到 P 的右子結點位置，然後執行一次左旋轉即可（下圖右）。

父結點 P 爲紅色，同時存在叔叔結點 U 也爲紅色

因爲 P 爲紅色，按照性質 4 則 G 必定爲黑色，如果 X 的值小於 P，則需要在 P 的左子位置插入（如下圖），插入後不滿足性質 4，此時只需要執行一次變色操作，將 P、G、U 的顏色反轉一下即可，因爲 G 變爲紅色，所以路徑長度減 1，但是因爲 P 和 U 都變爲了黑色，所以路徑長度又加 1，最終長度不變，但此時 G 變爲了紅色，所以需要繼續向上遞歸。

如果 X 的值大於 P，則需要在 P 的右子位置插入（如下圖），插入後不滿足性質 4，此時需要先執行左旋轉變爲上面這種情況，繼續變色即可。

父結點 P 爲紅色，同時叔叔結點 U 爲黑色或不存在

因爲 P 爲紅色，按照性質 4 則 G 必定爲黑色，如果 X 的值小於 P，則需要在 P 的左子位置插入（如下圖），插入後不滿足性質 4，此時需要先執行一次右旋轉，旋轉之後仍然違背性質 4，同時左子樹的高度減 1，這個時候需要再執行一次變色操作即可滿足定義。

如果 X 的值大於 P，則需要在 P 的右子位置插入（如下圖），插入後不滿足性質 4，此時我們需要執行一次左旋轉，然後就轉換成了上面這種情況，繼續右旋轉、變色即可。

刪除操作

紅黑樹作爲平衡二叉樹的一種，同樣需要藉助於查找操作定位刪除點，在執行刪除之前我們需要判斷待刪除結點有幾個孩子結點，如果是 2 個的話我們需要從結點的左子樹中尋找值最大的結點，或者從右子樹中尋找值最小的結點，並用結點值替換掉待刪除結點（只要目標結點值從樹上消失即可，不要糾結具體刪除的是哪個結點）。這兩個結點有一個共性，即最多隻有一個孩子結點（因爲已經是自己所處範圍內的最大和最小了嘛，一山不容二虎（鼠）），此時就將需求轉變成刪除只有一個孩子結點的結點，相對要簡單了許多。

我們約定 X 爲待刪除的結點，P 爲 X 的父結點，S 爲 X 的孩子結點，B 爲 X 的兄弟結點，BL 爲 B 的左孩子結點，BR 爲 B 的右孩子結點。

如果待刪除結點 X 是一個紅色結點，則直接刪除即可，不會違反定義。
如果待刪除結點 X 是一個黑色結點，且其孩子結點 S 是紅色的，那麼只需要將 X 替換成 S，同時將 S 由紅變黑即可。
如果需要刪除的結點 X 是黑色的，同時它的孩子結點 S 也是黑色的，這種情況需要進一步分場景討論。

對於第三種情況我們首先將 X 替換成 S，並重命名其爲 N，N 沿用 X 對於長輩和晚輩的稱呼，需要清楚這裏實際刪除的是 X 結點，並且刪除之後通過 N 的路徑長度減 1。

1.N 是新的根

這種情況比較簡單，不需要再做任何調整。

2.N 的父結點、兄弟結點 B，以及 B 的孩子結點均爲黑色

如下圖，此時只需要將 B 變爲紅色即可，這樣所有通過 B 的路徑減 1，與所有通過 N 的路徑正好一致，但是此時通過 P 的路徑都減少了 1 個長度，所以需要向上遞歸對結點 P 繼續判定。

3.N 的兄弟結點 B 爲紅色，其餘結點均爲黑色

如下圖，此時需要執行一次左旋轉，然後將 P 和 B 的顏色互換。調整前後各個結點的路徑沒有變化，但是因爲之前經過 N 的路徑長度少了一個單位，所以此時仍然不滿足定義，需要按照後面的場景繼續調整。

4.N 的父結點 P 爲紅色，兄弟結點 B，以及 B 的孩子結點均爲黑色

如下圖，此時我們只需要簡單互換 P 和 B 的顏色，這種情況下對於不通過 N 的結點路徑沒有影響，但是卻讓通過 N 的結點路徑加 1，正好彌補之前刪除操作所帶來的損失。

5.N 的兄弟結點 B 爲黑色，B 的左孩子爲紅色，B 的右孩子爲黑色

如下圖，此時我們需要先執行一次右旋轉操作，然後互換 B 與 BL 的顏色，操作之後通過所有結點的路徑長度並沒有發生變化，卻讓 N 有了一個新的黑色兄弟結點，並且該兄弟結點的右孩子爲紅色，從而可以按照接下去介紹的一種場景繼續調整。

注：白色結點表示該結點既可以是黑色也可以是紅色，後續圖示亦是如此。

6.N 的兄弟結點 B 爲黑色，B 的右孩子爲紅色

如下圖，此時我們需要先執行一次左旋轉，並互換 P 和 B 的顏色，同時將 B 的右孩子結點變爲黑色。變更之後，除 N 外其餘結點的路徑長度未發生變化，但是經過 N 的路徑上卻增加了一個黑色結點，這剛好彌補之前刪除操作所帶來的損失。

總結

我們從樹的概念說起，到二叉樹、平衡二叉樹，最後到紅黑樹。其實紅黑樹的主要難點在於插入和刪除過程中的自平衡調整，其中插入過程的調整相對簡單，刪除的過程需要處理的情況要多一些，但不管是插入還是刪除，都建議讀者將所有的圖放置在一起進行觀察，能夠發現其中承前啓後的奧妙，本文鑑於篇幅就不再貼出長圖。

參考：www.zhenchao.org

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ucQOYetaeSeiQ52Z2g2eRQ

樹