0 、前言

紅黑樹是軟件工程中非常重要的數(shù)據(jù)結(jié)構(gòu)，在很多的工程領(lǐng)域都有它的身影，比如java的treemap、linkedhashmap，linux內(nèi)核、linux的高并發(fā)多路復(fù)用利器epoll的核心數(shù)據(jù)結(jié)構(gòu)就是紅黑樹；然而這個(gè)數(shù)據(jù)結(jié)構(gòu)卻不是那么容易理解，特別是網(wǎng)絡(luò)上缺少對(duì)紅黑樹本質(zhì)的分析，一般都是自底向上的來講述，非常tricky，往往看了一段就不知所云，最后放棄了。但是，紅黑樹真的沒這么復(fù)雜，本文從自頂向下的方式來解構(gòu)紅黑樹，爭取寫一篇能持續(xù)看下去，最后達(dá)到能夠手寫（手畫）一棵紅黑樹出來的目的。

本文沒有代碼，全是圖解，請(qǐng)放心閱讀

1、什么是紅黑樹

紅黑樹是查找表（符號(hào)表）數(shù)據(jù)結(jié)構(gòu)群中的一員，這群數(shù)據(jù)結(jié)構(gòu)主要的功能是維護(hù)一組key-value鍵值對(duì)，并通過增刪查改等操作對(duì)其進(jìn)行操作。比如：hash表、二分查找表、BST、2-3樹，跳表、紅黑樹都是這些數(shù)據(jù)結(jié)構(gòu)的一員。

2、紅黑樹有啥用？

在眾多查找表中，可以說紅黑樹是最穩(wěn)定（增刪查改都是O(logn)的復(fù)雜度），動(dòng)態(tài)增刪性能最好（Ologn），編碼最容易的一種實(shí)現(xiàn)（奇怪吧，hashtable不是都是O(1)么？）。

hash表不是查找，插入都是O(1)么，怎么紅黑樹會(huì)是綜合性能最好的？這就要說到工程特性了。一個(gè)技術(shù)從科學(xué)研究到工程實(shí)踐可行是有一個(gè)鴻溝的，而hash表就是這個(gè)悖論的典型例子。雖然容易理解，但是hashtable并不容易實(shí)現(xiàn)，而且它的效率并不穩(wěn)定，原因有以下兩個(gè)：

1、惱人的最差性能，其實(shí)hashtable最差的效率是O(n)，就是在沖突不斷增加的時(shí)候，性能會(huì)急劇下降；這時(shí)需要做非常tricky的補(bǔ)救措施；

2、這個(gè)補(bǔ)救措施就是rehashing，簡單來講就是將這個(gè)數(shù)組重新搬到大一倍的空間中，然后重新算hash映射，除此之外沒別的辦法。這個(gè)過程耗時(shí)耗力，耗盡了hashtable的好印象。在這個(gè)過程中還會(huì)出線程同步問題，而且編碼難度極大？比如，如果在多線程環(huán)境下，對(duì)線程不安全版本的hashtable做頻繁的新增操作會(huì)死鎖（親測這個(gè)死鎖幾乎7 80%會(huì)出現(xiàn)），具體的原因，主要是rehashing的時(shí)候開鏈發(fā)對(duì)鏈表新增節(jié)點(diǎn)時(shí)的同步問題；

3、而且在java中，hashmap其實(shí)在鏈表的數(shù)量大于8時(shí)，會(huì)將鏈表轉(zhuǎn)成紅黑樹來加快查詢。

紅黑樹的穩(wěn)定性與動(dòng)態(tài)維護(hù)超大數(shù)據(jù)量kv表的能力使它成為互聯(lián)網(wǎng)應(yīng)用的重要數(shù)據(jù)結(jié)構(gòu)，對(duì)于一個(gè)10億規(guī)模的數(shù)據(jù)量，最多也只要查30多次就能找到你想要的key-value pair。而且對(duì)于很多l(xiāng)inux內(nèi)核的代碼中也是大量使用紅黑樹來保持插入與查詢的穩(wěn)定性。

3、解構(gòu)紅黑樹

既然，紅黑樹這么重要，對(duì)于有追求的碼農(nóng)應(yīng)該有必要了解它的原理。

但是遺憾的是，網(wǎng)絡(luò)上對(duì)紅黑樹的解讀大都比較難懂，大部分的解釋都是來自一本神書《算法導(dǎo)論》，這也是萬惡之源：

1、這本書并不是面向程序員的，別被導(dǎo)論這兩個(gè)字迷惑，這個(gè)導(dǎo)論可能是對(duì)于計(jì)算機(jī)科學(xué)家來說的吧~

2、這個(gè)書中所描述的紅黑樹定義是結(jié)論型的，也就是假設(shè)你對(duì)BST樹、2-3樹都很熟悉的情況下得出的結(jié)論，比如《導(dǎo)論》中對(duì)紅黑樹的定義是：

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

? ? 2.根節(jié)點(diǎn)是黑色。

? ? 3.每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。

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

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

很多人，包括我也疑惑很多年，這是啥？好好的數(shù)據(jù)結(jié)構(gòu)，咋還要染色？為啥是紅黑，黑白可以嗎？為啥會(huì)制定這么復(fù)雜的規(guī)則？這么復(fù)雜的規(guī)則是怎么得出來的？

后來看了《算法》這本面向程序員的算法書后才霍然開朗，這里我試著將這本書對(duì)紅黑樹的闡述總結(jié)一下。

3.1 還是得先講講BST

BST（Binary Search Tree）是二叉查找樹的簡稱，其實(shí)很簡單。大概的意思如下圖：

BST樹

1、樹左邊的都比根??；

2、右邊都比根大；

3、將規(guī)則遞歸到所有節(jié)點(diǎn)，就得到一顆BST。

細(xì)心的你會(huì)發(fā)現(xiàn)BST有個(gè)”bug“，在插入的時(shí)候，如果是按照升序插入，那么就是一個(gè)鏈表了那么這時(shí)的查詢也從O(logn)退化到了O(n).

退化后的BST

所以可以推斷，一顆好的查找樹一定是平衡的，而且最好是完美平衡的（任何節(jié)點(diǎn)的左右子樹深度都相等），因?yàn)檫@樣它的查詢操作就會(huì)穩(wěn)定到O(logn)——也就是樹的高度了。畢竟，在工程領(lǐng)域最重要的準(zhǔn)則就是——穩(wěn)定壓倒一切！

3.2、2-3 tree

那么主角2-3 tree就登場了，為啥2-3樹是主角？劇透一下，因?yàn)榧t黑樹本質(zhì)就是2-3tree，而且”紅“就是2-3樹中的3節(jié)點(diǎn)，”黑“就是2節(jié)點(diǎn)。下面詳細(xì)講解。

2-3 tree的定義其實(shí)很簡單:

1、2-3tree是BST的一種，繼承所有BST的特點(diǎn)；

2、整棵樹由2-node與3-node組成；

3、2-node就是包含一個(gè)key節(jié)點(diǎn)，兩個(gè)左右子樹鏈接（對(duì)應(yīng)BST中的普通節(jié)點(diǎn)），3-node就是包含2個(gè)key，同時(shí)包含3個(gè)子樹鏈接的節(jié)點(diǎn)，就是3叉樹節(jié)點(diǎn)；

4、2-3樹是完美平衡的。

有圖更好理解：

2-3 tree

可以看出來，2-node就是二叉樹普通節(jié)點(diǎn)，3-node就是三叉樹的普通節(jié)點(diǎn)。那么2-3 tree是由2-node與3-node組成的完美平衡的搜索樹，通俗的講就是，這棵樹中根節(jié)點(diǎn)的左右子樹中2-3 node高度始終都一樣高。

怎么保持樹的完美平衡呢？

我們通過例子看看插入的規(guī)則，我們以順序插入1-10來作為例子，先不講規(guī)則，我們看看例子，然后總結(jié)出規(guī)則，我們以依次向2-3 tree中插入1-10個(gè)數(shù)字的例子來演示。

1、插入1，只有一個(gè)節(jié)點(diǎn)，簡單：

插入1

2、插入2

插入2，由于樹不平衡，所以進(jìn)行融合

3、插入3

插入3

這里說明下，2-3樹在插入過程中會(huì)臨時(shí)形成4-node（也就是有3個(gè)key，4個(gè)子樹的node），而這時(shí)，4-node要馬上分解成3個(gè)2-node。

4、插入4

插入4

5、插入5

插入5-1

插入5-2

插入5-3

插入5的時(shí)候比較復(fù)雜，臨時(shí)的4-node會(huì)分解成3個(gè)2-nodes，這時(shí)會(huì)導(dǎo)致樹不平衡，右邊子樹高度+1，那么需要將3個(gè)2-node的中間節(jié)點(diǎn)向上融合（調(diào)平的重要步驟）。

6、插入6

插入6

7、插入7

插入7-1

插入7-2

插入7-3

插入7-4

可以看出插入7的結(jié)果會(huì)不斷將臨時(shí)4-node分裂成3個(gè)2-node，并向上傳遞，最后會(huì)使樹的高度增加1，但是整個(gè)樹是完美平衡的。

8、插入8

插入8

9、插入9

插入9-1

插入9-2

插入9-3

10、插入10

插入10

好了，畫完了，樹中2-3節(jié)點(diǎn)完美平衡。找到規(guī)律了么？沒有的話，我總結(jié)下：

1、在2-node中插入新節(jié)點(diǎn)，形成3-node，不破壞樹的平衡，done；

2、在3-node中插入新節(jié)點(diǎn)分為3步：

? ? 2.1、形成新的臨時(shí)4-node；

? ? 2.2、將4-node分解成3個(gè)2-node；

? ? 2.3、如果樹不平衡，就將中間節(jié)點(diǎn)向上融合，重新遞歸1、2、兩個(gè)步驟，直到樹平衡。

看懂了么？是不是很簡單，如果沒有，就再看看上面的圖解吧~

3.3 重新發(fā)明紅黑樹

您可能會(huì)問，2-3 tree已經(jīng)很完美了，不管怎么插入數(shù)據(jù)，只要根據(jù)"兩個(gè)"簡單的規(guī)則就能維持一個(gè)樹的完美平衡，為啥還要發(fā)明紅黑樹呢？

原因很簡單，工程實(shí)現(xiàn)難度！又是工程的實(shí)現(xiàn)難度！說白了就是容易出bug……

跟hashmap一樣，實(shí)現(xiàn)一個(gè)工程可用的2-3tree是比較困難的（觀點(diǎn)來自于《算法》沒有親測）：

1、樹中間包含3種節(jié)點(diǎn)，相比BST來說意味著更多的判斷，比如，從4-node，分裂成3個(gè)2-node，從2-node合并成3-node等等；情況多，編碼復(fù)雜；

2、各種node的節(jié)點(diǎn)在互相轉(zhuǎn)變的過程中需要拷貝的信息也比較多，比如3-node可以有3個(gè)子樹，2-node有2個(gè)，那么融合的時(shí)候情況較多，不能直接向BST一樣統(tǒng)一處理，算法實(shí)現(xiàn)要處理的情況太多，容易出bug；

3、代碼不能重用（BST的代碼不能重用）。

但是我覺得最重要的是2-3 tree原理完美，但是結(jié)構(gòu)不完美。一個(gè)完美的數(shù)據(jù)結(jié)構(gòu)一定是原理與結(jié)構(gòu)都是統(tǒng)一的、樸素簡單的。2-3 tree更像一個(gè)通向最終答案的中間解，只要把中間的3-node與4-node這些tricky的node想辦法變換成2-node就結(jié)構(gòu)也統(tǒng)一完美了；那么BST的很多代碼就可以稍微修改一下就可以重用了（特別是刪除節(jié)點(diǎn)的代碼~）。

怎么統(tǒng)一呢？

方法其實(shí)也很簡單、直接，我們只要將2-3 tree在結(jié)構(gòu)上對(duì)齊BST，在保持平衡的原理上維持現(xiàn)狀不就行了？也就是西瓜芝麻都一起抓——去掉2-3 tree中的3-node。

3.3.1 去掉3-node

怎么去掉3-node？很簡單，真的很簡單，還是看圖說話：

3-node到2個(gè)2-node

就是把3-node拉直就行了！

更一般化的形式為

《算法》節(jié)選

但是，左子樹的高度加了1，那么結(jié)構(gòu)的算法特性有沒有發(fā)生改變呢？

其實(shí)沒有，因?yàn)槟阋廊豢梢园选?-7“這個(gè)紅色標(biāo)記的鏈接看做是一個(gè)3-node，那么它的搜索特性就沒有變化。本質(zhì)來講，當(dāng)我們?cè)?-3 tree里面做搜索的時(shí)候，當(dāng)我們碰到3-node的時(shí)候，其實(shí)就相當(dāng)于在節(jié)點(diǎn)內(nèi)部要比2-node多做一次比較，拉直了相當(dāng)于把這個(gè)多出來的比較形式化成了一條鏈接，計(jì)算量是沒有變化的。

所以紅黑樹跟2-3 tree是完全等價(jià)的！或者說通過把2-3 tree中的3-node拉直而形成的BST樹就是——紅黑樹！

書中的例子，更加清楚：

截圖自《算法》

3.3.2 定義的解析

3.3.2.1 一些前提與說明

之前我們只是把邊涂成紅色，但是BST是沒有邊的定義的，所以這個(gè)顏色只能記錄在節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)中，所以我們把從父節(jié)點(diǎn)到子節(jié)點(diǎn)的紅邊會(huì)存儲(chǔ)在子節(jié)點(diǎn)中——將子節(jié)點(diǎn)涂成紅色，構(gòu)成紅色節(jié)點(diǎn)，其他的自然都是黑色節(jié)點(diǎn)。

對(duì)于網(wǎng)上比較常見的一個(gè)紅黑樹例子：

網(wǎng)上常用的例子

細(xì)心的讀者會(huì)發(fā)現(xiàn)，這個(gè)根本不是一個(gè)2-3 tree，但是確實(shí)是紅黑樹，這是怎么回事？

因?yàn)榧t黑樹定義有不同，相同節(jié)點(diǎn)的紅黑樹會(huì)根據(jù)定義不同產(chǎn)生不同的紅黑節(jié)點(diǎn)數(shù)量，如果直接從2-3tree轉(zhuǎn)的紅黑樹可能跟以上5條定義獲得的紅黑樹稍有不同，但是他們都是紅黑樹。

再來看看經(jīng)典紅黑樹的定義《導(dǎo)論》中的定義（針對(duì)的是節(jié)點(diǎn)顏色）：

1.節(jié)點(diǎn)是紅色或黑色。（貌似是廢話，難道對(duì)于紅黑樹還有第三種顏色？）

? ? 2.根節(jié)點(diǎn)是黑色。（沒啥用）

? ? 3.每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。

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

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

再看看《算法》中的定義（針對(duì)的是線的顏色）：

1、紅色的線永遠(yuǎn)是左側(cè)鏈接；（強(qiáng)行的規(guī)定）

? 2、沒有一個(gè)節(jié)點(diǎn)同時(shí)鏈了兩條紅色的線；（也就是沒有3-node）

? 3、任何從根到葉子節(jié)點(diǎn)的路徑上有相同顏色的黑線。

可以看出定義是完全不同的（一個(gè)針對(duì)節(jié)點(diǎn)顏色，一個(gè)針對(duì)線的顏色——而線的顏色存在node中，所以還是紅黑樹），但是都能構(gòu)成一棵紅黑樹。

而我們的解析是采用《算法》中的，因?yàn)樗?-3 tree一一對(duì)應(yīng)，很好理解。而《導(dǎo)論》中的定義是經(jīng)過2-3 tree，2-3-4 tree的抽象總結(jié)出來的非常通用抽象的解析，其經(jīng)過很多思維迭代后的結(jié)果，所以很抽象，但是本質(zhì)來說他們是一回事，是可以通過有限次推導(dǎo)（reduction）互相轉(zhuǎn)換的。

那么下面我們對(duì)網(wǎng)上的例子做些轉(zhuǎn)換，將它化簡成一個(gè)2-3 tree的原型：

有兩個(gè)紅色子節(jié)點(diǎn)的都可以做傳遞轉(zhuǎn)換

轉(zhuǎn)換得到的依然是紅黑樹。

然后可以將紅色節(jié)點(diǎn)跟父節(jié)點(diǎn)融合成一個(gè)3-node

3.3.3 一步步構(gòu)建紅黑樹

還是通過依次插入1-10，用《算法》中講述的紅黑線試圖來解析。

1、插入1

很簡單……

2、插入2

rule1：插入的新節(jié)點(diǎn)跟父節(jié)點(diǎn)用red線連接

插入2

3、插入3

rule2：一個(gè)節(jié)點(diǎn)不能有兩個(gè)紅線相連（不是父子），否則就要通過旋轉(zhuǎn)將中間節(jié)點(diǎn)移動(dòng)成父節(jié)點(diǎn)。

rule3：如果一個(gè)節(jié)點(diǎn)父子都是紅線相連，則需要翻轉(zhuǎn)顏色，并把父節(jié)點(diǎn)與祖父節(jié)點(diǎn)的鏈接變成紅色（也就是2-3 tree中分解4-node的時(shí)候，3個(gè)2-node中間的那個(gè)向上傳遞的過程）。

插入3-1

插入3-2

所以，可見紅黑樹中的翻轉(zhuǎn)其本質(zhì)就是將4-node分解成3個(gè)2-node，并將中間節(jié)點(diǎn)與父節(jié)點(diǎn)融合的過程。

4、插入4

插入4

插入4，很簡單，紅線相連即可，因?yàn)槊織l路徑黑線數(shù)目一樣。

5、插入5

插入5-1

插入5-2

6、插入6

插入6

此時(shí)可以跟2-3 tree插入到6的圖比較下，其實(shí)可以找到規(guī)律:->

2-3 tree插入6

是不是紅色線跟3-node一一對(duì)應(yīng)？

7、插入7

插入7-1

插入7-2

插入7-3

插入7-4

可以發(fā)現(xiàn)2-3 tree插入7也是4步，跟紅黑樹的旋轉(zhuǎn)變色的過程一一對(duì)應(yīng)。

8、插入8

插入8

9、插入9

插入9-1

插入9-2

10、插入10

插入10

完畢，這就是一個(gè)以邊為視角的插入過程，只需要將邊的顏色信息存儲(chǔ)到節(jié)點(diǎn)中就可以得到一棵紅黑樹：

插入10后的紅黑樹

總結(jié)下2-3tree與紅黑樹的操作對(duì)應(yīng)：

1、2-3 tree中的4-node分裂成3個(gè)2-node，并讓中間節(jié)點(diǎn)上移；等價(jià)于紅黑樹中的左右旋轉(zhuǎn)；

2、2-3tree中間節(jié)點(diǎn)上移與父節(jié)點(diǎn)融合過程；等價(jià)于紅黑樹中的反色操作。

是不是很好理解了？

3.4 后續(xù)的操作

紅黑樹的插入操作我們解構(gòu)完了，我們還剩下一個(gè)比較復(fù)雜的刪除操作。這個(gè)操作其實(shí)是使用BST的標(biāo)準(zhǔn)刪除操作，一個(gè)比較標(biāo)準(zhǔn)的算法是，將要?jiǎng)h除節(jié)點(diǎn)的右子樹中的最小值（或者左子樹中最大值）替換掉當(dāng)前刪除的節(jié)點(diǎn)，當(dāng)然針對(duì)不同的情況需要做些判斷。而且在工程領(lǐng)域，也會(huì)引入隨機(jī)的刪除左右子樹中的最大最小交替的方式，來完成刪除，以至于不會(huì)使得樹的稀疏度差異太大，從而降低搜索效率那是另一個(gè)范疇的事情了。

4、總結(jié)

紅黑樹是一個(gè)非常重要的，而且在工程中常用的數(shù)據(jù)結(jié)構(gòu)。比如jvm的hashmap，linux中還為紅黑樹單獨(dú)建立了數(shù)據(jù)結(jié)構(gòu)對(duì)象（linux內(nèi)核源碼的lib/rbtree.c文件）因?yàn)樵趌inux內(nèi)核中的進(jìn)程調(diào)度，虛擬內(nèi)存管理等操作頻繁而且性能critical的地方都會(huì)使用紅黑樹；另外在linux的epoll多路復(fù)用的模型中，核心數(shù)據(jù)結(jié)構(gòu)就是紅黑樹。那么為什么紅黑樹這么好，一句話：

1、動(dòng)態(tài)插入、刪除、查找都是O(logn)，而且只要內(nèi)存足夠，性能穩(wěn)定在這個(gè)數(shù)量級(jí)上；

2、工程上好實(shí)現(xiàn)，編碼簡單。

作者：小龍的城堡

鏈接：http://www.itdecent.cn/p/4aeeabd326dc

來源：簡書

著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。