【51CTO.com原創稿件】 學過數據結構都知道二叉樹的概念，而又有多種比較常見的二叉樹類型，比如完全二叉樹、滿二叉樹、二叉搜索樹、均衡二叉樹、完美二叉樹等。

[[274480]]

圖片來自 Pexels

今天我們要說的紅黑樹就是就是一棵非嚴格均衡的二叉樹，均衡二叉樹又是在二叉搜索樹的基礎上增加了自動維持平衡的性質，插入、搜索、刪除的效率都比較高。紅黑樹也是實現 TreeMap 存儲結構的基石。

二叉搜索樹

二叉搜索樹又叫二叉查找樹、二叉排序樹，我們先看一下典型的二叉搜索樹，這樣的二叉樹有何規則特點呢?

二叉搜索樹有如下幾個特點：

• 節點的左子樹小于節點本身
• 節點的右子樹大于節點本身
• 左右子樹同樣為二叉搜索樹

下圖就是一棵典型的二叉搜索樹：

二叉搜索樹是均衡二叉樹的基礎，我們看一下它的搜索步驟如何。我們要從二叉樹中找到值為 58 的節點。

第一步：首先查找到根節點，值為 60 的節點。

第二步：比較我們要找的值 58 與該節點的大小。

如果等于，那么恭喜，已經找到;如果小于，繼續找左子樹;如果大于，那么找右子樹。

很明顯 58<60，因此我們找到左子樹的節點 56，此時我們已經定位到了節點 56。

第三步：按照第二步的規則繼續找。

58>56 我們需要繼續找右子樹，定位到了右子樹節點 58，恭喜，此時我們已經找到了。

我們經過三步就已經找到了，其實就是我們平時所說的二分查找，這種二叉搜索樹好像查找效率很高，但同樣它也有缺陷，如下面這樣的二叉搜索樹。

看到這樣的二叉搜索樹是否很別扭，典型的大長腿瘸子，但它也是二叉搜索樹，如果我們要找值為 50 的節點，基本上和單鏈表查詢沒多大區別了，性能將大打折扣。

這個時候我們的均衡二叉樹就粉墨登場了，均衡二叉樹就是在二叉搜索樹的基礎上添加了自動維持平衡的性質。

上面的大長腿瘸子二叉搜索樹經過自動平衡后，可能就成為了下面這樣的二叉樹。

經過了自動平衡，再去找值為 50 的節點，查找性能將提升很多。紅黑樹就是非嚴格均衡的二叉搜索樹。

紅黑樹規則特點

紅黑樹具體有哪些規則特點呢?具體如下：

• 節點分為紅色或者黑色。
• 根節點必為黑色。
• 葉子節點都為黑色，且為 null。
• 連接紅色節點的兩個子節點都為黑色(紅黑樹不會出現相鄰的紅色節點)。
• 從任意節點出發，到其每個葉子節點的路徑中包含相同數量的黑色節點。
• 新加入到紅黑樹的節點為紅色節點。

規則看著好像挺多，沒錯，因為紅黑樹也是均衡二叉樹，需要具備自動維持平衡的性質，上面的 6 條就是紅黑樹給出的自動維持平衡所需要具備的規則。

我們看一看一個典型的紅黑樹到底是什么樣兒?

首先解讀一下規則，除了字面上看到的意思，還隱藏了哪些意思呢?

①從根節點到葉子節點的最長路徑不大于最短路徑的 2 倍

怎么樣的路徑算最短路徑?從規則 5 中，我們知道從根節點到每個葉子節點的黑色節點數量是一樣的，那么純由黑色節點組成的路徑就是最短路徑。

什么樣的路徑算是最長路徑?根據規則 4 和規則 3，若有紅色節點，則必然有一個連接的黑色節點，當紅色節點和黑色節點數量相同時，就是最長路徑，也就是黑色節點(或紅色節點)*2。

②為什么說新加入到紅黑樹中的節點為紅色節點

從規則 4 中知道，當前紅黑樹中從根節點到每個葉子節點的黑色節點數量是一樣的，此時假如新的是黑色節點的話，必然破壞規則。

但加入紅色節點卻不一定，除非其父節點就是紅色節點，因此加入紅色節點，破壞規則的可能性小一些，下面我們也會舉例來說明。

什么情況下，紅黑樹的結構會被破壞呢?破壞后又怎么維持平衡，維持平衡主要通過兩種方式【變色】和【旋轉】，【旋轉】又分【左旋】和【右旋】，兩種方式可相互結合。

下面我們從插入和刪除兩種場景來舉例說明。

紅黑樹節點插入

當我們插入值為 66 的節點時，紅黑樹變成了這樣：

很明顯，這個時候結構依然遵循著上述 6 大規則，無需啟動自動平衡機制調整節點平衡狀態。

如果再向里面插入值為 51 的節點，這個時候紅黑樹變成了這樣：

很明顯現在的結構不遵循規則 4 了，這個時候就需要啟動自動平衡機制調整節點平衡狀態。

變色

我們可以通過變色的方式，使結構滿足紅黑樹的規則：

• 首先解決結構不遵循規則 4 這一點(紅色節點相連，節點 49-51)，需將節點 49 改為黑色。
• 此時我們發現又違反了規則 5(56-49-51-XX 路徑中黑色節點超過了其他路徑)，那么我們將節點 45 改為紅色節點。
• 哈哈，妹的，又違反了規則 4(紅色節點相連，節點 56-45-43)，那么我們將節點 56 和節點 43 改為黑色節點。
• 但是我們發現此時又違反了規則 5(60-56-XX 路徑的黑色節點比 60-68-XX 的黑色節點多)，因此我們需要調整節點 68 為黑色。
• 完成!

最終調整完成后的樹為：

但并不是什么時候都那么幸運，可以直接通過變色就達成目的，大多數時候還需要通過旋轉來解決。

如在下面這棵樹的基礎上，加入節點 65：

插入節點 65 后進行以下步驟：

這個時候，你會發現對于節點 64 無論是紅色節點還是黑色節點，都會違反規則 5，路徑中的黑色節點始終無法達成一致，這個時候僅通過【變色】已經無法達成目的。

我們需要通過旋轉操作，當然【旋轉】操作一般還需要搭配【變色】操作。旋轉包括【左旋】和【右旋】。

左旋：逆時針旋轉兩個節點，讓一個節點被其右子節點取代，而該節點成為右子節點的左子節點。

左旋操作步驟如下：首先斷開節點 PL 與右子節點 G 的關系，同時將其右子節點的引用指向節點 C2;然后斷開節點 G 與左子節點 C2 的關系，同時將 G 的左子節點的應用指向節點 PL。

右旋：順時針旋轉兩個節點，讓一個節點被其左子節點取代，而該節點成為左子節點的右子節點。

右旋操作步驟如下：首先斷開節點 G 與左子節點 PL 的關系，同時將其左子節點的引用指向節點 C2;然后斷開節點 PL 與右子節點 C2 的關系，同時將 PL 的右子節點的應用指向節點 G。

無法通過變色而進行旋轉的場景分為以下四種：

左左節點旋轉

這種情況下，父節點和插入的節點都是左節點，如下圖(旋轉原始圖1)這種情況下，我們要插入節點 65。

規則如下：以祖父節點【右旋】，搭配【變色】。

按照規則，步驟如下：

左右節點旋轉

這種情況下，父節點是左節點，插入的節點是右節點，在旋轉原始圖 1 中，我們要插入節點 67。

規則如下：先父節點【左旋】，然后祖父節點【右旋】，搭配【變色】。

按照規則，步驟如下：

右左節點旋轉

這種情況下，父節點是右節點，插入的節點是左節點，如下圖(旋轉原始圖 2)這種情況，我們要插入節點 68。

規則如下：先父節點【右旋】，然后祖父節點【左旋】，搭配【變色】。

按照規則，步驟如下：

右右節點旋轉

這種情況下，父節點和插入的節點都是右節點，在旋轉原始圖 2 中，我們要插入節點 70。

規則如下：以祖父節點【左旋】，搭配【變色】。

按照規則，步驟如下：

紅黑樹插入總結

紅黑樹插入總結如下圖：

紅黑樹節點刪除

相比較于紅黑樹的節點插入，刪除節點更為復雜，我們從子節點是否為 null 和紅色為思考維度來討論。

子節點至少有一個為 null

當待刪除的節點的子節點至少有一個為 null 節點時，刪除了該節點后，將其有值的節點取代當前節點即可。

若都為 null，則將當前節點設置為 null，當然如果違反規則了，則按需調整，如【變色】以及【旋轉】。

子節點都是非 null 節點

這種情況下，第一步：找到該節點的前驅或者后繼。

前驅：左子樹中值最大的節點(可得出其最多只有一個非 null 子節點，可能都為 null)。

后繼：右子樹中值最小的節點(可得出其最多只有一個非 null 子節點，可能都為 null)。

前驅和后繼都是值最接近該節點值的節點，類似于該節點.prev=前驅，該節點.next=后繼。

第二步：將前驅或者后繼的值復制到該節點中，然后刪掉前驅或者后繼。

如果刪除的是左節點，則將前驅的值復制到該節點中，然后刪除前驅;如果刪除的是右節點，則將后繼的值復制到該節點中，然后刪除后繼。

這相當于是一種“取巧”的方法，我們刪除節點的目的是使該節點的值在紅黑樹上不存在。

因此專注于該目的，我們并不關注刪除節點時是否真是我們想刪除的那個節點，同時我們也不需考慮樹結構的變化，因為樹的結構本身就會因為自動平衡機制而經常進行調整。

前面我們已經說了，我們要刪除的實際上是前驅或者后繼，因此我們就以前驅為主線來講解。

后繼的學習可參考前驅，包括下面幾種情況：

①前驅為黑色節點，并且有一個非 null 子節點

分析：因為要刪除的是左節點 64，找到該節點的前驅 63;然后用前驅的值 63替換待刪除節點的值 64，此時兩個節點(待刪除節點和前驅)的值都為 63;

刪除前驅 63，此時成為上圖過程中間環節，但我們發現其不符合紅黑樹規則 4，因此需要進行自動平衡調整。這里直接通過【變色】即可完成。

②前驅為黑色節點，同時子節點都為 null

分析：因為要刪除的是左節點 64，找到該節點的前驅 63;然后用前驅的值 63 替換待刪除節點的值 64，此時兩個節點(待刪除節點和前驅)的值都為 63。

刪除前驅 63，此時成為上圖過程中間環節，但我們發現其不符合紅黑樹規則 5，因此需要進行自動平衡調整。這里直接通過【變色】即可完成。

③前驅為紅色節點，同時子節點都為 null

分析：因為要刪除的是左節點 64，找到該節點的前驅 63;然后用前驅的值 63替換待刪除節點的值 64，此時兩個節點(待刪除節點和前驅)的值都為 63;刪除前驅 63，樹的結構并沒有打破規則。

紅黑樹刪除總結

紅黑樹刪除的情況比較多，但也就存在以下情況：

• 刪除的是根節點，則直接將根節點置為 null。
• 待刪除節點的左右子節點都為 null，刪除時將該節點置為 null。
• 待刪除節點的左右子節點有一個有值，則用有值的節點替換該節點即可。
• 待刪除節點的左右子節點都不為 null，則找前驅或者后繼，將前驅或者后繼的值復制到該節點中，然后刪除前驅或者后繼。
• 節點刪除后可能會造成紅黑樹的不平衡，這時我們需通過【變色】+【旋轉】的方式來調整，使之平衡，上面也給出了例子，建議大家多多練習，而不必背下來。

總結

本文主要介紹了紅黑樹的相關原理，首先紅黑樹的基礎二叉搜索樹，我們先簡單說了一下二叉搜索樹，并且講了一下搜索的流程。

然后就針對紅黑樹的六大規則特點，紅黑樹的插入操作，刪除操作，都使用了大量的圖形來加以說明。

技術都是練出來的，有時候很多似是而非的地方，當動筆去寫的時候，其實很好理解。

紅黑樹的使用非常廣泛，如 TreeMap 和 TreeSet 都是基于紅黑樹實現的，而 JDK8 中 HashMap 當鏈表長度大于 8 時也會轉化為紅黑樹。

紅黑樹比較復雜，本人也是還在學習過程中，如果有不對的地方請批評指正，望共同進步謝謝。

作者：梁洪

簡介：網名工匠初心，熱愛技術，喜歡鉆研與分享，6 年 Java 開發經驗，專注于 Java 以及 Spring 生態圈，同時也喜歡研究物聯網、大數據、AI 等前沿技術，帶過 15 人以下的小團隊，做過項目管理，現在是一家軟件公司的部門經理。

【51CTO原創稿件，合作站點轉載請注明原文作者和出處為51CTO.com】