0 胜嗓、前言
紅黑樹是軟件工程中非常重要的數(shù)據(jù)結(jié)構(gòu)牡整，在很多的工程領(lǐng)域都有它的身影粉铐，比如java的treemap疼约、linkedhashmap，linux內(nèi)核蝙泼、linux的高并發(fā)多路復(fù)用利器epoll的核心數(shù)據(jù)結(jié)構(gòu)就是紅黑樹程剥；然而這個數(shù)據(jù)結(jié)構(gòu)卻不是那么容易理解，特別是網(wǎng)絡(luò)上缺少對紅黑樹本質(zhì)的分析汤踏，一般都是自底向上的來講述织鲸，非常tricky，往往看了一段就不知所云溪胶，最后放棄了搂擦。但是，紅黑樹真的沒這么復(fù)雜哗脖，本文從自頂向下的方式來解構(gòu)紅黑樹瀑踢，爭取寫一篇能持續(xù)看下去扳还，最后達到能夠手寫（手畫）一棵紅黑樹出來的目的。
本文沒有代碼橱夭，全是圖解氨距，請放心閱讀
1、什么是紅黑樹
紅黑樹是查找表（符號表）數(shù)據(jù)結(jié)構(gòu)群中的一員棘劣，這群數(shù)據(jù)結(jié)構(gòu)主要的功能是維護一組key-value鍵值對俏让，并通過增刪查改等操作對其進行操作。比如：hash表呈础、二分查找表舆驶、BST橱健、2-3樹而钞，跳表、紅黑樹都是這些數(shù)據(jù)結(jié)構(gòu)的一員拘荡。
2臼节、紅黑樹有啥用？
在眾多查找表中珊皿，可以說紅黑樹是最穩(wěn)定（增刪查改都是O(logn)的復(fù)雜度）网缝，動態(tài)增刪性能最好（Ologn），編碼最容易的一種實現(xiàn)（奇怪吧蟋定，hashtable不是都是O(1)么粉臊？）。
hash表不是查找驶兜，插入都是O(1)么扼仲，怎么紅黑樹會是綜合性能最好的？這就要說到工程特性了抄淑。一個技術(shù)從科學(xué)研究到工程實踐可行是有一個鴻溝的屠凶，而hash表就是這個悖論的典型例子。雖然容易理解肆资，但是hashtable并不容易實現(xiàn)矗愧，而且它的效率并不穩(wěn)定，原因有以下兩個：
1郑原、惱人的最差性能唉韭，其實hashtable最差的效率是O(n)，就是在沖突不斷增加的時候犯犁，性能會急劇下降属愤；這時需要做非常tricky的補救措施；
2栖秕、這個補救措施就是rehashing春塌，簡單來講就是將這個數(shù)組重新搬到大一倍的空間中，然后重新算hash映射，除此之外沒別的辦法只壳。這個過程耗時耗力俏拱，耗盡了hashtable的好印象。在這個過程中還會出線程同步問題吼句，而且編碼難度極大锅必？比如，如果在多線程環(huán)境下惕艳，對線程不安全版本的hashtable做頻繁的新增操作會死鎖（親測這個死鎖幾乎7 80%會出現(xiàn)）搞隐，具體的原因，主要是rehashing的時候開鏈發(fā)對鏈表新增節(jié)點時的同步問題远搪；
3劣纲、而且在java中，hashmap其實在鏈表的數(shù)量大于8時谁鳍，會將鏈表轉(zhuǎn)成紅黑樹來加快查詢癞季。
紅黑樹的穩(wěn)定性與動態(tài)維護超大數(shù)據(jù)量kv表的能力使它成為互聯(lián)網(wǎng)應(yīng)用的重要數(shù)據(jù)結(jié)構(gòu)，對于一個10億規(guī)模的數(shù)據(jù)量倘潜，最多也只要查30多次就能找到你想要的key-value pair绷柒。而且對于很多l(xiāng)inux內(nèi)核的代碼中也是大量使用紅黑樹來保持插入與查詢的穩(wěn)定性。
3涮因、解構(gòu)紅黑樹
既然废睦，紅黑樹這么重要，對于有追求的碼農(nóng)應(yīng)該有必要了解它的原理养泡。
但是遺憾的是嗜湃，網(wǎng)絡(luò)上對紅黑樹的解讀大都比較難懂，大部分的解釋都是來自一本神書《算法導(dǎo)論》瓤荔，這也是萬惡之源：
1净蚤、這本書并不是面向程序員的，別被導(dǎo)論這兩個字迷惑输硝，這個導(dǎo)論可能是對于計算機科學(xué)家來說的吧~
2今瀑、這個書中所描述的紅黑樹定義是結(jié)論型的，也就是假設(shè)你對BST樹点把、2-3樹都很熟悉的情況下得出的結(jié)論橘荠，比如《導(dǎo)論》中對紅黑樹的定義是：
? ? 1.節(jié)點是紅色或黑色。
? ? 2.根節(jié)點是黑色郎逃。
? ? 3.每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）哥童。
? ? 4 每個紅色節(jié)點的兩個子節(jié)點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
? ? 5.從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點褒翰。
很多人贮懈，包括我也疑惑很多年匀泊，這是啥？好好的數(shù)據(jù)結(jié)構(gòu)朵你，咋還要染色各聘？為啥是紅黑，黑白可以嗎抡医？為啥會制定這么復(fù)雜的規(guī)則躲因？這么復(fù)雜的規(guī)則是怎么得出來的？
后來看了《算法》這本面向程序員的算法書后才霍然開朗忌傻，這里我試著將這本書對紅黑樹的闡述總結(jié)一下大脉。
3.1 還是得先講講BST
BST（Binary Search Tree）是二叉查找樹的簡稱，其實很簡單水孩。大概的意思如下圖：
1镰矿、樹左邊的都比根小荷愕；
2衡怀、右邊都比根大；
3安疗、將規(guī)則遞歸到所有節(jié)點，就得到一顆BST够委。
細(xì)心的你會發(fā)現(xiàn)BST有個”bug“荐类，在插入的時候，如果是按照升序插入茁帽，那么就是一個鏈表了那么這時的查詢也從O(logn)退化到了O(n).
所以可以推斷玉罐，一顆好的查找樹一定是平衡的，而且最好是完美平衡的（任何節(jié)點的左右子樹深度都相等）潘拨，因為這樣它的查詢操作就會穩(wěn)定到O(logn)——也就是樹的高度了吊输。畢竟，在工程領(lǐng)域最重要的準(zhǔn)則就是——穩(wěn)定壓倒一切铁追！
3.2季蚂、2-3 tree
那么主角2-3 tree就登場了，為啥2-3樹是主角琅束？劇透一下扭屁，因為紅黑樹本質(zhì)就是2-3tree，而且”紅“就是2-3樹中的3節(jié)點涩禀，”黑“就是2節(jié)點料滥。下面詳細(xì)講解。
2-3 tree的定義其實很簡單:
1艾船、2-3tree是BST的一種葵腹，繼承所有BST的特點高每；
2、整棵樹由2-node與3-node組成践宴；
3觉义、2-node就是包含一個key節(jié)點，兩個左右子樹鏈接（對應(yīng)BST中的普通節(jié)點）浴井，3-node就是包含2個key晒骇，同時包含3個子樹鏈接的節(jié)點，就是3叉樹節(jié)點磺浙；
4洪囤、2-3樹是完美平衡的。
有圖更好理解：
可以看出來撕氧，2-node就是二叉樹普通節(jié)點瘤缩，3-node就是三叉樹的普通節(jié)點。那么2-3 tree是由2-node與3-node組成的完美平衡的搜索樹伦泥，通俗的講就是剥啤，這棵樹中根節(jié)點的左右子樹中2-3 node高度始終都一樣高。
怎么保持樹的完美平衡呢不脯？
我們通過例子看看插入的規(guī)則府怯，我們以順序插入1-10來作為例子，先不講規(guī)則防楷，我們看看例子牺丙，然后總結(jié)出規(guī)則，我們以依次向2-3 tree中插入1-10個數(shù)字的例子來演示复局。
1冲簿、插入1，只有一個節(jié)點亿昏，簡單：
2峦剔、插入2
3吝沫、插入3
這里說明下，2-3樹在插入過程中會臨時形成4-node（也就是有3個key彤断，4個子樹的node）野舶，而這時，4-node要馬上分解成3個2-node宰衙。
4平道、插入4
5、插入5
插入5的時候比較復(fù)雜供炼，臨時的4-node會分解成3個2-nodes一屋，這時會導(dǎo)致樹不平衡窘疮，右邊子樹高度+1，那么需要將3個2-node的中間節(jié)點向上融合（調(diào)平的重要步驟）冀墨。
6闸衫、插入6
7、插入7
可以看出插入7的結(jié)果會不斷將臨時4-node分裂成3個2-node诽嘉，并向上傳遞蔚出，最后會使樹的高度增加1，但是整個樹是完美平衡的虫腋。
8骄酗、插入8
9、插入9
10悦冀、插入10
好了趋翻，畫完了，樹中2-3節(jié)點完美平衡盒蟆。找到規(guī)律了么踏烙？沒有的話，我總結(jié)下：
1历等、在2-node中插入新節(jié)點讨惩，形成3-node，不破壞樹的平衡募闲，done步脓；
2、在3-node中插入新節(jié)點分為3步：
? ? 2.1浩螺、形成新的臨時4-node；
? ? 2.2仍侥、將4-node分解成3個2-node要出；
? ? 2.3、如果樹不平衡农渊，就將中間節(jié)點向上融合患蹂，重新遞歸1、2砸紊、兩個步驟传于，直到樹平衡。
看懂了么醉顽？是不是很簡單沼溜，如果沒有，就再看看上面的圖解吧~
3.3 重新發(fā)明紅黑樹
您可能會問游添，2-3 tree已經(jīng)很完美了系草，不管怎么插入數(shù)據(jù)通熄，只要根據(jù)"兩個"簡單的規(guī)則就能維持一個樹的完美平衡，為啥還要發(fā)明紅黑樹呢找都？
原因很簡單唇辨，工程實現(xiàn)難度！又是工程的實現(xiàn)難度能耻！說白了就是容易出bug……
跟hashmap一樣赏枚，實現(xiàn)一個工程可用的2-3tree是比較困難的（觀點來自于《算法》沒有親測）：
1、樹中間包含3種節(jié)點晓猛，相比BST來說意味著更多的判斷饿幅，比如，從4-node鞍帝，分裂成3個2-node诫睬，從2-node合并成3-node等等；情況多帕涌，編碼復(fù)雜摄凡；
2、各種node的節(jié)點在互相轉(zhuǎn)變的過程中需要拷貝的信息也比較多蚓曼，比如3-node可以有3個子樹亲澡，2-node有2個，那么融合的時候情況較多纫版，不能直接向BST一樣統(tǒng)一處理床绪，算法實現(xiàn)要處理的情況太多，容易出bug其弊；
3癞己、代碼不能重用（BST的代碼不能重用）。
但是我覺得最重要的是2-3 tree原理完美梭伐，但是結(jié)構(gòu)不完美痹雅。一個完美的數(shù)據(jù)結(jié)構(gòu)一定是原理與結(jié)構(gòu)都是統(tǒng)一的、樸素簡單的糊识。2-3 tree更像一個通向最終答案的中間解绩社，只要把中間的3-node與4-node這些tricky的node想辦法變換成2-node就結(jié)構(gòu)也統(tǒng)一完美了；那么BST的很多代碼就可以稍微修改一下就可以重用了（特別是刪除節(jié)點的代碼~）赂苗。
怎么統(tǒng)一呢愉耙？
方法其實也很簡單、直接拌滋，我們只要將2-3 tree在結(jié)構(gòu)上對齊BST朴沿，在保持平衡的原理上維持現(xiàn)狀不就行了？也就是西瓜芝麻都一起抓——去掉2-3 tree中的3-node鸠真。
3.3.1 去掉3-node
怎么去掉3-node悯仙？很簡單龄毡，真的很簡單，還是看圖說話：
就是把3-node拉直就行了锡垄！
更一般化的形式為
但是沦零，左子樹的高度加了1，那么結(jié)構(gòu)的算法特性有沒有發(fā)生改變呢货岭？
其實沒有路操，因為你依然可以把”4-7“這個紅色標(biāo)記的鏈接看做是一個3-node，那么它的搜索特性就沒有變化千贯。本質(zhì)來講屯仗，當(dāng)我們在2-3 tree里面做搜索的時候，當(dāng)我們碰到3-node的時候搔谴，其實就相當(dāng)于在節(jié)點內(nèi)部要比2-node多做一次比較魁袜，拉直了相當(dāng)于把這個多出來的比較形式化成了一條鏈接，計算量是沒有變化的敦第。
所以紅黑樹跟2-3 tree是完全等價的峰弹！或者說通過把2-3 tree中的3-node拉直而形成的BST樹就是——紅黑樹！
書中的例子芜果，更加清楚：
3.3.2 定義的解析
3.3.2.1 一些前提與說明
之前我們只是把邊涂成紅色鞠呈，但是BST是沒有邊的定義的，所以這個顏色只能記錄在節(jié)點的數(shù)據(jù)結(jié)構(gòu)中右钾，所以我們把從父節(jié)點到子節(jié)點的紅邊會存儲在子節(jié)點中——將子節(jié)點涂成紅色蚁吝，構(gòu)成紅色節(jié)點，其他的自然都是黑色節(jié)點舀射。
對于網(wǎng)上比較常見的一個紅黑樹例子：
細(xì)心的讀者會發(fā)現(xiàn)窘茁，這個根本不是一個2-3 tree，但是確實是紅黑樹脆烟，這是怎么回事庙曙？
因為紅黑樹定義有不同，相同節(jié)點的紅黑樹會根據(jù)定義不同產(chǎn)生不同的紅黑節(jié)點數(shù)量浩淘，如果直接從2-3tree轉(zhuǎn)的紅黑樹可能跟以上5條定義獲得的紅黑樹稍有不同，但是他們都是紅黑樹吴攒。
再來看看經(jīng)典紅黑樹的定義《導(dǎo)論》中的定義（針對的是節(jié)點顏色）：
?1.節(jié)點是紅色或黑色张抄。（貌似是廢話，難道對于紅黑樹還有第三種顏色洼怔？）
? ? 2.根節(jié)點是黑色署惯。（沒啥用）
? ? 3.每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）。
? ? 4 每個紅色節(jié)點的兩個子節(jié)點都是黑色镣隶。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
? ? 5.從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點极谊。
再看看《算法》中的定義（針對的是線的顏色）：
?1诡右、紅色的線永遠是左側(cè)鏈接彻秆；（強行的規(guī)定）
? 2摸屠、沒有一個節(jié)點同時鏈了兩條紅色的線；（也就是沒有3-node）
? 3播掷、任何從根到葉子節(jié)點的路徑上有相同顏色的黑線咙边。
可以看出定義是完全不同的（一個針對節(jié)點顏色猜煮，一個針對線的顏色——而線的顏色存在node中，所以還是紅黑樹）败许，但是都能構(gòu)成一棵紅黑樹王带。
而我們的解析是采用《算法》中的，因為它跟2-3 tree一一對應(yīng)市殷，很好理解愕撰。而《導(dǎo)論》中的定義是經(jīng)過2-3 tree，2-3-4 tree的抽象總結(jié)出來的非常通用抽象的解析醋寝，其經(jīng)過很多思維迭代后的結(jié)果搞挣，所以很抽象，但是本質(zhì)來說他們是一回事甥桂，是可以通過有限次推導(dǎo)（reduction）互相轉(zhuǎn)換的柿究。
那么下面我們對網(wǎng)上的例子做些轉(zhuǎn)換，將它化簡成一個2-3 tree的原型：
轉(zhuǎn)換得到的依然是紅黑樹黄选。
3.3.3 一步步構(gòu)建紅黑樹
還是通過依次插入1-10蝇摸，用《算法》中講述的紅黑線試圖來解析。
1办陷、插入1
很簡單……
2貌夕、插入2
rule1：插入的新節(jié)點跟父節(jié)點用red線連接
3、插入3
rule2：一個節(jié)點不能有兩個紅線相連（不是父子）民镜，否則就要通過旋轉(zhuǎn)將中間節(jié)點移動成父節(jié)點啡专。
rule3：如果一個節(jié)點父子都是紅線相連，則需要翻轉(zhuǎn)顏色制圈，并把父節(jié)點與祖父節(jié)點的鏈接變成紅色（也就是2-3 tree中分解4-node的時候们童，3個2-node中間的那個向上傳遞的過程）。
所以鲸鹦，可見紅黑樹中的翻轉(zhuǎn)其本質(zhì)就是將4-node分解成3個2-node慧库，并將中間節(jié)點與父節(jié)點融合的過程。
4馋嗜、插入4
插入4齐板，很簡單，紅線相連即可，因為每條路徑黑線數(shù)目一樣甘磨。
5橡羞、插入5
6、插入6
此時可以跟2-3 tree插入到6的圖比較下济舆，其實可以找到規(guī)律:->
是不是紅色線跟3-node一一對應(yīng)卿泽？
7、插入7
可以發(fā)現(xiàn)2-3 tree插入7也是4步吗冤，跟紅黑樹的旋轉(zhuǎn)變色的過程一一對應(yīng)又厉。
8、插入8
9椎瘟、插入9
10覆致、插入10
完畢，這就是一個以邊為視角的插入過程肺蔚，只需要將邊的顏色信息存儲到節(jié)點中就可以得到一棵紅黑樹：
總結(jié)下2-3tree與紅黑樹的操作對應(yīng)：
1煌妈、2-3 tree中的4-node分裂成3個2-node，并讓中間節(jié)點上移宣羊；等價于紅黑樹中的左右旋轉(zhuǎn)璧诵；
2、2-3tree中間節(jié)點上移與父節(jié)點融合過程仇冯；等價于紅黑樹中的反色操作之宿。
是不是很好理解了？
3.4 后續(xù)的操作
紅黑樹的插入操作我們解構(gòu)完了苛坚，我們還剩下一個比較復(fù)雜的刪除操作比被。這個操作其實是使用BST的標(biāo)準(zhǔn)刪除操作，一個比較標(biāo)準(zhǔn)的算法是泼舱，將要刪除節(jié)點的右子樹中的最小值（或者左子樹中最大值）替換掉當(dāng)前刪除的節(jié)點等缀，當(dāng)然針對不同的情況需要做些判斷。而且在工程領(lǐng)域娇昙，也會引入隨機的刪除左右子樹中的最大最小交替的方式尺迂，來完成刪除，以至于不會使得樹的稀疏度差異太大冒掌，從而降低搜索效率那是另一個范疇的事情了噪裕。
4、總結(jié)
紅黑樹是一個非常重要的股毫，而且在工程中常用的數(shù)據(jù)結(jié)構(gòu)州疾。比如jvm的hashmap，linux中還為紅黑樹單獨建立了數(shù)據(jù)結(jié)構(gòu)對象（linux內(nèi)核源碼的lib/rbtree.c文件）因為在linux內(nèi)核中的進程調(diào)度皇拣，虛擬內(nèi)存管理等操作頻繁而且性能critical的地方都會使用紅黑樹；另外在linux的epoll多路復(fù)用的模型中，核心數(shù)據(jù)結(jié)構(gòu)就是紅黑樹氧急。那么為什么紅黑樹這么好颗胡，一句話：
1、動態(tài)插入吩坝、刪除毒姨、查找都是O(logn)，而且只要內(nèi)存足夠钉寝，性能穩(wěn)定在這個數(shù)量級上弧呐；
2、工程上好實現(xiàn)嵌纲，編碼簡單俘枫。
