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

[[274480]]

圖片來(lái)自 Pexels

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

二叉搜索樹

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

二叉搜索樹有如下幾個(gè)特點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

紅黑樹規(guī)則特點(diǎn)

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

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

規(guī)則看著好像挺多，沒(méi)錯(cuò)，因?yàn)榧t黑樹也是均衡二叉樹，需要具備自動(dòng)維持平衡的性質(zhì)，上面的 6 條就是紅黑樹給出的自動(dòng)維持平衡所需要具備的規(guī)則。

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

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

①?gòu)母?jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)路徑不大于最短路徑的 2 倍

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

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

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

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

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

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

下面我們從插入和刪除兩種場(chǎng)景來(lái)舉例說(shuō)明。

紅黑樹節(jié)點(diǎn)插入

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

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

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

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

變色

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

紅黑樹插入總結(jié)

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

紅黑樹節(jié)點(diǎn)刪除

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

子節(jié)點(diǎn)至少有一個(gè)為 null

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

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

子節(jié)點(diǎn)都是非 null 節(jié)點(diǎn)

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

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

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

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

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

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

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

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

前面我們已經(jīng)說(shuō)了，我們要?jiǎng)h除的實(shí)際上是前驅(qū)或者后繼，因此我們就以前驅(qū)為主線來(lái)講解。

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

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

分析：因?yàn)橐獎(jiǎng)h除的是左節(jié)點(diǎn) 64，找到該節(jié)點(diǎn)的前驅(qū) 63;然后用前驅(qū)的值 63替換待刪除節(jié)點(diǎn)的值 64，此時(shí)兩個(gè)節(jié)點(diǎn)(待刪除節(jié)點(diǎn)和前驅(qū))的值都為 63;

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

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

分析：因?yàn)橐獎(jiǎng)h除的是左節(jié)點(diǎn) 64，找到該節(jié)點(diǎn)的前驅(qū) 63;然后用前驅(qū)的值 63 替換待刪除節(jié)點(diǎn)的值 64，此時(shí)兩個(gè)節(jié)點(diǎn)(待刪除節(jié)點(diǎn)和前驅(qū))的值都為 63。

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

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

分析：因?yàn)橐獎(jiǎng)h除的是左節(jié)點(diǎn) 64，找到該節(jié)點(diǎn)的前驅(qū) 63;然后用前驅(qū)的值 63替換待刪除節(jié)點(diǎn)的值 64，此時(shí)兩個(gè)節(jié)點(diǎn)(待刪除節(jié)點(diǎn)和前驅(qū))的值都為 63;刪除前驅(qū) 63，樹的結(jié)構(gòu)并沒(méi)有打破規(guī)則。

紅黑樹刪除總結(jié)

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

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

總結(jié)

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

然后就針對(duì)紅黑樹的六大規(guī)則特點(diǎn)，紅黑樹的插入操作，刪除操作，都使用了大量的圖形來(lái)加以說(shuō)明。

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

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

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

作者：梁洪

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

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