一文詳解紅黑樹

一、紅黑樹簡(jiǎn)介

紅黑樹是一種自平衡的二叉查找樹，是一種高效的查找樹。它是由 Rudolf Bayer 于1972年發(fā)明，在當(dāng)時(shí)被稱為對(duì)稱二叉 B 樹(symmetric binary B-trees)。后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的紅黑樹。紅黑樹具有良好的效率，它可在 O(logN) 時(shí)間內(nèi)完成查找、增加、刪除等操作。因此，紅黑樹在業(yè)界應(yīng)用很廣泛，比如 Java 中的 TreeMap，JDK 1.8 中的 HashMap、C++ STL 中的 map 均是基于紅黑樹結(jié)構(gòu)實(shí)現(xiàn)的。考慮到紅黑樹是一種被廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)，所以我們很有必要去弄懂它。

“

二、紅黑樹的性質(zhì)

學(xué)過二叉查找樹的同學(xué)都知道，普通的二叉查找樹在極端情況下可退化成鏈表，此時(shí)的增刪查效率都會(huì)比較低下。為了避免這種情況，就出現(xiàn)了一些自平衡的查找樹，比如 AVL，紅黑樹等。這些自平衡的查找樹通過定義一些性質(zhì)，將任意節(jié)點(diǎn)的左右子樹高度差控制在規(guī)定范圍內(nèi)，以達(dá)到平衡狀態(tài)。以紅黑樹為例，紅黑樹通過如下的性質(zhì)定義實(shí)現(xiàn)自平衡：

節(jié)點(diǎn)是紅色或黑色。

根是黑色。

所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。

每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。）

從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)（簡(jiǎn)稱黑高）。

有了上面的幾個(gè)性質(zhì)作為限制，即可避免二叉查找樹退化成單鏈表的情況。但是，僅僅避免這種情況還不夠，這里還要考慮某個(gè)節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)路徑長(zhǎng)度的問題。如果某些路徑長(zhǎng)度過長(zhǎng)，那么，在對(duì)這些路徑上的及誒單進(jìn)行增刪查操作時(shí)，效率也會(huì)大大降低。這個(gè)時(shí)候性質(zhì)4和性質(zhì)5用途就凸顯了，有了這兩個(gè)性質(zhì)作為約束，即可保證任意節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)路徑最長(zhǎng)不會(huì)超過最短路徑的2倍。原因如下：

當(dāng)某條路徑最短時(shí)，這條路徑必然都是由黑色節(jié)點(diǎn)構(gòu)成。當(dāng)某條路徑長(zhǎng)度最長(zhǎng)時(shí)，這條路徑必然是由紅色和黑色節(jié)點(diǎn)相間構(gòu)成（性質(zhì)4限定了不能出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）。而性質(zhì)5又限定了從任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的所有路徑必須包含相同數(shù)量的黑色節(jié)點(diǎn)。此時(shí)，在路徑最長(zhǎng)的情況下，路徑上紅色節(jié)點(diǎn)數(shù)量 = 黑色節(jié)點(diǎn)數(shù)量。該路徑長(zhǎng)度為兩倍黑色節(jié)點(diǎn)數(shù)量，也就是最短路徑長(zhǎng)度的2倍。舉例說明一下，請(qǐng)看下圖：

上圖畫出了從根節(jié)點(diǎn) M 出發(fā)的到其葉子節(jié)點(diǎn)的最長(zhǎng)和最短路徑。這里偷懶只畫出了兩條最長(zhǎng)路徑，實(shí)際上最長(zhǎng)路徑有4條，分別為：

M -> Q -> O -> N

M -> Q -> O -> p

M -> Q -> Y -> X

M -> Q -> Y -> Z

長(zhǎng)度為4，最短路徑為 M -> E，長(zhǎng)度為2。最長(zhǎng)路徑的長(zhǎng)度正好為最短路徑長(zhǎng)度的2倍。

前面說了關(guān)于紅黑樹的一些性質(zhì)，這里還需要補(bǔ)充一些其他方面的東西。在紅黑樹簡(jiǎn)介一節(jié)中說到紅黑樹被發(fā)明出來的時(shí)候并不叫紅黑樹，而是叫做對(duì)稱二叉 B 樹，從名字中可發(fā)現(xiàn)紅黑樹和 B 樹（這里指的是2-3樹）或許有一定的關(guān)聯(lián)，事實(shí)也正是如此。如果對(duì)紅黑樹的性質(zhì)稍加修改，就能讓紅黑樹和B樹形成一一對(duì)應(yīng)的關(guān)系。關(guān)于紅黑樹和 B 樹關(guān)系的細(xì)節(jié)這里不展開說明了，有興趣的同學(xué)可以參考《算法》第4版，那本書上講的很透徹。

“

三、紅黑樹操作

紅黑樹的基本操作和其他樹形結(jié)構(gòu)一樣，一般都包括查找、插入、刪除等操作。前面說到，紅黑樹是一種自平衡的二叉查找樹，既然是二叉查找樹的一種，那么查找過程和二叉查找樹一樣，比較簡(jiǎn)單，這里不再贅述。相對(duì)于查找操作，紅黑樹的插入和刪除操作就要復(fù)雜的多。尤其是刪除操作，要處理的情況比較多，不過大家如果靜下心來去看，會(huì)發(fā)現(xiàn)其實(shí)也沒想的那么難。好了，廢話就說到這，接下來步入正題吧。

3.1 旋轉(zhuǎn)操作

在分析插入和刪除操作前，這里需要插個(gè)隊(duì)，先說明一下旋轉(zhuǎn)操作，這個(gè)操作在后續(xù)操作中都會(huì)用得到。旋轉(zhuǎn)操作分為左旋和右旋，左旋是將某個(gè)節(jié)點(diǎn)旋轉(zhuǎn)為其右孩子的左孩子，而右旋是節(jié)點(diǎn)旋轉(zhuǎn)為其左孩子的右孩子。這話聽起來有點(diǎn)繞，所以還是請(qǐng)看下圖：

上圖包含了左旋和右旋的示意圖，這里以右旋為例進(jìn)行說明，右旋節(jié)點(diǎn) M 的步驟如下：

1、將節(jié)點(diǎn) M 的左孩子引用指向節(jié)點(diǎn) E 的右孩子

2、將節(jié)點(diǎn) E 的右孩子引用指向節(jié)點(diǎn) M，完成旋轉(zhuǎn)

上面分析了右旋操作，左旋操作與此類似，大家有興趣自己畫圖試試吧，這里不再贅述了。旋轉(zhuǎn)操作本身并不復(fù)雜，這里先分析到這吧。

3.2 插入

紅黑樹的插入過程和二叉查找樹插入過程基本類似，不同的地方在于，紅黑樹插入新節(jié)點(diǎn)后，需要進(jìn)行調(diào)整，以滿足紅黑樹的性質(zhì)。性質(zhì)1規(guī)定紅黑樹節(jié)點(diǎn)的顏色要么是紅色要么是黑色，那么在插入新節(jié)點(diǎn)時(shí)，這個(gè)節(jié)點(diǎn)應(yīng)該是紅色還是黑色呢？答案是紅色，原因也不難理解。如果插入的節(jié)點(diǎn)是黑色，那么這個(gè)節(jié)點(diǎn)所在路徑比其他路徑多出一個(gè)黑色節(jié)點(diǎn)，這個(gè)調(diào)整起來會(huì)比較麻煩（參考紅黑樹的刪除操作，就知道為啥多一個(gè)或少一個(gè)黑色節(jié)點(diǎn)時(shí)，調(diào)整起來這么麻煩了）。如果插入的節(jié)點(diǎn)是紅色，此時(shí)所有路徑上的黑色節(jié)點(diǎn)數(shù)量不變，僅可能會(huì)出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)的情況。這種情況下，通過變色和旋轉(zhuǎn)進(jìn)行調(diào)整即可，比之前的簡(jiǎn)單多了。

接下來，將分析插入紅色節(jié)點(diǎn)后紅黑樹的情況。這里假設(shè)要插入的節(jié)點(diǎn)為 N，N 的父節(jié)點(diǎn)為 P，祖父節(jié)點(diǎn)為 G，叔叔節(jié)點(diǎn)為 U。插入紅色節(jié)點(diǎn)后，會(huì)出現(xiàn)5種情況，分別如下：

情況一：

插入的新節(jié)點(diǎn) N 是紅黑樹的根節(jié)點(diǎn)，這種情況下，我們把節(jié)點(diǎn) N 的顏色由紅色變?yōu)楹谏?，性質(zhì)2（根是黑色）被滿足。同時(shí) N 被染成黑色后，紅黑樹所有路徑上的黑色節(jié)點(diǎn)數(shù)量增加一個(gè)，性質(zhì)5（從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)）仍然被滿足。

情況二：

N 的父節(jié)點(diǎn)是黑色，這種情況下，性質(zhì)4（每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)）和性質(zhì)5沒有受到影響，不需要調(diào)整。

情況三：N 的父節(jié)點(diǎn)是紅色（節(jié)點(diǎn) P 為紅色，其父節(jié)點(diǎn)必然為黑色），叔叔節(jié)點(diǎn) U 也是紅色。由于 P 和 N 均為紅色，所有性質(zhì)4被打破，此時(shí)需要進(jìn)行調(diào)整。這種情況下，先將 P 和 U 的顏色染成黑色，再將 G 的顏色染成紅色。此時(shí)經(jīng)過 G 的路徑上的黑色節(jié)點(diǎn)數(shù)量不變，性質(zhì)5仍然滿足。但需要注意的是 G 被染成紅色后，可能會(huì)和它的父節(jié)點(diǎn)形成連續(xù)的紅色節(jié)點(diǎn)，此時(shí)需要遞歸向上調(diào)整。

情況四：

N 的父節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)為黑色。節(jié)點(diǎn) N 是 P 的右孩子，且節(jié)點(diǎn) P 是 G 的左孩子。此時(shí)先對(duì)節(jié)點(diǎn) P 進(jìn)行左旋，調(diào)整 N 與 P 的位置。接下來按照情況五進(jìn)行處理，以恢復(fù)性質(zhì)4。

這里需要特別說明一下，上圖中的節(jié)點(diǎn) N 并非是新插入的節(jié)點(diǎn)。當(dāng) P 為紅色時(shí)，P 有兩個(gè)孩子節(jié)點(diǎn)，且孩子節(jié)點(diǎn)均為黑色，這樣從 G 出發(fā)到各葉子節(jié)點(diǎn)路徑上的黑色節(jié)點(diǎn)數(shù)量才能保持一致。既然 P 已經(jīng)有兩個(gè)孩子了，所以 N 不是新插入的節(jié)點(diǎn)。情況四是由以 N 為根節(jié)點(diǎn)的子樹中插入了新節(jié)點(diǎn)，經(jīng)過調(diào)整后，導(dǎo)致 N 被變?yōu)榧t色，進(jìn)而導(dǎo)致了情況四的出現(xiàn)?？紤]下面這種情況（PR 節(jié)點(diǎn)就是上圖的 N 節(jié)點(diǎn)）：

如上圖，插入節(jié)點(diǎn) N 并按情況三處理。此時(shí) PR 被染成了紅色，與 P 節(jié)點(diǎn)形成了連續(xù)的紅色節(jié)點(diǎn)，這個(gè)時(shí)候就需按情況四再次進(jìn)行調(diào)整。

情況五：

N 的父節(jié)點(diǎn)為紅色，叔叔節(jié)點(diǎn)為黑色。N 是 P 的左孩子，且節(jié)點(diǎn) P 是 G 的左孩子。此時(shí)對(duì) G 進(jìn)行右旋，調(diào)整 P 和 G 的位置，并互換顏色。經(jīng)過這樣的調(diào)整后，性質(zhì)4被恢復(fù)，同時(shí)也未破壞性質(zhì)5。

插入總結(jié)

上面五種情況中，情況一和情況二比較簡(jiǎn)單，情況三、四、五稍復(fù)雜。但如果細(xì)心觀察，會(huì)發(fā)現(xiàn)這三種情況的區(qū)別在于叔叔節(jié)點(diǎn)的顏色，如果叔叔節(jié)點(diǎn)為紅色，直接變色即可。如果叔叔節(jié)點(diǎn)為黑色，則需要選選擇，再交換顏色。當(dāng)把這三種情況的圖畫在一起就區(qū)別就比較容易觀察了，如下圖：

3.3 刪除

相較于插入操作，紅黑樹的刪除操作則要更為復(fù)雜一些。刪除操作首先要確定待刪除節(jié)點(diǎn)有幾個(gè)孩子，如果有兩個(gè)孩子，不能直接刪除該節(jié)點(diǎn)。而是要先找到該節(jié)點(diǎn)的前驅(qū)（該節(jié)點(diǎn)左子樹中最大的節(jié)點(diǎn)）或者后繼（該節(jié)點(diǎn)右子樹中最小的節(jié)點(diǎn)），然后將前驅(qū)或者后繼的值復(fù)制到要?jiǎng)h除的節(jié)點(diǎn)中，最后再將前驅(qū)或后繼刪除。由于前驅(qū)和后繼至多只有一個(gè)孩子節(jié)點(diǎn)，這樣我們就把原來要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)孩子的問題轉(zhuǎn)化為只有一個(gè)孩子節(jié)點(diǎn)的問題，問題被簡(jiǎn)化了一些。我們并不關(guān)心最終被刪除的節(jié)點(diǎn)是否是我們開始想要?jiǎng)h除的那個(gè)節(jié)點(diǎn)，只要節(jié)點(diǎn)里的值最終被刪除就行了，至于樹結(jié)構(gòu)如何變化，這個(gè)并不重要。

紅黑樹刪除操作的復(fù)雜度在于刪除節(jié)點(diǎn)的顏色，當(dāng)刪除的節(jié)點(diǎn)是紅色時(shí)，直接拿其孩子節(jié)點(diǎn)補(bǔ)空位即可。因?yàn)閯h除紅色節(jié)點(diǎn)，性質(zhì)5（從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)）仍能夠被滿足。當(dāng)刪除的節(jié)點(diǎn)是黑色時(shí)，那么所有經(jīng)過該節(jié)點(diǎn)的路徑上的黑節(jié)點(diǎn)數(shù)量少了一個(gè)，破壞了性質(zhì)5。如果該節(jié)點(diǎn)的孩子為紅色，直接拿孩子節(jié)點(diǎn)替換被刪除的節(jié)點(diǎn)，并將孩子節(jié)點(diǎn)染成黑色，即可恢復(fù)性質(zhì)5。但如果孩子節(jié)點(diǎn)為黑色，處理起來就要復(fù)雜的多。分為6種情況，下面會(huì)展開說明。

在展開說明之前，我們先做一些假設(shè)，方便說明。這里假設(shè)最終被刪除的節(jié)點(diǎn)為X（至多只有一個(gè)孩子節(jié)點(diǎn)），其孩子節(jié)點(diǎn)為N，X的兄弟節(jié)點(diǎn)為S，S的左節(jié)點(diǎn)為 SL，右節(jié)點(diǎn)為 SR。接下來討論是建立在節(jié)點(diǎn) X 被刪除，節(jié)點(diǎn) N 替換X的基礎(chǔ)上進(jìn)行的。這里說明把被刪除的節(jié)點(diǎn)X特地拎出來說一下的原因是防止大家誤以為節(jié)點(diǎn)N會(huì)被刪除，不然后面就會(huì)看不明白。

在上面的基礎(chǔ)上，接下來就可以展開討論了。紅黑樹刪除有6種情況，分別是：

情況一：

N 是新的根。在這種情形下，我們就做完了。我們從所有路徑去除了一個(gè)黑色節(jié)點(diǎn)，而新根是黑色的，所以性質(zhì)都保持著。

上面是維基百科中關(guān)于紅黑樹刪除的情況一說明，由于沒有配圖，看的有點(diǎn)暈。經(jīng)過思考，我覺得可能會(huì)是下面這種情形：

要?jiǎng)h除的節(jié)點(diǎn) X 是根節(jié)點(diǎn)，且左右孩子節(jié)點(diǎn)均為空節(jié)點(diǎn)，此時(shí)將節(jié)點(diǎn) X 用空節(jié)點(diǎn)替換完成刪除操作。

可能還有其他情形，大家如果知道，煩請(qǐng)告知。

情況二：

S 為紅色，其他節(jié)點(diǎn)為黑色。這種情況下可以對(duì) N 的父節(jié)點(diǎn)進(jìn)行左旋操作，然后互換 P 與 S 顏色。但這并未結(jié)束，經(jīng)過節(jié)點(diǎn) P 和 N 的路徑刪除前有3個(gè)黑色節(jié)點(diǎn)（P -> X -> N），現(xiàn)在只剩兩個(gè)了（P -> N）。比未經(jīng)過 N 的路徑少一個(gè)黑色節(jié)點(diǎn)，性質(zhì)5仍不滿足，還需要繼續(xù)調(diào)整。不過此時(shí)可以按照情況四、五、六進(jìn)行調(diào)整。

情況三：

N 的父節(jié)點(diǎn)，兄弟節(jié)點(diǎn) S 和 S 的孩子節(jié)點(diǎn)均為黑色。這種情況下可以簡(jiǎn)單的把 S 染成紅色，所有經(jīng)過 S 的路徑比之前少了一個(gè)黑色節(jié)點(diǎn)，這樣經(jīng)過 N 的路徑和經(jīng)過 S 的路徑黑色節(jié)點(diǎn)數(shù)量一致了。但經(jīng)過 P 的路徑比不經(jīng)過 P 的路徑少一個(gè)黑色節(jié)點(diǎn)，此時(shí)需要從情況一開始對(duì) P 進(jìn)行平衡處理。

情況四：

N 的父節(jié)點(diǎn)是紅色，S 和 S 孩子為黑色。這種情況比較簡(jiǎn)單，我們只需交換 P 和 S 顏色即可。這樣所有通過 N 的路徑上增加了一個(gè)黑色節(jié)點(diǎn)，所有通過 S 的節(jié)點(diǎn)的路徑必然也通過 P 節(jié)點(diǎn)，由于 P 與 S 只是互換顏色，并不影響這些路徑。

情況五：

S 為黑色，S 的左孩子為紅色，右孩子為黑色。N 的父節(jié)點(diǎn)顏色可紅可黑，且 N 是 P 左孩子。這種情況下對(duì) S 進(jìn)行右旋操作，并互換 S 和 SL 的顏色。此時(shí)，所有路徑上的黑色數(shù)量仍然相等，N 兄弟節(jié)點(diǎn)的由 S 變?yōu)榱?SL，而 SL 的右孩子變?yōu)榧t色。接下來我們到情況六繼續(xù)分析。

情況六：

S 為黑色，S 的右孩子為紅色。N 的父節(jié)點(diǎn)顏色可紅可黑，且 N 是其父節(jié)點(diǎn)左孩子。這種情況下，我們對(duì) P 進(jìn)行左旋操作，并互換 P 和 S 的顏色，并將 SR 變?yōu)楹谏?。因?yàn)?P 變?yōu)楹谏?，所以?jīng)過 N 的路徑多了一個(gè)黑色節(jié)點(diǎn)，經(jīng)過 N 的路徑上的黑色節(jié)點(diǎn)與刪除前的數(shù)量一致。對(duì)于不經(jīng)過 N 的路徑，則有以下兩種情況：

該路徑經(jīng)過 N 新的兄弟節(jié)點(diǎn) SL ，那它之前必然經(jīng)過 S 和 P。而 S 和 P 現(xiàn)在只是交換顏色，對(duì)于經(jīng)過 SL 的路徑不影響。

該路徑經(jīng)過 N 新的叔叔節(jié)點(diǎn) S，那它之前必然經(jīng)過 P、 S 和 SR，而現(xiàn)在它只經(jīng)過 S 和 SR。在對(duì) P 進(jìn)行左旋，并與 S 換色后，經(jīng)過 SR 的路徑少了一個(gè)黑色節(jié)點(diǎn)，性質(zhì)5被打破。另外，由于 S 的顏色可紅可黑，如果 S 是紅色的話，會(huì)與 SR 形成連續(xù)的紅色節(jié)點(diǎn)，打破性質(zhì)4（每個(gè)紅色節(jié)點(diǎn)必須有兩個(gè)黑色的子節(jié)點(diǎn)）。此時(shí)僅需將 SR 由紅色變?yōu)楹谏纯赏瑫r(shí)恢復(fù)性質(zhì)4和性質(zhì)5（從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。）。

刪除總結(jié)

紅黑樹刪除的情況比較多，大家剛開始看的時(shí)候可能會(huì)比較暈?？赡軙?huì)產(chǎn)生這樣的疑問，為啥紅黑樹會(huì)有這種刪除情況，為啥又會(huì)有另一種情況，它們之間有什么聯(lián)系和區(qū)別？和大家一樣，我剛開始看的時(shí)候也有這樣的困惑，直到我把所有情況對(duì)應(yīng)的圖形畫在一起時(shí)，撥云見日，一切都明了了。此時(shí)天空中出現(xiàn)了4個(gè)字，原來如此、原來如此、原來如此。所以，請(qǐng)看圖吧：

“

四、總結(jié)

紅黑樹是一種重要的二叉樹，應(yīng)用廣泛，但在很多數(shù)據(jù)結(jié)構(gòu)相關(guān)的書本中出現(xiàn)的次數(shù)并不多。很多書中要么不說，要么就一筆帶過，并不會(huì)進(jìn)行詳細(xì)的分析，這可能是因?yàn)榧t黑樹比較復(fù)雜的緣故。我在學(xué)習(xí)紅黑樹的時(shí)候也找了很多資料，但總體感覺講的都不太好。尤其是在我學(xué)習(xí)刪除操作的時(shí)候，很多資料是在讓人看不下去，看的我很痛苦。直到我看到維基百科上關(guān)于紅黑樹的分析時(shí)，很是欣喜。這篇文章分析的很有條理，言簡(jiǎn)意賅，比很多資料好了太多。本文對(duì)紅黑樹的分析也主要參考了維基百科中的紅黑樹分析，并對(duì)維基百科中容易讓人產(chǎn)生疑問和誤解的地方進(jìn)行了說明。同時(shí)維基百科中文版紅黑樹文中的圖片較為模糊，這里我重新進(jìn)行了繪制。需要說明的是，維基百科中文版無法打開了，文中關(guān)于維基百科的鏈接都是英文版的。另外在給大家推薦一個(gè)數(shù)據(jù)結(jié)構(gòu)可視化的網(wǎng)站，里面包含常見數(shù)據(jù)結(jié)構(gòu)可視化過程，地址為：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html。

另外，由于紅黑樹本身比較復(fù)雜，實(shí)現(xiàn)也較為復(fù)雜。在寫這篇文章之前，我曾嘗試過用 Java 語言實(shí)現(xiàn)紅黑樹的增刪操作，最終只寫出了新增節(jié)點(diǎn)操作，刪除沒做出來。而且自己寫的新增邏輯實(shí)在在太繁瑣，寫的不好看，沒臉拿出來 show。所以最后把 Java 中的 TreeMap 增刪相關(guān)源碼拷出來，按照自己的需求把源碼修改了一下，也勉強(qiáng)算是實(shí)現(xiàn)了紅黑樹吧。以下是代碼RBTree.java。

package search;import java.util.*;/** * 紅黑樹實(shí)現(xiàn)，該實(shí)現(xiàn)核心邏輯由 TreeMap 源碼修改而來 * * @author code4wt * @date 2017-12-23 17:26:28 */public class RBTree> { private final static boolean RED = true; private final static boolean BLACK = false; private TreeNode root; public boolean contains(T value) { return Objects.nonNull(getNode(value)); } public void putAll(Collection collection) { collection.forEach(this::put); } public void put(T value) { if (Objects.isNull(value)) { throw new NullPointerException(); } TreeNode t = root; if (Objects.isNull(t)) { root = new TreeNode<>(null, null, null, value); return; } int cmp; TreeNode parent; do { parent = t; cmp = value.compareTo(t.value); if (cmp == 0) { return; } else if (cmp > 0) { t = t.right; } else { t = t.left; } } while (Objects.nonNull(t)); TreeNode e = new TreeNode<>(parent, null, null, value); if (cmp < 0) { ? ? ? ? ? ?parent.left = e; ? ? ? ?} else { ? ? ? ? ? ?parent.right = e; ? ? ? ?} ? ? ? ?fixAfterInsertion(e); ? ?} ? ?public void remove(T value) { ? ? ? ?TreeNode p = getNode(value); if (Objects.nonNull(value)) { deleteNode(p); } } public void clear() { root = null; } private TreeNode getNode(T value) { if (Objects.isNull(value)) { throw new NullPointerException(); } TreeNode p = root; while (Objects.nonNull(p)) { int cmp = value.compareTo(p.value); if (cmp < 0) { ? ? ? ? ? ? ? ?p = p.left; ? ? ? ? ? ?} else if (cmp > 0) { p = p.right; } else { return p; } } return null; } private void deleteNode(TreeNode p) { // 節(jié)點(diǎn) p 有兩個(gè)孩子節(jié)點(diǎn)時(shí)，先找到 p 節(jié)點(diǎn)的后繼節(jié)點(diǎn) if (p.left != null && p.right != null) { TreeNode s = successor(p); p.value = s.value; p = s; } TreeNode replacement = (p.left != null ? p.left : p.right); if (replacement != null) { replacement.parent = p.parent; if (p.parent == null) { root = replacement; } else if (p == p.parent.left) { p.parent.left = replacement; } else { p.parent.right = replacement; } p.left = p.right = p.parent = null; if (p.color == BLACK) { fixAfterDeletion(replacement); } } else if (p.parent == null) { root = null; } else { // 待刪除的節(jié)點(diǎn)沒有孩子節(jié)點(diǎn) // 如果刪除的節(jié)點(diǎn)是黑色，則需要先進(jìn)行修復(fù) if (p.color == BLACK) { fixAfterDeletion(p); } // 將待刪除節(jié)點(diǎn)從樹中刪除 if (p.parent != null) { if (p == p.parent.left) { p.parent.left = null; } else if (p == p.parent.right) { p.parent.right = null; } p.parent = null; } } } private TreeNode successor(TreeNode t) { if (Objects.isNull(t)) { return null; } if (t.right != null) { TreeNode p = t.right; while (p.left != null) { p = p.left; } return p; } else { TreeNode p = t.parent; TreeNode ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } private void rotateLeft(TreeNode p) { if (Objects.nonNull(p)) { TreeNode r = p.right; p.right = r.left; if (r.left != null) { r.left.parent = p; } r.parent = p.parent; if (p.parent == null) { root = r; } else if (p.parent.left == p) { p.parent.left = r; } else { p.parent.right = r; } r.left = p; p.parent = r; } } /** From CLR */ private void rotateRight(TreeNode p) { if (Objects.nonNull(p)) { TreeNode l = p.left; p.left = l.right; if (l.right != null) { l.right.parent = p; } l.parent = p.parent; if (p.parent == null) { root = l; } else if (p.parent.right == p) { p.parent.right = l; } else { p.parent.left = l; } l.right = p; p.parent = l; } } /** From CLR */ private void fixAfterInsertion(TreeNode x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { TreeNode y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == rightOf(parentOf(x))) { x = parentOf(x); rotateLeft(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { TreeNode y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); setColor(y, BLACK); setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); rotateRight(x); } setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } root.color = BLACK; } private void fixAfterDeletion(TreeNode x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { TreeNode sib = rightOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateLeft(parentOf(x)); sib = rightOf(parentOf(x)); } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } else { // symmetric TreeNode sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); x = parentOf(x); } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } setColor(sib, colorOf(parentOf(x))); setColor(parentOf(x), BLACK); setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); } private boolean colorOf(TreeNode p) { return (p == null ? BLACK : p.color); } private TreeNode parentOf(TreeNode p) { return (p == null ? null: p.parent); } private void setColor(TreeNode p, boolean c) { if (p != null) { p.color = c; } } private TreeNode leftOf(TreeNode p) { return (p == null) ? null: p.left; } private TreeNode rightOf(TreeNode p) { return (p == null) ? null: p.right; } private class TreeNode> { TreeNode parent; TreeNode left; TreeNode right; T value; boolean color; public TreeNode(TreeNode parent, TreeNode left, TreeNode right, T value) { this.parent = parent; this.left = left; this.right = right; this.value = value; this.color = RED; } @Override public String toString() { return value + "," + (color == RED ? "r" : "b"); } }}

最后，如果你也在學(xué)習(xí)紅黑樹，希望這篇文章能夠幫助到你。另外，由于紅黑樹本身比較復(fù)雜，加之本人水平有限，難免會(huì)出一些錯(cuò)誤。如果有錯(cuò)，還望大家指出來，我們共同討論。