紅黑樹和AVL樹的思想是類似的剪撬，都是在插入過程中對二叉排序樹進(jìn)行調(diào)整，從而提升性能悠反，它的增刪改查均可以在O(lg n)內(nèi)完成残黑。
本文會從定義到實(shí)現(xiàn)一棵紅黑樹展開馍佑，還會簡單介紹其與AVL樹的異同。
定義
紅黑樹是一棵二叉排序樹梨水。且滿足以下特點(diǎn)：
- 每個節(jié)點(diǎn)或者是黑色拭荤，或者是紅色。
- 根節(jié)點(diǎn)是黑色疫诽。
- 每個葉子節(jié)點(diǎn)（NIL）是黑色舅世。 [注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)奇徒！]
- 如果一個節(jié)點(diǎn)是紅色的雏亚，則它的兩個兒子都是黑色的。
- 從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)摩钙。
下圖就是一棵簡單的紅黑樹示例：
示例中每個結(jié)點(diǎn)最后都是一個NIL結(jié)點(diǎn)罢低，它是黑色的，不過我們畫圖時通常會省略它胖笛。所以下文以及后續(xù)文章中繪制時都會省略NIL結(jié)點(diǎn)网持，大家記得還有它就可以。
實(shí)現(xiàn)原理
紅黑樹的插入與刪除和AVL樹類似匀钧，也是每插入一個結(jié)點(diǎn)翎碑，都檢查是否破壞了樹的結(jié)構(gòu)，然后進(jìn)行調(diào)整之斯。紅黑樹每個結(jié)點(diǎn)插入時默認(rèn)都為紅色日杈，這樣做可以降低黑高，也可以減少調(diào)整的次數(shù)佑刷。
插入元素
紅黑樹的概念理解起來較為復(fù)雜莉擒，我們以一個簡單的示例，看看如何構(gòu)造一棵紅黑樹瘫絮。
現(xiàn)有數(shù)組int[] a = {1, 10, 9, 2, 3, 8, 7, 4, 5, 6};我們要將其變?yōu)橐豢眉t黑樹涨冀。
首先插入1，此時樹是空的麦萤，1就是根結(jié)點(diǎn)鹿鳖，根結(jié)點(diǎn)是黑色的：
然后插入元素10，此時依然符合規(guī)則壮莹，結(jié)果如下：
當(dāng)插入元素9時翅帜，這時是需要調(diào)整的第一種情況，結(jié)果如下：
紅黑樹規(guī)則4中強(qiáng)調(diào)不能有兩個相鄰的紅色結(jié)點(diǎn)命满，所以此時我們需要對其進(jìn)行調(diào)整涝滴。調(diào)整的原則有多個相關(guān)因素，這里的情況是，父結(jié)點(diǎn)10是其祖父結(jié)點(diǎn)1（父結(jié)點(diǎn)的父結(jié)點(diǎn)）的右孩子歼疮，當(dāng)前結(jié)點(diǎn)9是其父結(jié)點(diǎn)10的左孩子杂抽，且沒有叔叔結(jié)點(diǎn)（父結(jié)點(diǎn)的兄弟結(jié)點(diǎn)），此時需要進(jìn)行兩次旋轉(zhuǎn)韩脏，第一次缩麸，以父結(jié)點(diǎn)10右旋：
然后將父結(jié)點(diǎn)（此時是9）染為黑色，祖父結(jié)點(diǎn)1染為紅色骤素，如下所示：
然后以祖父結(jié)點(diǎn)1左旋：
下一步匙睹，插入元素2，結(jié)果如下：
此時情況與上一步類似济竹，區(qū)別在于父結(jié)點(diǎn)1是祖父結(jié)點(diǎn)9的左孩子，當(dāng)前結(jié)點(diǎn)2是父結(jié)點(diǎn)的右孩子霎槐，且叔叔結(jié)點(diǎn)10是紅色的送浊。這時需要先將叔叔結(jié)點(diǎn)10染為黑色，再進(jìn)行下一步操作丘跌，具體做法是將父結(jié)點(diǎn)1和叔叔結(jié)點(diǎn)10染為黑色袭景，祖父結(jié)點(diǎn)9染為紅色，如下所示：
由于結(jié)點(diǎn)9是根節(jié)點(diǎn)闭树，必須為黑色耸棒，將它染為黑色即可：
下一步，插入元素3报辱，如下所示：
這和我們之前插入元素10的情況一模一樣与殃，需要將父結(jié)點(diǎn)2染為黑色，祖父結(jié)點(diǎn)1染為紅色碍现，如下所示：
然后左旋：
下一步幅疼，插入元素8，結(jié)果如下：
此時和插入元素2有些類似昼接，區(qū)別在于父結(jié)點(diǎn)3是右孩子爽篷，當(dāng)前結(jié)點(diǎn)8也是右孩子，這時也需要先將叔叔結(jié)點(diǎn)1染為黑色慢睡，具體操作是先將1和3染為黑色逐工，再將祖父結(jié)點(diǎn)2染為紅色，如下所示：
此時樹已經(jīng)平衡了漂辐，不需要再進(jìn)行其他操作了泪喊，現(xiàn)在插入元素7，如下所示：
這時和之前插入元素9時一模一樣了者吁，先將7和8右旋窘俺，如下所示：
然后將7染為黑色，3染為紅色，再進(jìn)行左旋瘤泪，結(jié)果如下：
下一步要插入的元素是4灶泵，結(jié)果如下：
這里和插入元素2是類似的，先將3和8染為黑色对途，7染為紅色赦邻，如下所示：
但此時2和7相鄰且顏色均為紅色，我們需要對它們繼續(xù)進(jìn)行調(diào)整实檀。這時情況變?yōu)榱烁附Y(jié)點(diǎn)2為紅色惶洲，叔叔結(jié)點(diǎn)10為黑色，且2為左孩子膳犹，7為右孩子恬吕，這時需要以2左旋。這時左旋與之前不同的地方在于結(jié)點(diǎn)7旋轉(zhuǎn)完成后將有三個孩子须床，結(jié)果類似于下圖：
這種情況處理起來也很簡單铐料，只需要把7原來的左孩子3，變成2的右孩子即可豺旬，結(jié)果如下：
然后再把2的父結(jié)點(diǎn)7染為黑色钠惩，祖父結(jié)點(diǎn)9染為紅色。結(jié)果如下所示：
此時又需要右旋了族阅，我們要以9右旋篓跛，右旋完成后7又有三個孩子，這種情況和上述是對稱的坦刀，我們把7原有的右孩子8愧沟，變成9的左孩子即可，如下所示：
下一個要插入的元素是5求泰，插入后如下所示：
有了上述一些操作央渣，處理5變得十分簡單，將3染為紅色渴频，4染為黑色芽丹，然后左旋，結(jié)果如下所示：
最后插入元素6卜朗，如下所示：
又是叔叔結(jié)點(diǎn)3為紅色的情況拔第，這種情況我們處理過多次了，首先將3和5染為黑色场钉，4染為紅色蚊俺，結(jié)果如下：
此時問題向上傳遞到了元素4，我們看2逛万、4泳猬、7、9的顏色和位置關(guān)系，這種情況我們也處理過得封，先將2和9染為黑色埋心，7染為紅色，結(jié)果如下：
最后7是根結(jié)點(diǎn)忙上，染為黑色即可拷呆，最終結(jié)果如下所示：
可以看到，在插入元素時疫粥，叔叔結(jié)點(diǎn)是主要影響因素茬斧，待插入結(jié)點(diǎn)與父結(jié)點(diǎn)的關(guān)系決定了是否需要多次旋轉(zhuǎn)」４可以總結(jié)為以下幾種情況：
如果父結(jié)點(diǎn)是黑色项秉，插入即可，無需調(diào)整慷彤。
如果叔叔結(jié)點(diǎn)是紅色伙狐，就把父結(jié)點(diǎn)和叔叔結(jié)點(diǎn)都轉(zhuǎn)為黑色，祖父結(jié)點(diǎn)轉(zhuǎn)為紅色瞬欧，將不平衡向上傳遞。
如果叔叔結(jié)點(diǎn)是黑色或者沒有叔叔結(jié)點(diǎn)罢防，就看父結(jié)點(diǎn)和待插入結(jié)點(diǎn)的關(guān)系艘虎。如果待插入結(jié)點(diǎn)和父結(jié)點(diǎn)的關(guān)系，與父結(jié)點(diǎn)與祖父結(jié)點(diǎn)的關(guān)系一致咒吐，比如待插入結(jié)點(diǎn)是父結(jié)點(diǎn)的左孩子野建，父結(jié)點(diǎn)也是祖父結(jié)點(diǎn)的左孩子，就無需多次旋轉(zhuǎn)恬叹。否則就先通過相應(yīng)的旋轉(zhuǎn)將其關(guān)系變?yōu)橐恢隆?/p>
刪除元素
要從一棵紅黑樹中刪除一個元素候生，主要分為三種情況。
情況1：待刪除元素沒有孩子
沒有孩子指的是沒有值不為NIL的孩子绽昼。這種情況下唯鸭，如果刪除的元素是紅色的，可以直接刪除硅确，如果刪除的元素是黑色的目溉，就需要進(jìn)行調(diào)整了。
例如我們從下圖中刪除元素1：
刪除元素1后菱农，2的左孩子為NIL缭付，這條支路上的黑色結(jié)點(diǎn)數(shù)就比其他支路少了，所以需要進(jìn)行調(diào)整循未。
這時陷猫，我們的關(guān)注點(diǎn)從叔叔結(jié)點(diǎn)轉(zhuǎn)到兄弟結(jié)點(diǎn)，也就是結(jié)點(diǎn)4，此時4是紅色的绣檬，就把它染為黑色足陨，把父結(jié)點(diǎn)2染為紅色，如下所示：
然后以2左旋河咽，結(jié)果如下：
此時兄弟結(jié)點(diǎn)為3钠右，且它沒有紅色的孩子，這時只需要把它染為紅色忘蟹，父結(jié)點(diǎn)2染為黑色即可飒房。結(jié)果如下所示：
情況2：待刪除元素有一個孩子
這應(yīng)該是刪除操作中最簡單的一種情況了，根據(jù)紅黑樹的定義媚值，我們可以推測狠毯，如果一個元素僅有一個孩子，那么這個元素一定是黑色的褥芒，而且其孩子是紅色的嚼松。
假設(shè)我們有一個紅色節(jié)點(diǎn)，它是樹中的某一個節(jié)點(diǎn)锰扶，且僅有一個孩子献酗，那么根據(jù)紅色節(jié)點(diǎn)不能相鄰的條件，它的孩子一定是黑色的坷牛，如下所示：
但這個子樹的黑高卻不再平衡了（注意每個節(jié)點(diǎn)的葉節(jié)點(diǎn)都是一個NIL節(jié)點(diǎn)）罕偎，因此紅色節(jié)點(diǎn)不可能只有一個孩子。
而若是一個黑色節(jié)點(diǎn)僅有一個孩子京闰，如果其孩子是黑色的颜及，同樣會打破黑高的平衡，所以其孩子只能是紅色的蹂楣，如下所示：
只有這一種情況符合紅黑樹的定義俏站，這時要刪除這個元素，只需要使用其孩子代替它痊土，僅代替值而不代替顏色即可肄扎，上圖的情況刪除完后變?yōu)椋?/p>
可以看到，樹的黑高并沒有發(fā)生變化施戴，因此也不需要進(jìn)行調(diào)整反浓。
情況3：待刪除元素有兩個孩子
我們在討論二叉排序樹時說過，如果刪除一個有兩個孩子的元素赞哗，可以使用它的前驅(qū)或者后繼結(jié)點(diǎn)代替它雷则。因?yàn)樗那膀?qū)或者后繼結(jié)點(diǎn)最多只會有一個孩子，所以這種情況可以轉(zhuǎn)為情況1或情況2處理肪笋。
總結(jié)
刪除元素最復(fù)雜的是情況1月劈，這主要由其兄弟結(jié)點(diǎn)以及兄弟結(jié)點(diǎn)的孩子顏色共同決定度迂。這里簡要做下總結(jié)。
我們以N代表當(dāng)前待刪除節(jié)點(diǎn)猜揪，以P代表父結(jié)點(diǎn)惭墓，以S代表兄弟結(jié)點(diǎn)，以SL代表兄弟結(jié)點(diǎn)的左孩子而姐，SR代表兄弟結(jié)點(diǎn)的右孩子腊凶，如下所示：
根據(jù)紅黑樹定義，這種情況下S要么有紅色的子結(jié)點(diǎn)拴念，要么只有NIL結(jié)點(diǎn)钧萍，以下對S有黑色結(jié)點(diǎn)的情況均表示NIL
主要有以下幾種：
- S是紅色，P一定是黑色政鼠，S也不會有紅色的孩子风瘦，如下：
此時把P和S顏色變換，再左旋公般，如下：
這樣變換后万搔，N支路上的黑色結(jié)點(diǎn)并沒有增加，所以依然少一個官帘，
- P瞬雹，S以及S的全部孩子都是黑色
無論S有幾個孩子，或者沒有孩子刽虹，只要不是紅色都是這種情況挖炬，此時情況如下：
我們把S染為紅色，這樣一來状婶，N和S兩個支路都少了一個黑色結(jié)點(diǎn)，所以可以把問題向父結(jié)點(diǎn)轉(zhuǎn)移馅巷，通過遞歸解決膛虫。染色后如下：
- P為紅（S一定為黑），S的孩子都為黑
這種情況最為簡單钓猬，只需要把P和S顏色交換即可稍刀。這樣N支路多了一個黑色元素，而S支路沒有減少敞曹，所以達(dá)到了平衡账月。
- P任意色，S為黑澳迫，N是P的左孩子局齿，S的右孩子SR為紅，S的左孩子任意
如下所示
此時將S改為P的顏色橄登，SR和P改為黑色抓歼，然后左旋讥此，結(jié)果如下：
可以發(fā)現(xiàn)，此時N支路多了一個黑色結(jié)點(diǎn)谣妻，而其余支路均沒有收到影響萄喳，所以調(diào)整完畢。
-
P任意色蹋半，S為黑他巨，N是P的左孩子，S的左孩子SL為紅减江，S的右孩子SR為黑染突，如下所示：
SR黑色
此時變換S和SL的顏色，然后右旋您市，結(jié)果如下：
這時觉痛，所有分支的黑色結(jié)點(diǎn)數(shù)均沒有改變，但情況5轉(zhuǎn)為了情況4茵休，再進(jìn)行一次操作即可薪棒。
還有一些情況與上述是對稱的，我們進(jìn)行相應(yīng)的轉(zhuǎn)換即可榕莺。
總結(jié)
紅黑樹的操作比較復(fù)雜俐芯，插入元素可能需要多次變色與旋轉(zhuǎn)，刪除也是钉鸯。這些操作的目的都是為了保證紅黑樹的結(jié)構(gòu)不被破壞吧史。這些復(fù)雜的插入與刪除操作希望大家可以親手嘗試一下，以加深理解唠雕。
紅黑樹是JDK中TreeMap贸营、TreeSet的底層數(shù)據(jù)結(jié)構(gòu)，在JDK1.8中HashMap也用到了紅黑樹岩睁，所以掌握它對我們后續(xù)的分析十分重要钞脂。
關(guān)于紅黑樹與AVL樹的區(qū)別，以及為何選用紅黑樹捕儒，已經(jīng)不屬于我們的討論范圍冰啃，大家可以查閱相關(guān)資料進(jìn)一步了解。
上一篇：Java集合源碼分析之基礎(chǔ)（五）：平衡二叉樹（AVL Tree）
我是飛機(jī)醬刘莹，如果您喜歡我的文章阎毅，可以關(guān)注我~
編程之路，道阻且長点弯。唯扇调，路漫漫其修遠(yuǎn)兮，吾將上下而求索抢肛。
