【51CTO.com原創(chuàng)稿件】 學(xué)過數(shù)據(jù)結(jié)構(gòu)都知道二叉樹的概念，而又有多種比較常見的二叉樹類型，比如完全二叉樹、滿二叉樹、二叉搜索樹、均衡二叉樹、完美二叉樹等。

[[274480]]

圖片來自 Pexels

今天我們要說的紅黑樹就是就是一棵非嚴(yán)格均衡的二叉樹，均衡二叉樹又是在二叉搜索樹的基礎(chǔ)上增加了自動維持平衡的性質(zhì)，插入、搜索、刪除的效率都比較高。紅黑樹也是實現(xiàn) TreeMap 存儲結(jié)構(gòu)的基石。

二叉搜索樹

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

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

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

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

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

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

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

如果等于，那么恭喜，已經(jīng)找到;如果小于，繼續(xù)找左子樹;如果大于，那么找右子樹。

很明顯 58<60，因此我們找到左子樹的節(jié)點 56，此時我們已經(jīng)定位到了節(jié)點 56。

第三步：按照第二步的規(guī)則繼續(xù)找。

58>56 我們需要繼續(xù)找右子樹，定位到了右子樹節(jié)點 58，恭喜，此時我們已經(jīng)找到了。

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

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

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

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

經(jīng)過了自動平衡，再去找值為 50 的節(jié)點，查找性能將提升很多。紅黑樹就是非嚴(yán)格均衡的二叉搜索樹。

紅黑樹規(guī)則特點

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

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

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

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

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

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

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

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

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

從規(guī)則 4 中知道，當(dāng)前紅黑樹中從根節(jié)點到每個葉子節(jié)點的黑色節(jié)點數(shù)量是一樣的，此時假如新的是黑色節(jié)點的話，必然破壞規(guī)則。

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

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

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

紅黑樹節(jié)點插入

當(dāng)我們插入值為 66 的節(jié)點時，紅黑樹變成了這樣：

很明顯，這個時候結(jié)構(gòu)依然遵循著上述 6 大規(guī)則，無需啟動自動平衡機制調(diào)整節(jié)點平衡狀態(tài)。

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

很明顯現(xiàn)在的結(jié)構(gòu)不遵循規(guī)則 4 了，這個時候就需要啟動自動平衡機制調(diào)整節(jié)點平衡狀態(tài)。

變色

我們可以通過變色的方式，使結(jié)構(gòu)滿足紅黑樹的規(guī)則：

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

最終調(diào)整完成后的樹為：

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

如在下面這棵樹的基礎(chǔ)上，加入節(jié)點 65：

插入節(jié)點 65 后進(jìn)行以下步驟：

這個時候，你會發(fā)現(xiàn)對于節(jié)點 64 無論是紅色節(jié)點還是黑色節(jié)點，都會違反規(guī)則 5，路徑中的黑色節(jié)點始終無法達(dá)成一致，這個時候僅通過【變色】已經(jīng)無法達(dá)成目的。

我們需要通過旋轉(zhuǎn)操作，當(dāng)然【旋轉(zhuǎn)】操作一般還需要搭配【變色】操作。旋轉(zhuǎn)包括【左旋】和【右旋】。

左旋：逆時針旋轉(zhuǎn)兩個節(jié)點，讓一個節(jié)點被其右子節(jié)點取代，而該節(jié)點成為右子節(jié)點的左子節(jié)點。

左旋操作步驟如下：首先斷開節(jié)點 PL 與右子節(jié)點 G 的關(guān)系，同時將其右子節(jié)點的引用指向節(jié)點 C2;然后斷開節(jié)點 G 與左子節(jié)點 C2 的關(guān)系，同時將 G 的左子節(jié)點的應(yīng)用指向節(jié)點 PL。

右旋：順時針旋轉(zhuǎn)兩個節(jié)點，讓一個節(jié)點被其左子節(jié)點取代，而該節(jié)點成為左子節(jié)點的右子節(jié)點。

右旋操作步驟如下：首先斷開節(jié)點 G 與左子節(jié)點 PL 的關(guān)系，同時將其左子節(jié)點的引用指向節(jié)點 C2;然后斷開節(jié)點 PL 與右子節(jié)點 C2 的關(guān)系，同時將 PL 的右子節(jié)點的應(yīng)用指向節(jié)點 G。

無法通過變色而進(jìn)行旋轉(zhuǎn)的場景分為以下四種：

左左節(jié)點旋轉(zhuǎn)

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

規(guī)則如下：以祖父節(jié)點【右旋】，搭配【變色】。

按照規(guī)則，步驟如下：

左右節(jié)點旋轉(zhuǎn)

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

規(guī)則如下：先父節(jié)點【左旋】，然后祖父節(jié)點【右旋】，搭配【變色】。

按照規(guī)則，步驟如下：

右左節(jié)點旋轉(zhuǎn)

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

規(guī)則如下：先父節(jié)點【右旋】，然后祖父節(jié)點【左旋】，搭配【變色】。

按照規(guī)則，步驟如下：

右右節(jié)點旋轉(zhuǎn)

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

規(guī)則如下：以祖父節(jié)點【左旋】，搭配【變色】。

按照規(guī)則，步驟如下：

紅黑樹插入總結(jié)

紅黑樹插入總結(jié)如下圖：

紅黑樹節(jié)點刪除

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

子節(jié)點至少有一個為 null

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

若都為 null，則將當(dāng)前節(jié)點設(shè)置為 null，當(dāng)然如果違反規(guī)則了，則按需調(diào)整，如【變色】以及【旋轉(zhuǎn)】。

子節(jié)點都是非 null 節(jié)點

這種情況下，第一步：找到該節(jié)點的前驅(qū)或者后繼。

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

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

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

第二步：將前驅(qū)或者后繼的值復(fù)制到該節(jié)點中，然后刪掉前驅(qū)或者后繼。

如果刪除的是左節(jié)點，則將前驅(qū)的值復(fù)制到該節(jié)點中，然后刪除前驅(qū);如果刪除的是右節(jié)點，則將后繼的值復(fù)制到該節(jié)點中，然后刪除后繼。

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

因此專注于該目的，我們并不關(guān)注刪除節(jié)點時是否真是我們想刪除的那個節(jié)點，同時我們也不需考慮樹結(jié)構(gòu)的變化，因為樹的結(jié)構(gòu)本身就會因為自動平衡機制而經(jīng)常進(jìn)行調(diào)整。

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

后繼的學(xué)習(xí)可參考前驅(qū)，包括下面幾種情況：

①前驅(qū)為黑色節(jié)點，并且有一個非 null 子節(jié)點

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

刪除前驅(qū) 63，此時成為上圖過程中間環(huán)節(jié)，但我們發(fā)現(xiàn)其不符合紅黑樹規(guī)則 4，因此需要進(jìn)行自動平衡調(diào)整。這里直接通過【變色】即可完成。

②前驅(qū)為黑色節(jié)點，同時子節(jié)點都為 null

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

刪除前驅(qū) 63，此時成為上圖過程中間環(huán)節(jié)，但我們發(fā)現(xiàn)其不符合紅黑樹規(guī)則 5，因此需要進(jìn)行自動平衡調(diào)整。這里直接通過【變色】即可完成。

③前驅(qū)為紅色節(jié)點，同時子節(jié)點都為 null

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

紅黑樹刪除總結(jié)

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

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

總結(jié)

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

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

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

紅黑樹的使用非常廣泛，如 TreeMap 和 TreeSet 都是基于紅黑樹實現(xiàn)的，而 JDK8 中 HashMap 當(dāng)鏈表長度大于 8 時也會轉(zhuǎn)化為紅黑樹。

紅黑樹比較復(fù)雜，本人也是還在學(xué)習(xí)過程中，如果有不對的地方請批評指正，望共同進(jìn)步謝謝。

作者：梁洪

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

【51CTO原創(chuàng)稿件，合作站點轉(zhuǎn)載請注明原文作者和出處為51CTO.com】