前言
紅黑樹
在講紅黑樹之前，我們需要先了解幾種樹：二叉樹，二叉查找樹以及平衡二叉樹，
二叉樹
最多有 2 個孩子的樹稱為二叉樹，由于二叉樹中的每個元素只能有 2 個孩子，我們通常將它們命名為左孩子和右孩子，
- 示意：
5
/ \
2 3
復制代碼- 代碼定義：
class Node {
T data;
Node left;
Node right;
}
復制代碼二叉查找樹
二叉查找樹（Binary Search Tree，簡稱BST），（又：二叉搜索樹，二叉排序樹） 它是一種基于節點的二叉樹資料結構，具有以下特性：
- 節點的左子樹僅包含值小于節點值的節點，
- 節點的右子樹僅包含值大于節點值的節點，
- 左右子樹也必須是二叉查找樹，
- 示意：
5 / \ 2 6 / \ 1 3 \ 4 復制代碼
一顆平衡的 BST 查找效率很高，原理就是二分查找，二分查找的時間復雜度為 O(log n)，
二叉查找樹退化成鏈表
當我們插入一組元素正好是有序的時候，這時會讓排序二叉樹退化成鏈表，如下所示:
1
\
2
\
3
\
4
復制代碼這樣排序二叉樹退化成鏈表結構，那么檢索效率就變成了線性的 O(n) 的，相對來說，檢索效率肯定是要差不少的，
平衡二叉樹
平衡二叉樹 (AVL) 樹是一種自平衡二叉查找樹 (BST)，并且其中所有節點的左右子樹的高度差不能超過 1，
平衡二叉樹在二叉查找樹的基礎上多了一個特性：所有節點的左右子樹的高度差不能超過 ；從而實作自平衡，
AVL樹示意：
13
/ \
8 18
/ \ \
6 10 20
/
4
復制代碼大多數 BST 操作（例如，搜索、最大、最小、插入、洗掉等）花費 O(h) 時間，其中 h 是 BST 的高度，對于偏斜二叉樹，這些操作的成本可能變為 O(n)，如果我們確保每次插入和洗掉后樹的高度都保持 O(Logn)，那么我們可以保證所有這些操作的上限為 O(Logn)，AVL 樹的高度始終為 O(Logn)，其中 n 是樹中的節點數，
紅黑樹
- 介紹：
紅黑樹是一種自平衡二叉搜索樹，每個節點都有一個額外的位置用來存盤節點的顏色（紅色或黑色），這些顏色用于確保樹在插入和洗掉程序中保持平衡，雖然樹的平衡性并不完美，但足以減少搜索時間并保持在 O(log n) 時間左右，其中 n 是樹中元素的總數，紅黑樹是由魯道夫·拜耳 (Rudolf Bayer) 于 1972 年發明的，
其實紅黑樹和上面的平衡二叉樹類似，本質上都是為了解決排序二叉樹在極端情況下退化成鏈表導致檢索效率大大降低的問題，
紅黑樹的特性
- 每個節點要么是紅色，要么是黑色，
- 根節點永遠是黑色的，
- 所有的葉子節點都是空節點（即null），并且是黑色的，
- 沒有兩個相鄰的紅色節點（紅色節點不能有紅色父節點或紅色子節點），
- 從任一節點到其子樹中每個葉子節點的路徑都包含相同數量的黑色節點，
紅黑樹示意圖：
``
對于3 中指定紅黑樹的每個葉子節點都是空節點，而且葉子節點都是黑色，但 Java 實作的紅黑樹會使用 null 來代表空節點，因此我們在遍歷 Java里的紅黑樹的時候會看不到葉子節點，而看到的是每個葉子節點都是紅色的，這一點需要注意，
由第5條：
- 從任一節點到它的子樹的每個葉子節點黑色節點的數量都是相同的，這個數量被稱為這個節點的黑高
- 從根節點出發到每個葉子節點的路徑都包含相同數量的黑色節點，這個黑色節點的數量被稱為樹的黑高
我們知道 AVL 樹 所有節點的左右子樹的高度差不超過 1， 在這里我們思考一個問題，對于紅黑樹任意節點左右樹的高度差是多少呢？
看下面的這個紅黑樹：
依次驗證上面5條特性，
- 每個節點要么是紅色，要么是黑色，
- 根節點永遠是黑色的，
- 所有的葉子節點都是空節點（即null），并且是黑色的，
- 沒有兩個相鄰的紅色節點（紅色節點不能有紅色父節點或紅色子節點），
- 從任一節點到其子樹中每個葉子節點的路徑都包含相同數量的黑色節點，
發現都可以滿足，
事實上，以上是紅黑樹中比較極端的一個例子，該樹在滿足紅黑樹特性的前提下，左子樹達到了最小高度（全黑） ，右子樹達到了最大高度（一層黑一層紅，紅黑交替） ；分別是 2 和 4；
也就是說，一個黑高為 3 的紅黑樹 ，其最小高度為3，最大高度為 5；同時其子樹最小高度為 2，最大高度為 4，
從一個節點到其最遠后代葉的節點數不超過到最近后代葉節點數的兩倍；可以這么簡單理解，紅黑樹根節點到葉子節點最長的路徑都不會比最短的路徑長出兩倍，
紅黑樹 VS AVL樹
與紅黑樹相比，AVL 樹更平衡，但它們在插入和洗掉程序中可能會導致更多的旋轉，所以如果涉及頻繁的插入和洗掉，那么紅黑樹應該是首選，如果插入和洗掉不那么頻繁并且搜索是一個更頻繁的操作，那么 AVL 樹應該比紅黑樹更合適，
紅黑樹的應用
紅黑樹的應用比較廣泛，主要是用它來存盤有序的資料，它的時間復雜度是O(lgn)，效率非常之高， 例如，Java集合中的 TreeSet 和 TreeMap，C++ STL中的set、map，以及Linux虛擬記憶體的管理，都是通過紅黑樹去實作的，
插入
當我們向紅黑樹中插入新的元素時，紅黑樹發生變化，有可能不再滿足那5個條件，不再平衡；我們有兩種方法使其重新恢復平衡：重新著色、旋轉，
其中旋轉分為左旋和右旋
- 對X左旋：
- 對X右旋：
為了避免混淆，接下來使用圖示的叫法：
設 X 為新插入的節點，完整步驟為：
一、按照二叉查找插入方法將 X 插入到指定的位置，并將新插入節點的顏色設為紅色，
二、如果 X 是根節點，則將 X 的顏色更改為黑色，
三、被 X 節點的父節點是黑色，什么都不需要做，
四、被 X 節點的父節點是紅色（該情況與紅黑樹的“特性(4)”相沖突）：
? a) 如果 x 的叔叔節點是紅色的
- 將父節點和叔叔節點的顏色更改為黑色
- 將祖父節點設為紅色
- 令 x = 祖父節點，對新的 x 重復以上步驟
? b) 如果 x 的叔叔節點是黑色的，分別對應下面四種不同情況
- 左左案例（LL 旋轉）
- 左右案例（LR 旋轉）
- 右右案例（RR 旋轉）
- 右左案例（RL 旋轉）
以上就是插入的所有步驟，接下來舉例分析以上幾種情況：
叔叔節點為紅色：
這種情況不需要旋轉，只需要對父節點，叔叔節點，祖父節點重新染色即可，注意，由于祖父節點重新染色后有可能會破壞掉之前的平衡，所以我們需要對祖父節點重復這個染色操作，使其始終滿足5條特性，
左左案例（插入節點的父節點是左節點，插入節點也是左節點）
- 對祖父節點右旋
- 重新著色
左右案例（插入節點的父節點是左節點，插入節點是右節點）
- 對父節點左旋
- 對祖父節點右旋
- 重新染色
右右案例（插入節點的父節點是右節點，插入節點左節點）
- 對祖父節點左旋
- 重新染色
右左案例（插入節點的父節點是右節點，插入節點左節點）
- 對父節點右旋
- 對祖父節點左旋
- 重新著色
洗掉
與插入一樣，利用重新著色、旋轉來保持紅黑樹平衡， 在插入操作中，我們檢查叔叔節點的顏色來決定合適的情況，在洗掉操作中，我們檢查兄弟節點的顏色來決定合適的情況，
插入新元素后違反的主要屬性是兩個連續的紅色，在洗掉中，主要違反的性質是，子樹中黑色高度的變化，因為洗掉一個黑色節點可能會導致一個根到葉路徑的黑色高度降低，
洗掉是一個相當復雜的程序，為了方便理解，使用了雙黑的概念，當一個黑色節點被洗掉并被一個黑色子節點替換時，這個子節點被標記為雙黑（在本文中，雙黑意味著節點的黑高不再平衡，需要調整，這里只是一種叫法而已，并沒有什么其他的含義），這是會引起黑高改變的情況，也是我們需要重點關注的情況，
洗掉的詳細步驟：
1) 執行標準 BST 洗掉. 當我們在 BST 中執行標準洗掉操作時，最終將洗掉一個節點，它要么是葉子節點，要么只有一個子節點（對于內部節點，我們復制后繼節點，然后遞回呼叫后繼節點的洗掉，后繼節點始終是葉子節點或有一個孩子的節點），所以我們只需要處理節點是葉子節點或有一個子節點的情況，設 v 是要洗掉的節點，u 是替換 v 的子節點（注意，當 v 是葉子時，u 是 NULL，NULL 的顏色被認為是黑色），
2) 如果 u 或 v 是紅色，我們只需要將替換上來的節點標記為黑色（黑色高度沒有變化），請注意，u 和 v 不能都是紅色，因為 v 是 u 的父級，紅黑樹中不允許出現兩個連續的紅色，如下圖：
3) 如果 u 和 v 都是 Black，
3.1）如果u是根節點，什么都不需要做，（樹的黑高減 1）
3.2）出現雙黑，設 U 的兄弟節點為 s，
…… (a): 如果兄弟節點 s 是黑色并且兄弟的至少一個孩子是紅色，則執行旋轉，設 s 的紅色孩子是 r，根據 s 和 r 的位置，這種情況可以分為四個子情況，
…………..(i) 左左案例（s 是其父級的左孩子，r 是 s 的左孩子，或者 s 的兩個孩子都是紅色的），這是下圖所示的右右案例的鏡像，
………….. (ii) 左右案例（s 是其父母的左孩子，r 是右孩子），這是下圖所示的右左案例的鏡像，
……………(iii) 右右案例（s 是其父節點的右孩子，r 是 s 的右孩子，或者 s 的兩個孩子都是紅色的）
………….. (iv) 右左案例（s 是其父節點的右孩子，r 是 s 的左孩子）
..... (b): 如果兄弟 s 是黑色的，并且它的兩個孩子都是黑色的，則需要染色，如果父級 P 也是黑色，則需要父級遞回染色，
在這種情況下，如果父節點 P 為紅色，我們只需要將其設定為黑色，不再需要遞回，
..... (c): 如果兄弟是紅色的，則執行旋轉要向上移動舊兄弟節點，對舊兄弟節點和父級節點重新染色，新的兄弟節點一定是黑色的（見下圖，看圖容易明白），這時候，將會出現我們在 （a）或 （b）中分析過的情況，按照上面的分析步驟繼續就可以了，這種情況又可以分為兩個子情況，
………….. (i) 左案例（s 是其父級的左子級），這是下圖所示的右案例的鏡像，需要右旋父節點 p， ………….. (ii) 右案例（s 是其父母的右孩子），左旋父節點 p，
說明：本文限于篇幅，故而只展示部分的檔案截圖，完整的 Java面試學習檔案小編已經幫你整理好了，有需要的朋友可私信“666”領取演算法、樹、Java等面試學習資料哦！
最后
寫了好久終于寫完了，最后總結一下，
紅黑樹和 AVL 樹，一樣，本質都是二叉查找樹，兩種樹在保持平衡方面的能力不同，所以適合的場景也有所不同，同時，紅黑樹的應用比較廣泛，值得一提的是，Java 8中HashMap的實作也因為用紅黑樹取代鏈表，性能有所提升，
紅黑樹的插入洗掉比較復雜，不容易理解，研究這塊需要有耐心啊，哈哈，
文章中有什么有問題的地方，也歡迎指出，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/374615.html
標籤：其他
上一篇：判斷對稱日