前言

前段時(shí)間在研究 JDK1.8 的 hashmap 源碼，看到 put 方法的插入環(huán)節(jié)驱闷，遇到了紅黑樹(shù)核偿，不得不停止閱讀源碼的過(guò)程，因?yàn)檫€沒(méi)掌握紅黑樹(shù)是無(wú)法完全讀透 hashmap 源碼的碳竟。紅黑樹(shù)作為一種數(shù)據(jù)結(jié)構(gòu)草丧，它被應(yīng)用得非常多，可能很多人不認(rèn)識(shí)它莹桅，但其實(shí)它已經(jīng)在默默為我們的代碼在發(fā)光發(fā)熱昌执。例如，你只要在 Java 中用到 map诈泼，基本上就是在用紅黑樹(shù)（當(dāng)元素個(gè)數(shù)到達(dá)八個(gè)時(shí)鏈表轉(zhuǎn)紅黑樹(shù)）懂拾。

PS：在看這篇文章前麦备，必須先了解普通的二叉查找樹(shù)和平衡查找樹(shù)（AVL）樹(shù)圣贸、2-3-4樹(shù)。不然看起來(lái)會(huì)非常吃力鞭莽。

歡迎加入交流群一起討論：611481448

紅黑樹(shù)的性質(zhì)

紅黑樹(shù)是一種自平衡樹(shù)瓮孙，它也是一顆二叉樹(shù)唐断。既然能保持平衡，說(shuō)明它和 AVL 樹(shù)類似杭抠，在插入或者刪除時(shí)肯定有調(diào)整的過(guò)程脸甘，只不過(guò)這個(gè)調(diào)整過(guò)程并不像 AVL 樹(shù)那樣繁瑣。為何紅黑樹(shù)使用得比 AVL 樹(shù)更多祈争，就是因?yàn)榧t黑樹(shù)它的調(diào)整過(guò)程迅速且簡(jiǎn)介斤程。紅黑樹(shù)有以下五個(gè)特性：

性質(zhì)1：節(jié)點(diǎn)是紅色或黑色

性質(zhì)2：根是黑色

性質(zhì)3：所有葉子都是黑色。葉子是 NIL 節(jié)點(diǎn)，也就是 Null 節(jié)點(diǎn)

性質(zhì)4：如果一個(gè)節(jié)點(diǎn)是紅的忿墅，則它的兩個(gè)兒子都是黑的

性質(zhì)5：從任一節(jié)點(diǎn)到其葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)扁藕。

下圖展示了一棵紅黑樹(shù)。

分析：

注意理解上疚脐，葉子并不等價(jià)于黑色節(jié)點(diǎn)亿柑，但是他們的顏色都是黑色。

為何要給節(jié)點(diǎn)指定紅或者黑的顏色棍弄？

作者這種設(shè)計(jì)望薄，只是為了從編程上達(dá)到一種便利的效果。另外可以讓它們?cè)诓迦霑r(shí)達(dá)到近似的平衡呼畸，并不像 AVL 樹(shù)那樣絕對(duì)平衡痕支。實(shí)際上，紅黑樹(shù)是2-3樹(shù)的一種變體蛮原，某種情況下卧须，它又相當(dāng)于2-3-4樹(shù)。因?yàn)?-3樹(shù)在編程上需要比較多的代碼量儒陨，所以誕生了紅黑樹(shù)這種巧妙的設(shè)計(jì)花嘶。通過(guò)加了顏色來(lái)區(qū)分結(jié)點(diǎn)，這樣編程上就可以當(dāng)成二叉樹(shù)來(lái)寫程序蹦漠，不用分別用三個(gè)指針表示左椭员、中、右孩子了笛园。

看一下紅黑樹(shù)和2-3樹(shù)的等價(jià)性聯(lián)系

從上面可以看到隘击，把紅色節(jié)點(diǎn)放到與父親齊平，就是2-3樹(shù)中的一個(gè)2-3節(jié)點(diǎn)研铆。

紅黑樹(shù)的操作

數(shù)據(jù)結(jié)構(gòu)的性質(zhì)看完之后闸度，就要掌握它到底會(huì)存在哪種操作？例如 hashmap蚜印，它最常見(jiàn)的操作就是 get 和 put莺禁、擴(kuò)容。同理窄赋，紅黑樹(shù)也有它的基本操作哟冬。因?yàn)樗旧砩弦彩且豢枚娌檎覙?shù)，所以重點(diǎn)關(guān)注的操作無(wú)非就是查找忆绰、插入浩峡、刪除。

1. 查找操作

紅黑樹(shù)的查找方式很簡(jiǎn)單错敢，只要是樹(shù)翰灾，查找的過(guò)程無(wú)非就是一個(gè)遞歸過(guò)程缕粹。如果查找的元素小于當(dāng)前節(jié)點(diǎn)，那么查找其左子樹(shù)纸淮；如果查找的元素大于當(dāng)前元素平斩，則查找其右子樹(shù)。

2. 插入操作

插入操作首先需要通過(guò)查找操作找到合適的插入點(diǎn)咽块，然后插入新節(jié)點(diǎn)绘面。如果在插入節(jié)點(diǎn)后，發(fā)生了違背紅黑樹(shù)特性的情況時(shí)侈沪，需要對(duì)紅黑樹(shù)進(jìn)行旋轉(zhuǎn)染色等操作揭璃，使其重新滿足特性。

2.1 插入新節(jié)點(diǎn)

為了在插入新節(jié)點(diǎn)時(shí)盡可能少的違反紅黑樹(shù)特性且更容易調(diào)整紅黑樹(shù)亭罪，就先將新節(jié)點(diǎn)染成紅色瘦馍。這樣就只可能會(huì)違反特性4。如果這里沒(méi)有違反特性4应役，那么就不需要對(duì)紅黑樹(shù)進(jìn)行調(diào)整扣墩，插入操作完成。

2.2 調(diào)整子樹(shù)

那么扛吞，在違反了特性4的時(shí)候，新節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色節(jié)點(diǎn)荆责。根據(jù)特性2可知滥比，父節(jié)點(diǎn)不是根節(jié)點(diǎn)，則新節(jié)點(diǎn)必有祖父節(jié)點(diǎn)做院。又根據(jù)特性3可推論出紅色節(jié)點(diǎn)必有兩個(gè)黑色子節(jié)點(diǎn)（空節(jié)點(diǎn)為黑色）盲泛。此時(shí)會(huì)出現(xiàn)兩種情況：叔節(jié)點(diǎn)為紅色、叔節(jié)點(diǎn)為黑色键耕。

圖例：C 表示當(dāng)前節(jié)點(diǎn)寺滚，P 表示父節(jié)點(diǎn)，U 表示叔節(jié)點(diǎn)屈雄，G 表示祖父節(jié)點(diǎn)

（1）父節(jié)點(diǎn)與叔節(jié)點(diǎn)都為紅色的情況

在這種情況下村视，需要將父節(jié)點(diǎn)和叔節(jié)點(diǎn)變?yōu)楹谏賹⒆娓腹?jié)點(diǎn)變?yōu)榧t色酒奶。這樣蚁孔，圖上所展示的子樹(shù)就滿足了紅黑樹(shù)的特性。如下圖所示惋嚎。

但是這里又可能會(huì)產(chǎn)生新的違反特性情況杠氢，因?yàn)樽娓腹?jié)點(diǎn)變成了紅色，那么它可能會(huì)造成違反特性4的情況另伍。所以鼻百，這里就將祖父節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，進(jìn)行新一輪的調(diào)整操作。

（2）父節(jié)點(diǎn)為紅色温艇，叔節(jié)點(diǎn)為黑色的情況

在這種情況下因悲，對(duì)其調(diào)整的核心就是保持父節(jié)點(diǎn)分支符合特性4，而叔節(jié)點(diǎn)分支保持符合特性5中贝。

第一步囤捻，旋轉(zhuǎn)。對(duì)祖父節(jié)點(diǎn)進(jìn)行左旋或者右旋邻寿。如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右子節(jié)點(diǎn)蝎土，那么對(duì)祖父節(jié)點(diǎn)進(jìn)行左旋；否則绣否，對(duì)祖父節(jié)點(diǎn)進(jìn)行右旋誊涯。

第二步，染色蒜撮。將祖父節(jié)點(diǎn)染為紅色暴构，而父節(jié)點(diǎn)染為黑色。

進(jìn)過(guò)這兩步段磨，上圖的情況會(huì)轉(zhuǎn)換為下圖所示取逾。

可以看出，父節(jié)點(diǎn)這一分支進(jìn)過(guò)調(diào)整后苹支，當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)的顏色不再是連續(xù)紅色砾隅，滿足特性4。而叔節(jié)點(diǎn)這一分支的黑色節(jié)點(diǎn)數(shù)目沒(méi)有發(fā)生變化债蜜，滿足特性5晴埂。對(duì)原祖父節(jié)點(diǎn)的父節(jié)點(diǎn)來(lái)說(shuō)，該子樹(shù)沒(méi)有發(fā)生違反特性的變化寻定。該子樹(shù)調(diào)整完成儒洛。

2.3 檢查根節(jié)點(diǎn)

當(dāng)上述調(diào)整執(zhí)行完后，還有最后一步狼速，就是檢查是否滿足特性2琅锻。這一步只需要將根節(jié)點(diǎn)染成黑色就可以，無(wú)需再多加判斷向胡。

3. 刪除操作

需要重點(diǎn)理解的就是刪除操作浅浮，這個(gè)也是我覺(jué)得是紅黑樹(shù)中最難的部分。

刪除操作要比插入操作略微復(fù)雜一些捷枯。因?yàn)閯h除的節(jié)點(diǎn)可能是出現(xiàn)在樹(shù)的中間層的節(jié)點(diǎn)滚秩，此時(shí)刪除該節(jié)點(diǎn)會(huì)遇到很復(fù)雜的情況。所以淮捆，在刪除節(jié)點(diǎn)的時(shí)候郁油，需要先對(duì)紅黑樹(shù)進(jìn)行一些調(diào)整本股，使得刪除節(jié)點(diǎn)對(duì)整個(gè)樹(shù)的影響降到最低。

3.1 替換刪除節(jié)點(diǎn)

首先根據(jù) BST 刪除節(jié)點(diǎn)的規(guī)則桐腌，使用當(dāng)前節(jié)點(diǎn)左子樹(shù)的最大值節(jié)點(diǎn)或者右子樹(shù)的最小值節(jié)點(diǎn)代替其刪除拄显。這兩個(gè)節(jié)點(diǎn)是其子樹(shù)中數(shù)值上最貼近當(dāng)前節(jié)點(diǎn)數(shù)值的節(jié)點(diǎn)）。 這一點(diǎn)案站，只要懂了二叉查找樹(shù)的刪除操作就明白了躬审，在這里不多說(shuō)了。如下圖所示：

圖例：D 表示當(dāng)前節(jié)點(diǎn)蟆盐，P 表示父節(jié)點(diǎn)承边，B 表示兄弟節(jié)點(diǎn)，BR 表示兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)石挂，BL 表示兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)

既然待刪除節(jié)點(diǎn)是要被移走的博助，那肯定有一個(gè)節(jié)點(diǎn)要替換到它的位置上去。如何找到這個(gè)替換節(jié)點(diǎn)痹愚，這個(gè)過(guò)程和二叉查找樹(shù)一模一樣富岳，要么在它的左子樹(shù)下一直往右找到最大節(jié)點(diǎn)，要么在右子樹(shù)下找到最小節(jié)點(diǎn)拯腮。

下面的描述過(guò)程采用的是右子樹(shù)的最小值節(jié)點(diǎn)代替

當(dāng)找到替換節(jié)點(diǎn)之后窖式，現(xiàn)在需要考慮的情況就減少了，只可能會(huì)出現(xiàn)以下幾種情況（因?yàn)樾枰獫M足紅黑樹(shù)特性）：

無(wú)子節(jié)點(diǎn)动壤，節(jié)點(diǎn)為紅色

無(wú)子節(jié)點(diǎn)萝喘，節(jié)點(diǎn)為黑色

只有右子節(jié)點(diǎn)，右子節(jié)點(diǎn)為紅色狼电，節(jié)點(diǎn)本身為黑色

上面這三種情況，說(shuō)的是新待刪除節(jié)點(diǎn)弦蹂。新待刪除節(jié)點(diǎn)肩碟，就是即將被替換到待刪除位置的節(jié)點(diǎn)。

因?yàn)?D 節(jié)點(diǎn)就是即將要替換到待刪節(jié)點(diǎn)位置的節(jié)點(diǎn)凸椿，它同時(shí)又是右子樹(shù)的最小值削祈，既然是最小值了，它就不再可能擁有左子樹(shù)了脑漫，所以只有可能有右子節(jié)點(diǎn)髓抑。另外，假如它有右節(jié)點(diǎn)且右節(jié)點(diǎn)的顏色是黑色优幸，它自身顏色是紅色吨拍，根本不成立。因?yàn)榧偃缢陨頌榧t色且又有黑孩子网杆，那它必須要有兩個(gè)黑孩子才滿足紅黑樹(shù)性質(zhì)羹饰，所以不滿足伊滋。 那有沒(méi)有可能，它自身是黑色且右孩子也為黑色呢队秩？也不可能笑旺！因?yàn)樗蠛⒆右呀?jīng)為空了，說(shuō)明它從自身出發(fā)到左子樹(shù)的葉子的距離就是1馍资，假如它右孩子也為黑色筒主，那它從自身出發(fā)到右子樹(shù)葉子的距離肯定大于等于2了，明顯不可能鸟蟹。

所以總的來(lái)說(shuō)只可能有下面三種情況：

情況1：只需要直接刪除節(jié)點(diǎn)就可以乌妙。刪了一個(gè)紅色新待刪節(jié)點(diǎn)，不會(huì)影響紅黑樹(shù)性質(zhì)戏锹。

情況2：刪除該 D 節(jié)點(diǎn)后冠胯，違反了紅黑樹(shù)特性5，需要調(diào)整（不考慮待刪除節(jié)點(diǎn)為根節(jié)點(diǎn)的情況）

情況3：用右子節(jié)點(diǎn) R 占據(jù)待刪除節(jié)點(diǎn) D锦针，再將其染成黑色即可荠察，不違反紅黑樹(shù)特性。因?yàn)樽筮叡緛?lái)就是空了奈搜，其實(shí)右子樹(shù)下即使有多少個(gè)黑色節(jié)點(diǎn)悉盆，也不會(huì)影響整體特性。

在這三種情況中馋吗，情況1和情況3比較簡(jiǎn)單焕盟，不需要多余的調(diào)整。情況2則需要后續(xù)的調(diào)整步驟使其滿足紅黑樹(shù)特性宏粤。

3.2 調(diào)整紅黑樹(shù)

上述情況2的調(diào)整比較復(fù)雜脚翘。下面對(duì)各種情況進(jìn)行講解。

根據(jù)紅黑樹(shù)的特性5绍哎，待刪除節(jié)點(diǎn)必然有兄弟節(jié)點(diǎn)来农。

為什么這么說(shuō)呢？因?yàn)槲覀円呀?jīng)假設(shè)上面的 D 節(jié)點(diǎn)不為根了崇堰，那說(shuō)明它肯定有父親沃于。首先它是沒(méi)有孩子的，它下面直接就是葉子了海诲，既然有父親繁莹，不論它是父親的左孩子或者右孩子，從父親出發(fā)到它自身特幔，黑色節(jié)點(diǎn)的個(gè)數(shù)為1咨演。反證法：假如父親只有它一個(gè)孩子，那說(shuō)明父親到另一邊子樹(shù)的葉子距離就為0蚯斯，因?yàn)?個(gè)節(jié)點(diǎn)雪标。這明顯不符合零院，所以說(shuō)明父親肯定有兩個(gè)孩子，那從而得知待刪節(jié)點(diǎn)D必有兄弟村刨。

下面根據(jù)其兄弟節(jié)點(diǎn)所在分支的不同告抄，來(lái)分情況討論。

以下是以關(guān)注待刪節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)進(jìn)行描述嵌牺，如果遇到關(guān)注節(jié)點(diǎn)為父節(jié)點(diǎn)的右子節(jié)點(diǎn)的情況打洼，則鏡像處理。

思路：下面的任何調(diào)整只有一個(gè)目的逆粹，就是不斷調(diào)整募疮，直到調(diào)整到可以直接將 D 移除又不會(huì)影響紅黑樹(shù)特性的情況。但關(guān)鍵是調(diào)整過(guò)程中紅黑樹(shù)特性也不會(huì)發(fā)生改變僻弹。

圖例：D 表示當(dāng)前節(jié)點(diǎn)阿浓，P 表示父節(jié)點(diǎn)，B 表示兄弟節(jié)點(diǎn)蹋绽，BR 表示兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn)芭毙，BL 表示兄弟節(jié)點(diǎn)的左子節(jié)點(diǎn)

（1）兄弟節(jié)點(diǎn)為紅色

將父節(jié)點(diǎn)染成紅色，兄弟節(jié)點(diǎn)染成黑色卸耘，然后對(duì)父節(jié)點(diǎn)進(jìn)行左旋操作退敦。此時(shí)就轉(zhuǎn)換為了下面的（4），之后按照（4）繼續(xù)進(jìn)行調(diào)整蚣抗。

分析：這種情況侈百，樹(shù)的整體高度為2，變色左旋之后翰铡，整體高度還是保持在2钝域。

（2）兄弟節(jié)點(diǎn)為黑色，遠(yuǎn)侄節(jié)點(diǎn)為紅色

這種情況下锭魔，不需要考慮父節(jié)點(diǎn)的顏色例证。

將父節(jié)點(diǎn) P 與兄弟節(jié)點(diǎn) B 的顏色互換 ，這個(gè)過(guò)程父親染黑

將兄弟節(jié)點(diǎn)的右子節(jié)點(diǎn) BR 染成黑色

對(duì)父節(jié)點(diǎn) P 進(jìn)行左旋操作

可以看到赂毯，原本高度就是符合紅黑樹(shù)特性的战虏，左右子樹(shù)的高度都為1拣宰，因?yàn)楹谏?jié)點(diǎn)只有一個(gè)党涕。經(jīng)過(guò)這三步的調(diào)整后，直接刪除節(jié)點(diǎn) D 后仍然滿足紅黑樹(shù)的特性巡社，調(diào)整完成膛堤，跳出算法循環(huán)。

（3）兄弟節(jié)點(diǎn)為黑色晌该，遠(yuǎn)侄節(jié)點(diǎn)為黑色肥荔，近侄節(jié)點(diǎn)為紅色

這種情況下绿渣，兄弟節(jié)點(diǎn)的左節(jié)點(diǎn)染成黑色。兄弟節(jié)點(diǎn)染紅燕耿。然后對(duì)兄弟節(jié)點(diǎn)做右旋中符。此時(shí)的狀況就和（2）一樣了。之后就通過(guò)（2）的調(diào)整方式進(jìn)行調(diào)整誉帅。

（4）父節(jié)點(diǎn)為紅色淀散，兄弟節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)

這種情況下蚜锨，將父節(jié)點(diǎn)P染成黑色档插，再將兄弟節(jié)點(diǎn)染成紅色。經(jīng)過(guò)這樣的操作后亚再，除去節(jié)點(diǎn)D后郭膛，以P為根節(jié)點(diǎn)的子樹(shù)的黑節(jié)點(diǎn)深度并沒(méi)有發(fā)生變化。調(diào)整完成氛悬。

怎么理解這個(gè)操作则剃？

可以看左邊，沒(méi)調(diào)整前圆雁，P 的左右子樹(shù)的黑色結(jié)點(diǎn)的數(shù)目都是1忍级，是相同的，符合紅黑樹(shù)的性質(zhì)：從任一節(jié)點(diǎn)到其葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)伪朽。然后再看右邊轴咱，調(diào)整后，刪掉 D 之后烈涮，P 結(jié)點(diǎn)的左右子樹(shù)的黑色結(jié)點(diǎn)都是0個(gè)朴肺，仍然滿足性質(zhì)，所以調(diào)整完成坚洽。

（5）父節(jié)點(diǎn)為黑色戈稿，兄弟節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)

這種情況下讶舰，為了在刪除節(jié)點(diǎn) D 后使以 P 為根節(jié)點(diǎn)的子樹(shù)能滿足紅黑樹(shù)特性5鞍盗，將兄弟節(jié)點(diǎn) B 染成紅色。但是這樣操作后跳昼，以 P 為根節(jié)點(diǎn)的子樹(shù)的黑色節(jié)點(diǎn)深度變小了般甲。所以需要繼續(xù)調(diào)整。

因?yàn)镻節(jié)點(diǎn)子樹(shù)的黑色深度發(fā)生了減少鹅颊，可以把其當(dāng)作待刪除節(jié)點(diǎn)敷存，那么此時(shí)就以 P 節(jié)點(diǎn)為關(guān)注節(jié)點(diǎn)進(jìn)行進(jìn)一步調(diào)整（繼續(xù)向上調(diào)整）。 這句話的意思我們?cè)僖?P 為起始點(diǎn)堪伍，繼續(xù)根據(jù)情況進(jìn)行平衡操作锚烦。就是把 P 當(dāng)成 D觅闽，只是不要再刪除 P 了。再看是這五種中的哪種情況涮俄，再進(jìn)行對(duì)應(yīng)的調(diào)整蛉拙，這樣一直向上，直到新的起始點(diǎn)為根節(jié)點(diǎn)或者關(guān)注節(jié)點(diǎn)不為黑色彻亲。

第五種情況刘离，不會(huì)一直連續(xù)回溯的。假如能一直回溯睹栖，指針向上走之后硫惕，兄弟節(jié)點(diǎn)會(huì)一直都沒(méi)有右孩子嗎？不存在的野来。假如有這種情況恼除，說(shuō)明樹(shù)的路徑長(zhǎng)度已經(jīng)嚴(yán)重往左傾斜，肯定不可能曼氛。所以回溯這個(gè)情況只會(huì)回溯一次豁辉，不會(huì)連續(xù)回溯。第五個(gè)這種情況出現(xiàn)之后舀患，下一次進(jìn)入算法循環(huán)徽级，肯定就是進(jìn)入其他情況，直到遇到 break聊浅，跳出循環(huán)餐抢，終止整個(gè)算法過(guò)程。

3.3 檢查根節(jié)點(diǎn)及刪除節(jié)點(diǎn)

經(jīng)過(guò)上述的調(diào)整后低匙，此時(shí)基本滿足了紅黑樹(shù)的特性旷痕。但是存在根節(jié)點(diǎn)變成紅色的情況。所以需要將根節(jié)點(diǎn)染成黑色的操作顽冶。 最后欺抗，執(zhí)行刪除操作，將待刪除節(jié)點(diǎn)刪掉强重。

當(dāng)然從編程的角度绞呈，你也可以調(diào)整指針先把待刪除節(jié)點(diǎn)移掉，然后再開(kāi)始平衡調(diào)整過(guò)程间景。注意這里說(shuō)的平衡調(diào)整佃声，并不是 AVL 樹(shù)的絕對(duì)平衡調(diào)整，而是滿足紅黑樹(shù)特性的平衡調(diào)整拱燃。紅黑樹(shù)的平衡和 AVL 的平衡是有區(qū)別的秉溉。

總結(jié)

紅黑樹(shù)的刪除操作是整個(gè)紅黑樹(shù)中最復(fù)雜的一部分力惯，理解了這部分碗誉，紅黑樹(shù)就算基本拿下了召嘶。理解完一種數(shù)據(jù)結(jié)構(gòu)，要能 get 到作者當(dāng)初設(shè)計(jì)時(shí)的點(diǎn)哮缺，才算是一次積累弄跌。紅黑樹(shù)的刪除操作，它非常地巧妙尝苇，整一個(gè)算法循環(huán)過(guò)程铛只，它不會(huì)超過(guò)三次，調(diào)整過(guò)程基本都在子樹(shù)內(nèi)完成糠溜，指針不需要一直向上回溯淳玩，相比 AVL 樹(shù)，AVL 樹(shù)在刪除節(jié)點(diǎn)時(shí)非竿，指針有可能會(huì)一直回溯到根為止蜕着。

”我自己是一名從事了十余年的后端的老程序員，辭職后目前在做講師红柱，近期我花了一個(gè)月整理了一份最適合2018年學(xué)習(xí)的JAVA干貨（里面有高可用承匣、高并發(fā)、高性能及分布式锤悄、Jvm性能調(diào)優(yōu)韧骗、Spring源碼，MyBatis零聚，Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等多個(gè)知識(shí)點(diǎn)的架構(gòu)資料）從事后端的小伙伴們都可以來(lái)了解一下的袍暴，這里是程序員秘密聚集地，各位還在架構(gòu)師的道路上掙扎的小伙伴們速來(lái)隶症∪菸埽“

加QQ群：611481448（名額有限哦！）