紅黑樹的使用場景非常廣泛，比如nginx中用來管理timer、epoll中用紅黑樹管理事件塊（文件描述符）、Linux進(jìn)程調(diào)度Completely Fair Scheduler用紅黑樹管理進(jìn)程控制塊、C++STL中map,set的底層實(shí)現(xiàn)全是用的紅黑樹。掌握紅黑樹的原理以及使用場景，對(duì)于我們面試和工作、以及理解開源代碼都是非常有幫助。

二叉樹介紹

在關(guān)注紅黑樹之前，首先復(fù)習(xí)一下二叉樹的概念。在數(shù)據(jù)結(jié)構(gòu)中，二叉樹有如下定義：

二叉樹是一種由節(jié)點(diǎn)和層組成的結(jié)構(gòu)

每一層有若干個(gè)節(jié)點(diǎn)

第一層只能有一個(gè)根節(jié)點(diǎn)

每個(gè)節(jié)點(diǎn)可以擁有兩顆支樹，分別被稱為左子樹(left subtree)和右子樹(right subtree)

對(duì)于一個(gè)節(jié)點(diǎn)，左子樹所有的元素都比這個(gè)節(jié)點(diǎn)存儲(chǔ)的元素小，右子樹所有的節(jié)點(diǎn)都比這個(gè)節(jié)點(diǎn)存儲(chǔ)的元素大

它的結(jié)構(gòu)類似如下的截圖：

那么二叉樹被定義為以上的規(guī)則，到底有什么用呢？跟傳統(tǒng)的鏈表存儲(chǔ)相比，到底有什么優(yōu)勢呢？對(duì)于上述的二叉樹，如果使用鏈表存儲(chǔ)則表示如下：

當(dāng)我們從這個(gè)鏈表中的頭部107開始查找元素的時(shí)候，對(duì)于它的7個(gè)成員查找需要的次數(shù)如下：

通過如上表格我們發(fā)現(xiàn)，鏈表中元素的比較次數(shù)跟元素在鏈表中存儲(chǔ)的位置正相關(guān)，所有元素的最終的平均比較次數(shù)等于(1 + 2 + 3 + 4 + 5 + 6 + 7) / 7 = 4

對(duì)于二叉樹來說，由于二叉樹被定義為左子樹所有的元素都比這個(gè)節(jié)點(diǎn)存儲(chǔ)的元素小，右子樹所有的節(jié)點(diǎn)都比這個(gè)節(jié)點(diǎn)存儲(chǔ)的元素大，對(duì)于完全二叉樹來說，每次比較我們都可以排除掉一半的元素。

比如對(duì)于上述二叉樹中的元素45來說，第一次跟60比較，小于60，直接排除掉右子樹所有的元素(100,67,107)，第二次跟55比較，小于55，排除掉55右子樹所有的元素(57)，最后定位到45，這里只比較了3次。在二叉樹中七個(gè)成員查找需要的次數(shù)如下：

所有元素的最終的平均比較次數(shù)等于(1 + 2 + 2 + 3 + 3 + 3 + 3) / 7 ≈ 2.4，很直觀的發(fā)現(xiàn)，二叉樹的平均比較次數(shù)比鏈表少。即鏈表的平均復(fù)雜度為O(n)，而二叉樹的平均復(fù)雜度為O(logn)。可以說，二叉樹是一種比鏈表更高效查找的數(shù)據(jù)結(jié)構(gòu)。

二叉樹的弊端

上面已經(jīng)說過，二叉樹是比鏈表查找更高效的數(shù)據(jù)結(jié)構(gòu)，但是二叉樹的時(shí)間復(fù)雜度一定比鏈表低嗎？還是爭對(duì)上述的二叉樹中的元素舉例，即按45->55->57->60->67->100->107的順序，把元素插入二叉樹當(dāng)中，插入過程如下圖所

示：

我們發(fā)現(xiàn)，當(dāng)按順序插入的時(shí)候，二叉樹變成了一個(gè)”瘸子“，這樣的只有個(gè)一個(gè)支數(shù)的二叉樹，實(shí)際上就是一個(gè)鏈表。也就是說，二叉樹最壞的情況下，查找的時(shí)間復(fù)雜度等于鏈表O(n)，這完全失去了二叉樹的意義。那么如何避免這種情況，讓二叉樹能盡可能的“平衡”一點(diǎn)呢？

另外小編還整理了一些各大知名企業(yè)BAT精選面試題、需要的朋友可以加qun720209036獲取

紅黑樹的定義

為了讓插入的時(shí)候，二叉樹盡可能的平衡，1972年魯?shù)婪颉へ悹柼岢黾t黑樹的概念，對(duì)于紅黑樹的定義如下：

節(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è)葉子(NIL)的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)

遵循如上規(guī)則的二叉樹被稱為紅黑樹，但是為什么要定義成如上規(guī)則呢？事實(shí)上，如上所有的規(guī)則都只想做一件事，讓二叉樹盡可能的平衡。

對(duì)于定義4，即代表了紅黑樹中不可能出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)，也就是說支樹上最多是紅黑交替的情況(可以出現(xiàn)連續(xù)的黑節(jié)點(diǎn))。

對(duì)于定義5，結(jié)合定義4，即代表紅黑樹中最長路徑最多是最短路徑的兩倍。

爭對(duì)上述的1，2舉例：

上圖是一個(gè)符合紅黑樹定義的二叉樹，葉子(NIL)節(jié)點(diǎn)就是一個(gè)空節(jié)點(diǎn)，表示節(jié)點(diǎn)在此位置上沒有元素了。在實(shí)際的算法實(shí)現(xiàn)中NIL不需要考慮，填上NIL節(jié)點(diǎn)只是為了判斷到此路徑終點(diǎn)的NIL節(jié)點(diǎn)上，經(jīng)過多少黑節(jié)點(diǎn)。

此紅黑樹中，根節(jié)點(diǎn)到NIL節(jié)點(diǎn)，最短路徑為55到45（2個(gè)黑色節(jié)點(diǎn)），最長路徑為55到107（2個(gè)黑色節(jié)點(diǎn)，2個(gè)紅色節(jié)點(diǎn)），最長路徑是最短路徑的節(jié)點(diǎn)數(shù)的兩倍。如果在往107后面添加一個(gè)黑色節(jié)點(diǎn)，則不符合定義5，因?yàn)槎嗔艘粋€(gè)黑色節(jié)點(diǎn)。所以紅黑樹保證了最壞情況和最好情況不會(huì)差太多，做到一個(gè)相對(duì)來說的平衡。

左旋和右旋

對(duì)于一個(gè)節(jié)點(diǎn)N來說，它有一個(gè)左節(jié)點(diǎn)L，右節(jié)點(diǎn)R，如下圖所示：

根據(jù)二叉樹定義，N > L，N < R，且N為L和R的父節(jié)點(diǎn)。那么如果L當(dāng)兒子當(dāng)夠了，現(xiàn)在L想當(dāng)N的爸爸（父節(jié)點(diǎn)），二叉樹該怎么調(diào)整？

因?yàn)長 < N，根據(jù)二叉樹定義，把N放入L的右節(jié)點(diǎn)處

N的左節(jié)點(diǎn)指向節(jié)點(diǎn)2

上述的過程稱為對(duì)節(jié)點(diǎn)N的右旋，對(duì)應(yīng)的動(dòng)態(tài)圖為：

同理，如果R想做N的父節(jié)點(diǎn)呢？

因?yàn)镽 > N，根據(jù)二叉樹定義，把N放入R的左節(jié)點(diǎn)處

N的右節(jié)點(diǎn)節(jié)點(diǎn)指向節(jié)點(diǎn)3

上述的過程稱為對(duì)節(jié)點(diǎn)N的左旋，對(duì)應(yīng)的動(dòng)態(tài)圖為：

其實(shí)所謂的左旋右旋，可以理解為節(jié)點(diǎn)的子節(jié)點(diǎn)想”篡位“，原來的子節(jié)點(diǎn)變?yōu)楝F(xiàn)在節(jié)點(diǎn)的父節(jié)點(diǎn)。

紅黑樹的插入

復(fù)習(xí)一下二叉樹的插入規(guī)則：

定位到需要插入的位置

插入元素

二叉樹的插入如下圖所示：

而紅黑樹比二叉樹多了一個(gè)規(guī)則，插入后重新平衡二叉樹，讓它符合紅黑樹的定義。規(guī)定新插入的節(jié)點(diǎn)一定是紅色的，因?yàn)槿绻迦氲氖呛谏?#xff0c;原來經(jīng)過插入之前的節(jié)點(diǎn)的元素就會(huì)多一個(gè)黑色節(jié)點(diǎn)，調(diào)整起來比較麻煩。

下面介紹插入完成之后如何平衡二叉樹：

假設(shè)剛插入的節(jié)點(diǎn)為X，它的父節(jié)點(diǎn)為N，祖父節(jié)點(diǎn)為P，N的兄弟節(jié)點(diǎn)為U，下圖列舉了一種可能的情況：

說明：紅底的代表紅節(jié)點(diǎn)，黑底的代表黑節(jié)點(diǎn)，白底的代表顏色未知的節(jié)點(diǎn)（即可黑可紅）。

現(xiàn)在需要以X節(jié)點(diǎn)的父節(jié)點(diǎn)N的顏色作為一個(gè)切入點(diǎn)開始討論：

N為黑色
這種情況是最簡單的，不需要做任何調(diào)整，因?yàn)樾虏迦氲墓?jié)點(diǎn)X為紅色，并不會(huì)影響經(jīng)過X的支路的黑節(jié)點(diǎn)數(shù)量，之前是多少，現(xiàn)在就是多少。

N為紅色此時(shí)出現(xiàn)了X和N為兩個(gè)連續(xù)的紅節(jié)點(diǎn)，需要調(diào)整樹，讓它符合紅黑樹的特征。對(duì)于X,N,P節(jié)點(diǎn)的關(guān)系，現(xiàn)在這里有四種情況：

第一種：N為P的左節(jié)點(diǎn)，X為N的左節(jié)點(diǎn)
第二種：N為P的左節(jié)點(diǎn)，X為N的右節(jié)點(diǎn)
第三種：N為P的右節(jié)點(diǎn)，X為N的右節(jié)點(diǎn)
第四種：N為P的右節(jié)點(diǎn)，X為N的左節(jié)點(diǎn)

觀察后不難發(fā)現(xiàn)，其實(shí)前面兩種和后面兩種是成鏡像的，也就是說分析前兩種，后面兩種的操作可以效仿前兩種。現(xiàn)在我們可以對(duì)節(jié)點(diǎn)做一下左旋，右旋，節(jié)點(diǎn)顏色修改等操作，讓樹重新符合紅黑樹特征（由于N為紅色，根據(jù)紅黑樹的特征4，P節(jié)點(diǎn)一定為黑。）。

• N為P的左節(jié)點(diǎn)，X為N的左節(jié)點(diǎn)

• • 這種情況我們就需要分析U節(jié)點(diǎn)的顏色
    ① U節(jié)點(diǎn)為紅色
    直接把N和U全部設(shè)置為黑色，把P設(shè)置為紅色即可

設(shè)到達(dá)P節(jié)點(diǎn)之前，有a個(gè)黑色節(jié)點(diǎn)。在改變之前，在到達(dá)X,1,2,3這四個(gè)節(jié)點(diǎn)的時(shí)候，經(jīng)過黑色節(jié)點(diǎn)的數(shù)量如下：

X節(jié)點(diǎn)：a + 1
1節(jié)點(diǎn)：a + 2
2節(jié)點(diǎn)：a + 2
3節(jié)點(diǎn)：a + 2

• • 改變之后

X節(jié)點(diǎn)：a + 1
1節(jié)點(diǎn)：a + 2
2節(jié)點(diǎn)：a + 2
3節(jié)點(diǎn)：a + 2

• • 可以發(fā)現(xiàn)改變之后還是符合紅黑樹的特征5。上述給了一種分析經(jīng)過路徑的黑節(jié)點(diǎn)的數(shù)量的一種手段。
    ② U節(jié)點(diǎn)為黑色
    首先對(duì)P節(jié)點(diǎn)進(jìn)行右旋，然后交換N和P節(jié)點(diǎn)的顏色

設(shè)到達(dá)P節(jié)點(diǎn)之前，有a個(gè)黑色節(jié)點(diǎn)。在改變之前，在到達(dá)X,1,2,3這四個(gè)節(jié)點(diǎn)的時(shí)候，經(jīng)過黑色節(jié)點(diǎn)的數(shù)量如下 (因?yàn)?，3節(jié)點(diǎn)的顏色未知，所以用d2,d3代表。比如說如果2為黑，d2則為1，否則為0)：

X節(jié)點(diǎn)：a + 1
1節(jié)點(diǎn)：a + 2
2節(jié)點(diǎn)：a + 2 + d2
3節(jié)點(diǎn)：a + 2 + d3

• • 改變之后

X節(jié)點(diǎn)：a + 1
1節(jié)點(diǎn)：a + 2
2節(jié)點(diǎn)：a + 2 + d2
3節(jié)點(diǎn)：a + 2 + d3

• • 可以發(fā)現(xiàn)改變之后還是符合紅黑樹的特征5。
    N為P的左節(jié)點(diǎn)，X為N的右節(jié)點(diǎn)
    首先左旋N節(jié)點(diǎn)

設(shè)到達(dá)P節(jié)點(diǎn)之前，有a個(gè)黑色節(jié)點(diǎn)。在改變之前，在到達(dá)1,2,3,4,5這五個(gè)節(jié)點(diǎn)的時(shí)候，經(jīng)過黑色節(jié)點(diǎn)的數(shù)量如下 (因?yàn)?，3節(jié)點(diǎn)的顏色未知，所以用d2,d3代表。比如說如果2為黑，d2則為1，否則為0)：

1節(jié)點(diǎn)：a + 2
2節(jié)點(diǎn)：a + 2 + d2
3節(jié)點(diǎn)：a + 2 + d3
4節(jié)點(diǎn)：a + 2
5節(jié)點(diǎn)：a + 2

• • 改變之后

1節(jié)點(diǎn)：a + 2
2節(jié)點(diǎn)：a + 2 + d2
3節(jié)點(diǎn)：a + 2 + d3
4節(jié)點(diǎn)：a + 2
5節(jié)點(diǎn)：a + 2

• • 可以看出，并沒有改變支路上黑節(jié)點(diǎn)的數(shù)量。但是N,X還是兩個(gè)連續(xù)的紅節(jié)點(diǎn)，還要繼續(xù)操作。觀察到上圖被紅色方框圈出來的東西發(fā)現(xiàn)，它就是之前N為P的左節(jié)點(diǎn)，X為N的左節(jié)點(diǎn)的那種情況，所以可以轉(zhuǎn)到對(duì)應(yīng)的步驟處理。
  • N為P的右節(jié)點(diǎn)，X為N的右節(jié)點(diǎn)
    對(duì)應(yīng)N為P的左節(jié)點(diǎn)，X為N的左節(jié)點(diǎn)，把右旋換成左旋，其他步驟一樣。
  • N為P的右節(jié)點(diǎn)，X為N的左節(jié)點(diǎn)
    對(duì)應(yīng)N為P的左節(jié)點(diǎn)，X為N的右節(jié)點(diǎn)，把右旋換成左旋，其他步驟一樣。

紅黑樹的刪除

跟插入一樣，紅黑樹的刪除就比二叉樹多了一個(gè)步驟：刪除完成之后重新調(diào)整樹，讓它再次符合二叉樹的定義。那么二叉樹是如何進(jìn)行刪除的呢？下面是出二叉樹的刪除步驟：

定位到二叉樹需要?jiǎng)h除的節(jié)點(diǎn)

如果節(jié)點(diǎn)沒有支樹了，直接刪除節(jié)點(diǎn)

如果節(jié)點(diǎn)只有一個(gè)子支樹，直接把這個(gè)子支樹跟需要?jiǎng)h除的節(jié)點(diǎn)的父節(jié)點(diǎn)相連

如果節(jié)點(diǎn)有兩個(gè)支樹，找到節(jié)點(diǎn)的左支樹的最大值，或者右支樹的最小值，然后把這個(gè)值（這里我們使用左支樹的最大值）賦值給需要?jiǎng)h除的節(jié)點(diǎn)（注意：當(dāng)前需要被刪除的節(jié)點(diǎn)不會(huì)被刪掉了，只是被賦予了新值）。然后我們?cè)賱h除掉擁有左支樹的最大值的這個(gè)節(jié)點(diǎn)，因?yàn)檫@個(gè)節(jié)點(diǎn)是左邊最大的了，那么它的右分支肯定為空，也就是說最多只可能有一個(gè)支樹。這時(shí)候我們可以轉(zhuǎn)換為情況2,3處理了。

需要理解的是，我們常說的刪除一顆樹中的一個(gè)節(jié)點(diǎn)，表示只要這顆樹中不存在這個(gè)節(jié)點(diǎn)所存儲(chǔ)的值，就表明刪除了，并不一定要真正的抹掉這個(gè)節(jié)點(diǎn)！

下面爭對(duì)上面的第四種舉一個(gè)例子：

經(jīng)過上面的介紹，相信大家對(duì)二叉樹的刪除都有一點(diǎn)了解。紅黑樹的刪除也會(huì)經(jīng)過上面的步驟，不同的是，刪除之后會(huì)調(diào)整紅黑樹，讓它重新符合紅黑樹的特征，下面分析刪除完成之后的情況。

這里假設(shè)一個(gè)節(jié)點(diǎn)P，刪除了它的一個(gè)子節(jié)點(diǎn)X，刪除完成之后，N節(jié)點(diǎn)頂替掉了X節(jié)點(diǎn)，成為P的子節(jié)點(diǎn)。X節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為S，S的左右節(jié)點(diǎn)為SL，SR。

對(duì)于上述舉出的刪除的例子來說，這個(gè)P節(jié)點(diǎn)就是10，X節(jié)點(diǎn)就是11，N節(jié)點(diǎn)是NULL，S節(jié)點(diǎn)為13，SL為NULL，SR為NULL。注意，雖然上述刪除的是12，但是我們討論的X確并不是12。這是因?yàn)槲覀儼褎h除節(jié)點(diǎn)12這個(gè)問題轉(zhuǎn)換為了刪除節(jié)點(diǎn)11。最終樹中確實(shí)少了12，但是它的值只是被新值覆蓋，節(jié)點(diǎn)被沒有刪除。而我們討論的是被抹掉的節(jié)點(diǎn)。

所以有了上面的前提，我們分析問題的切入點(diǎn)就只有兩個(gè)，被刪除的節(jié)點(diǎn)有0個(gè)支樹，被刪除的的節(jié)點(diǎn)有1個(gè)支樹。為什么沒有被刪除的節(jié)點(diǎn)有兩個(gè)支樹的情況呢？因?yàn)槿绻袃蓚€(gè)，通過上面介紹的二叉樹的刪除步驟4，我們可以把刪除具有兩個(gè)子樹的節(jié)點(diǎn)的情況轉(zhuǎn)變?yōu)閯h除具有一個(gè)子樹或者具有0顆子樹的情況。

比如對(duì)于上面的例子，我們把刪除12(這個(gè)節(jié)點(diǎn)有兩個(gè)子樹)，轉(zhuǎn)變?yōu)閯h除11(具有0顆子樹)的情況。下面從被刪除節(jié)點(diǎn)的支樹數(shù)量的個(gè)數(shù)開始分析：

被刪除的X節(jié)點(diǎn)沒有分支
這種情況直接刪除節(jié)點(diǎn)就完事了，不需要做任何調(diào)整。我們常說調(diào)整紅黑樹，是因?yàn)椴环霞t黑樹的特征4和特征5。而刪除一個(gè)沒有分支的節(jié)點(diǎn)，用屁股隨便想一下就知道不會(huì)影響這兩條。

被刪除的X節(jié)點(diǎn)有一個(gè)分支這個(gè)時(shí)候的切入點(diǎn)就是被刪除節(jié)點(diǎn)的顏色

• 被刪除的X節(jié)點(diǎn)為紅色
  這種也是我們最喜歡的情況，不需要調(diào)整啊。因?yàn)楦鶕?jù)紅黑樹的特征4，此時(shí)X的父節(jié)點(diǎn)P必為黑色，所以N節(jié)點(diǎn)為紅還是黑都不會(huì)影響特征4。而X節(jié)點(diǎn)又為紅，也就是說，經(jīng)過原來X的那條支路只是少了一個(gè)紅節(jié)點(diǎn)，也不會(huì)影響特征5。
• 被刪除的節(jié)點(diǎn)是黑色
  這又要分為很多種情況了，這里你可以一條一條分析N，U和P節(jié)點(diǎn)的顏色。我們分析的切入點(diǎn)是，頂替X節(jié)點(diǎn)的N節(jié)點(diǎn)的顏色。

說明：紅底的代表紅節(jié)點(diǎn)，黑底的代表黑節(jié)點(diǎn)，白底的代表顏色未知的節(jié)點(diǎn)（即可黑可紅）。

• • (1) N節(jié)點(diǎn)為紅
    這種情況也很簡單，直接把N染成黑色

經(jīng)過上面的操作，不僅N不會(huì)和P產(chǎn)生兩個(gè)連續(xù)紅節(jié)點(diǎn)的情況，而且經(jīng)過N節(jié)點(diǎn)的路徑多了一個(gè)黑節(jié)點(diǎn)，正好替代被刪除的黑節(jié)點(diǎn)X。
(2) N節(jié)點(diǎn)為黑
然后從S節(jié)點(diǎn)的顏色開始分析
①S節(jié)點(diǎn)為紅色
因?yàn)镾為紅色，根據(jù)紅黑樹的定義，P，SL，SR肯定都是黑色，如下圖：

這里我們把P節(jié)點(diǎn)進(jìn)行左旋，然后交換S和P節(jié)點(diǎn)的顏色

上面的S節(jié)點(diǎn)為P節(jié)點(diǎn)的右節(jié)點(diǎn)，所以左旋P節(jié)點(diǎn)。如果S節(jié)點(diǎn)為P節(jié)點(diǎn)的左節(jié)點(diǎn)，則是右旋P節(jié)點(diǎn)。
分析N，SL，SR節(jié)點(diǎn)在操作前和操作后的路徑經(jīng)過的黑色節(jié)點(diǎn)數(shù)量，發(fā)現(xiàn)都沒有改變。但是我們把N節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為紅色的轉(zhuǎn)換為黑色的情況。為黑色的處理情況如下處理。
②S節(jié)點(diǎn)為黑色，SR節(jié)點(diǎn)為紅的情況。如下圖所示：

由于原來P的左邊有一個(gè)黑節(jié)點(diǎn)X，現(xiàn)在被刪除了，所以左邊路徑上少了一個(gè)黑節(jié)點(diǎn)。
這種情況，直接左旋P節(jié)點(diǎn)，然后交換P,S的顏色，并且把SR換成黑色。

上面的S節(jié)點(diǎn)為P節(jié)點(diǎn)的右節(jié)點(diǎn)，所以取了SR來舉例子。如果S為P節(jié)點(diǎn)的左節(jié)點(diǎn)，那么就應(yīng)該去SL。然后把左旋改成右旋。
通過如上操作，不難發(fā)現(xiàn)，經(jīng)過N節(jié)點(diǎn)的路徑的黑色節(jié)點(diǎn)數(shù)量多了一個(gè)，而經(jīng)過SL,SR節(jié)點(diǎn)的路徑的黑色節(jié)點(diǎn)并沒有變少，符合紅黑樹定義4，5。
③ S節(jié)點(diǎn)為黑色，SR節(jié)點(diǎn)為黑
這種情況下只剩下P節(jié)點(diǎn)和SL節(jié)點(diǎn)的顏色沒有確定，這兩個(gè)節(jié)點(diǎn)的組合，總共可能有四種情況：

P為黑，SL為黑色

P為白，SL為黑

P為黑，SL為白

P為白，SL為白

• • 對(duì)于第一種和第二種情況，都是轉(zhuǎn)換成如下的情況：

第一種是直接把S變成紅色。然后P的左右支樹的節(jié)點(diǎn)數(shù)量一樣（P的左子樹少了個(gè)黑色節(jié)點(diǎn)X）。
但是對(duì)于經(jīng)過P節(jié)點(diǎn)的支路上來說，全部都少了一個(gè)黑節(jié)點(diǎn)（比如經(jīng)過SL和SR節(jié)點(diǎn)的支路）。
所以可以把P節(jié)點(diǎn)看成N節(jié)點(diǎn)，進(jìn)行遞歸，分析P節(jié)點(diǎn)的父節(jié)點(diǎn)，兄弟節(jié)點(diǎn)。如果中途一直沒有解決，則會(huì)遞歸到根節(jié)點(diǎn)。如果根節(jié)點(diǎn)此時(shí)為紅色，則變回黑色。、第二種直接把P和S節(jié)點(diǎn)的顏色對(duì)調(diào)，就不需要再調(diào)整了。因?yàn)閷?duì)于經(jīng)過N節(jié)點(diǎn)的支路多了一個(gè)黑節(jié)點(diǎn)，對(duì)于SL，SR來說沒有變，正好符合情況。第三種和第四種其實(shí)都是對(duì)S節(jié)點(diǎn)進(jìn)行右旋，然后交換SL和S的顏色最后轉(zhuǎn)化成S節(jié)點(diǎn)為黑色，SR節(jié)點(diǎn)為紅的情況。

紅黑樹的代碼實(shí)現(xiàn)

引用linux紅黑樹的經(jīng)典實(shí)現(xiàn)

紅黑樹的實(shí)現(xiàn)文件(rbtree.h)

/*Red Black Trees(C) 1999 Andrea Arcangeli <andrea@suse.de>This program is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 2 of the License, or(at your option) any later version.This program is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See theGNU General Public License for more details.You should have received a copy of the GNU General Public Licensealong with this program; if not, write to the Free SoftwareFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USAlinux/include/linux/rbtree.hTo use rbtrees you'll have to implement your own insert and search cores.This will avoid us to use callbacks and to drop drammatically performances.I know it's not the cleaner way, but in C (not in C++) to getperformances and genericity...Some example of insert and search follows here. The search is a plainnormal search over an ordered tree. The insert instead must be implementedin two steps: First, the code must insert the element in order as a red leafin the tree, and then the support library function rb_insert_color() mustbe called. Such function will do the not trivial work to rebalance therbtree, if necessary.----------------------------------------------------------------------- static inline struct page * rb_search_page_cache(struct inode * inode,unsigned long offset) {struct rb_node * n = inode->i_rb_page_cache.rb_node;struct page * page;while (n){page = rb_entry(n, struct page, rb_page_cache);if (offset < page->offset)n = n->rb_left;else if (offset > page->offset)n = n->rb_right;elsereturn page;}return NULL; }static inline struct page * __rb_insert_page_cache(struct inode * inode,unsigned long offset,struct rb_node * node) {struct rb_node ** p = &inode->i_rb_page_cache.rb_node;struct rb_node * parent = NULL;struct page * page;while (*p){parent = *p;page = rb_entry(parent, struct page, rb_page_cache);if (offset < page->offset)p = &(*p)->rb_left;else if (offset > page->offset)p = &(*p)->rb_right;elsereturn page;}rb_link_node(node, parent, p);return NULL; }static inline struct page * rb_insert_page_cache(struct inode * inode,unsigned long offset,struct rb_node * node) {struct page * ret;if ((ret = __rb_insert_page_cache(inode, offset, node)))goto out;rb_insert_color(node, &inode->i_rb_page_cache);out:return ret; } ----------------------------------------------------------------------- */#ifndef _SLINUX_RBTREE_H #define _SLINUX_RBTREE_H#include <stdio.h> //#include <linux/kernel.h> //#include <linux/stddef.h>struct rb_node {unsigned long rb_parent_color; #define RB_RED 0 #define RB_BLACK 1struct rb_node *rb_right;struct rb_node *rb_left; } /* __attribute__((aligned(sizeof(long))))*/;/* The alignment might seem pointless, but allegedly CRIS needs it */struct rb_root {struct rb_node *rb_node; };#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) #define rb_color(r) ((r)->rb_parent_color & 1) #define rb_is_red(r) (!rb_color(r)) #define rb_is_black(r) rb_color(r) #define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) #define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) {rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; } static inline void rb_set_color(struct rb_node *rb, int color) {rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; }#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)#define container_of(ptr, type, member) ({ const typeof( ((type *)0)->member ) *__mptr = (ptr); (type *)( (char *)__mptr - offsetof(type,member) );})#define RB_ROOT (struct rb_root) { NULL, } #define rb_entry(ptr, type, member) container_of(ptr, type, member)#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) #define RB_EMPTY_NODE(node) (rb_parent(node) == node) #define RB_CLEAR_NODE(node) (rb_set_parent(node, node))static inline void rb_init_node(struct rb_node *rb) {rb->rb_parent_color = 0;rb->rb_right = NULL;rb->rb_left = NULL;RB_CLEAR_NODE(rb); }extern void rb_insert_color(struct rb_node *, struct rb_root *); extern void rb_erase(struct rb_node *, struct rb_root *);typedef void (*rb_augment_f)(struct rb_node *node, void *data);extern void rb_augment_insert(struct rb_node *node,rb_augment_f func, void *data); extern struct rb_node *rb_augment_erase_begin(struct rb_node *node); extern void rb_augment_erase_end(struct rb_node *node,rb_augment_f func, void *data);/* Find logical next and previous nodes in a tree */ extern struct rb_node *rb_next(const struct rb_node *); extern struct rb_node *rb_prev(const struct rb_node *); extern struct rb_node *rb_first(const struct rb_root *); extern struct rb_node *rb_last(const struct rb_root *);/* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,struct rb_root *root);static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,struct rb_node ** rb_link) {node->rb_parent_color = (unsigned long )parent;node->rb_left = node->rb_right = NULL;*rb_link = node; }#endif /* _LINUX_RBTREE_H */

紅黑樹的實(shí)現(xiàn)文件(rbtree.c)

/*Red Black Trees(C) 1999 Andrea Arcangeli <andrea@suse.de>(C) 2002 David Woodhouse <dwmw2@infradead.org>This program is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 2 of the License, or(at your option) any later version.This program is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See theGNU General Public License for more details.You should have received a copy of the GNU General Public Licensealong with this program; if not, write to the Free SoftwareFoundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USAlinux/lib/rbtree.c */#include "rbtree.h"static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) {struct rb_node *right = node->rb_right;struct rb_node *parent = rb_parent(node);if ((node->rb_right = right->rb_left))rb_set_parent(right->rb_left, node);right->rb_left = node;rb_set_parent(right, parent);if (parent){if (node == parent->rb_left)parent->rb_left = right;elseparent->rb_right = right;}elseroot->rb_node = right;rb_set_parent(node, right); }static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) {struct rb_node *left = node->rb_left;struct rb_node *parent = rb_parent(node);if ((node->rb_left = left->rb_right))rb_set_parent(left->rb_right, node);left->rb_right = node;rb_set_parent(left, parent);if (parent){if (node == parent->rb_right)parent->rb_right = left;elseparent->rb_left = left;}elseroot->rb_node = left;rb_set_parent(node, left); }void rb_insert_color(struct rb_node *node, struct rb_root *root) {struct rb_node *parent, *gparent;while ((parent = rb_parent(node)) && rb_is_red(parent)){gparent = rb_parent(parent);if (parent == gparent->rb_left){{register struct rb_node *uncle = gparent->rb_right;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;continue;}}if (parent->rb_right == node){register struct rb_node *tmp;__rb_rotate_left(parent, root);tmp = parent;parent = node;node = tmp;}rb_set_black(parent);rb_set_red(gparent);__rb_rotate_right(gparent, root);} else {{register struct rb_node *uncle = gparent->rb_left;if (uncle && rb_is_red(uncle)){rb_set_black(uncle);rb_set_black(parent);rb_set_red(gparent);node = gparent;continue;}}if (parent->rb_left == node){register struct rb_node *tmp;__rb_rotate_right(parent, root);tmp = parent;parent = node;node = tmp;}rb_set_black(parent);rb_set_red(gparent);__rb_rotate_left(gparent, root);}}rb_set_black(root->rb_node); }static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,struct rb_root *root) {struct rb_node *other;while ((!node || rb_is_black(node)) && node != root->rb_node){if (parent->rb_left == node){other = parent->rb_right;if (rb_is_red(other)){rb_set_black(other);rb_set_red(parent);__rb_rotate_left(parent, root);other = parent->rb_right;}if ((!other->rb_left || rb_is_black(other->rb_left)) &&(!other->rb_right || rb_is_black(other->rb_right))){rb_set_red(other);node = parent;parent = rb_parent(node);}else{if (!other->rb_right || rb_is_black(other->rb_right)){rb_set_black(other->rb_left);rb_set_red(other);__rb_rotate_right(other, root);other = parent->rb_right;}rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->rb_right);__rb_rotate_left(parent, root);node = root->rb_node;break;}}else{other = parent->rb_left;if (rb_is_red(other)){rb_set_black(other);rb_set_red(parent);__rb_rotate_right(parent, root);other = parent->rb_left;}if ((!other->rb_left || rb_is_black(other->rb_left)) &&(!other->rb_right || rb_is_black(other->rb_right))){rb_set_red(other);node = parent;parent = rb_parent(node);}else{if (!other->rb_left || rb_is_black(other->rb_left)){rb_set_black(other->rb_right);rb_set_red(other);__rb_rotate_left(other, root);other = parent->rb_left;}rb_set_color(other, rb_color(parent));rb_set_black(parent);rb_set_black(other->rb_left);__rb_rotate_right(parent, root);node = root->rb_node;break;}}}if (node)rb_set_black(node); }void rb_erase(struct rb_node *node, struct rb_root *root) {struct rb_node *child, *parent;int color;if (!node->rb_left)child = node->rb_right;else if (!node->rb_right)child = node->rb_left;else{struct rb_node *old = node, *left;node = node->rb_right;while ((left = node->rb_left) != NULL)node = left;if (rb_parent(old)) {if (rb_parent(old)->rb_left == old)rb_parent(old)->rb_left = node;elserb_parent(old)->rb_right = node;} elseroot->rb_node = node;child = node->rb_right;parent = rb_parent(node);color = rb_color(node);if (parent == old) {parent = node;} else {if (child)rb_set_parent(child, parent);parent->rb_left = child;node->rb_right = old->rb_right;rb_set_parent(old->rb_right, node);}node->rb_parent_color = old->rb_parent_color;node->rb_left = old->rb_left;rb_set_parent(old->rb_left, node);goto color;}parent = rb_parent(node);color = rb_color(node);if (child)rb_set_parent(child, parent);if (parent){if (parent->rb_left == node)parent->rb_left = child;elseparent->rb_right = child;}elseroot->rb_node = child;color:if (color == RB_BLACK)__rb_erase_color(child, parent, root); }static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data) {struct rb_node *parent;up:func(node, data);parent = rb_parent(node);if (!parent)return;if (node == parent->rb_left && parent->rb_right)func(parent->rb_right, data);else if (parent->rb_left)func(parent->rb_left, data);node = parent;goto up; }/** after inserting @node into the tree, update the tree to account for* both the new entry and any damage done by rebalance*/ void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data) {if (node->rb_left)node = node->rb_left;else if (node->rb_right)node = node->rb_right;rb_augment_path(node, func, data); }/** before removing the node, find the deepest node on the rebalance path* that will still be there after @node gets removed*/ struct rb_node *rb_augment_erase_begin(struct rb_node *node) {struct rb_node *deepest;if (!node->rb_right && !node->rb_left)deepest = rb_parent(node);else if (!node->rb_right)deepest = node->rb_left;else if (!node->rb_left)deepest = node->rb_right;else {deepest = rb_next(node);if (deepest->rb_right)deepest = deepest->rb_right;else if (rb_parent(deepest) != node)deepest = rb_parent(deepest);}return deepest; }/** after removal, update the tree to account for the removed entry* and any rebalance damage.*/ void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data) {if (node)rb_augment_path(node, func, data); }/** This function returns the first node (in sort order) of the tree.*/ struct rb_node *rb_first(const struct rb_root *root) {struct rb_node *n;n = root->rb_node;if (!n)return NULL;while (n->rb_left)n = n->rb_left;return n; }struct rb_node *rb_last(const struct rb_root *root) {struct rb_node *n;n = root->rb_node;if (!n)return NULL;while (n->rb_right)n = n->rb_right;return n; }struct rb_node *rb_next(const struct rb_node *node) {struct rb_node *parent;if (rb_parent(node) == node)return NULL;/* If we have a right-hand child, go down and then left as faras we can. */if (node->rb_right) {node = node->rb_right;while (node->rb_left)node=node->rb_left;return (struct rb_node *)node;}/* No right-hand children. Everything down and left issmaller than us, so any 'next' node must be in the generaldirection of our parent. Go up the tree; any time theancestor is a right-hand child of its parent, keep goingup. First time it's a left-hand child of its parent, saidparent is our 'next' node. */while ((parent = rb_parent(node)) && node == parent->rb_right)node = parent;return parent; }struct rb_node *rb_prev(const struct rb_node *node) {struct rb_node *parent;if (rb_parent(node) == node)return NULL;/* If we have a left-hand child, go down and then right as faras we can. */if (node->rb_left) {node = node->rb_left;while (node->rb_right)node=node->rb_right;return (struct rb_node *)node;}/* No left-hand children. Go up till we find an ancestor whichis a right-hand child of its parent */while ((parent = rb_parent(node)) && node == parent->rb_left)node = parent;return parent; }void rb_replace_node(struct rb_node *victim, struct rb_node *new,struct rb_root *root) {struct rb_node *parent = rb_parent(victim);/* Set the surrounding nodes to point to the replacement */if (parent) {if (victim == parent->rb_left)parent->rb_left = new;elseparent->rb_right = new;} else {root->rb_node = new;}if (victim->rb_left)rb_set_parent(victim->rb_left, new);if (victim->rb_right)rb_set_parent(victim->rb_right, new);/* Copy the pointers/colour from the victim to the replacement */*new = *victim; }

紅黑樹的測試文件(test.c)

/*** 根據(jù)Linux Kernel定義的紅黑樹(Red Black Tree)**/#include <stdio.h> #include <stdlib.h> #include "rbtree.h"#define CHECK_INSERT 0 // "插入"動(dòng)作的檢測開關(guān)(0，關(guān)閉；1，打開) #define CHECK_DELETE 0 // "刪除"動(dòng)作的檢測開關(guān)(0，關(guān)閉；1，打開) #define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )typedef int Type;struct my_node {struct rb_node rb_node; // 紅黑樹節(jié)點(diǎn)Type key; // 鍵值// ... 用戶自定義的數(shù)據(jù) };/** 查找"紅黑樹"中鍵值為key的節(jié)點(diǎn)。沒找到的話，返回NULL。*/ struct my_node *my_search(struct rb_root *root, Type key) {struct rb_node *rbnode = root->rb_node;while (rbnode!=NULL){struct my_node *mynode = container_of(rbnode, struct my_node, rb_node);if (key < mynode->key)rbnode = rbnode->rb_left;else if (key > mynode->key)rbnode = rbnode->rb_right;elsereturn mynode;}return NULL; }/** 將key插入到紅黑樹中。插入成功，返回0；失敗返回-1。*/ int my_insert(struct rb_root *root, Type key) {struct my_node *mynode; // 新建結(jié)點(diǎn)struct rb_node **tmp = &(root->rb_node), *parent = NULL;/* Figure out where to put new node */while (*tmp){struct my_node *my = container_of(*tmp, struct my_node, rb_node);parent = *tmp;if (key < my->key)tmp = &((*tmp)->rb_left);else if (key > my->key)tmp = &((*tmp)->rb_right);elsereturn -1;}// 如果新建結(jié)點(diǎn)失敗，則返回。if ((mynode=malloc(sizeof(struct my_node))) == NULL)return -1;mynode->key = key;/* Add new node and rebalance tree. */rb_link_node(&mynode->rb_node, parent, tmp);rb_insert_color(&mynode->rb_node, root);return 0; }/** 刪除鍵值為key的結(jié)點(diǎn)*/ void my_delete(struct rb_root *root, Type key) {struct my_node *mynode;// 在紅黑樹中查找key對(duì)應(yīng)的節(jié)點(diǎn)mynodeif ((mynode = my_search(root, key)) == NULL)return ;// 從紅黑樹中刪除節(jié)點(diǎn)mynoderb_erase(&mynode->rb_node, root);free(mynode); }/** 打印"紅黑樹"*/ static void print_rbtree(struct rb_node *tree, Type key, int direction) {if(tree != NULL){if(direction==0) // tree是根節(jié)點(diǎn)printf("%2d(B) is rootn", key);else // tree是分支節(jié)點(diǎn)printf("%2d(%s) is %2d's %6s childn", key, rb_is_black(tree)?"B":"R", key, direction==1?"right" : "left");if (tree->rb_left)print_rbtree(tree->rb_left, rb_entry(tree->rb_left, struct my_node, rb_node)->key, -1);if (tree->rb_right)print_rbtree(tree->rb_right,rb_entry(tree->rb_right, struct my_node, rb_node)->key, 1);} }void my_print(struct rb_root *root) {if (root!=NULL && root->rb_node!=NULL)print_rbtree(root->rb_node, rb_entry(root->rb_node, struct my_node, rb_node)->key, 0); }void main() {int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};int i, ilen=LENGTH(a);struct rb_root mytree = RB_ROOT;printf("== 原始數(shù)據(jù): ");for(i=0; i<ilen; i++)printf("%d ", a[i]);printf("n");for (i=0; i < ilen; i++){my_insert(&mytree, a[i]); #if CHECK_INSERTprintf("== 添加節(jié)點(diǎn): %dn", a[i]);printf("== 樹的詳細(xì)信息: n");my_print(&mytree);printf("n"); #endif}#if CHECK_DELETEfor (i=0; i<ilen; i++) {my_delete(&mytree, a[i]);printf("== 刪除節(jié)點(diǎn): %dn", a[i]);printf("== 樹的詳細(xì)信息: n");my_print(&mytree);printf("n");} #endif }

總結(jié)

以上是生活随笔為你收集整理的红黑树和平衡二叉树的区别_面试题精选红黑树(c/c++版本)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。