本篇主要寫的是結(jié)合之前分析的2-3-4樹和紅黑樹之間的聯(lián)系分析紅黑樹的插入刪除操作的原理艰匙。我剛剛開始學(xué)紅黑樹時在網(wǎng)上找紅黑樹相關(guān)資料大多都是以公式模式的方式說明在特性情況下需要變換旋轉(zhuǎn)哪些節(jié)點读处，但是為什么要怎么旋轉(zhuǎn)里面的原理是什么并沒有說明丹锹。本篇就主要圍繞紅黑樹和2-3-4樹插入時的對比結(jié)合我自己的理解來說明紅黑樹插入時變化的思想扒接。
背景知識
紅黑樹和2-3-4樹的結(jié)構(gòu)對應(yīng)
在說明插入刪除操作之前先結(jié)合之前2-3-4樹和紅黑樹之間對比說明一下它們之間的對應(yīng)關(guān)系精钮。
這個對應(yīng)關(guān)系看過前面一篇2-3-4樹和紅黑樹對應(yīng)關(guān)系文章的應(yīng)該就不難理解恕齐。只不過這里4node節(jié)點對應(yīng)的紅黑樹形態(tài)有穩(wěn)定和不穩(wěn)定兩種狀態(tài)乞娄。怎么理解這個穩(wěn)定和不穩(wěn)定狀態(tài)呢？簡單的說穩(wěn)定的狀態(tài)當(dāng)4node節(jié)點一般是紅黑樹在變化完成以后我們能夠看到的狀態(tài)显歧，而不穩(wěn)定的狀態(tài)一般都是出現(xiàn)在我們添加時向上遞歸的時候出現(xiàn)的情況仪或，當(dāng)出現(xiàn)不穩(wěn)定狀態(tài)的4node節(jié)點時都需要我們通過變色+旋轉(zhuǎn)來轉(zhuǎn)變?yōu)榉€(wěn)定狀態(tài)。
二叉樹的旋轉(zhuǎn)
在分析紅黑樹插入時會涉及到二叉樹的旋轉(zhuǎn)士骤，所以這里就先說明一下旋轉(zhuǎn)的操作邏輯范删。
先說一下我是怎么記左旋右旋操作的，一句話：左旋左下拷肌，右旋右下到旦。什么意思呢？就是說對一個節(jié)點左旋以后它會向左下移動巨缘，而當(dāng)一個節(jié)點右旋以后它會向右下移動添忘。至于左旋以后右子樹的左子和右旋時右子樹的左子變化邏輯可以看下圖來理解。
左旋左下若锁，右子樹的左子變化邏輯：
右旋右下搁骑，左子樹的右子變化邏輯：
上面記錄的是我自己的理解，如果感覺太抽象還是沒明白那也可以去百度谷歌一下又固，網(wǎng)上講這個的資料還是挺多的仲器。
紅黑樹的局部調(diào)整
之前說了紅黑樹對應(yīng)的2-3-4樹4node的情況右兩種，一種是穩(wěn)定狀態(tài)一種是不穩(wěn)定狀態(tài)仰冠，而不穩(wěn)定狀態(tài)可以通過變色+旋轉(zhuǎn)來變?yōu)榉€(wěn)定狀態(tài)乏冀，那具體是怎么個旋轉(zhuǎn)變色。很簡單如下圖所示：
而紅黑樹在插入時全都是圍繞2node 3node 4node之間的轉(zhuǎn)化來進(jìn)行的沪停，本質(zhì)上和2-3-4樹是一樣的煤辨。至于這里的不穩(wěn)定狀態(tài)變成穩(wěn)定狀態(tài)也是為了紅黑樹在執(zhí)行下一步操作時維護(hù)之前提到的不能有連續(xù)兩個紅色節(jié)點相連的規(guī)則裳涛，以及保證紅黑樹相對平衡的高度而進(jìn)行的。
紅黑樹的插入
紅黑樹的插入是在搜索二叉樹的插入基礎(chǔ)上再對樹進(jìn)行變換讓樹保持相對平衡來完成的众辨。在我自己學(xué)習(xí)紅黑樹插入操作時有部分網(wǎng)上資料是根據(jù)2-3樹來對紅黑樹插入時各個狀態(tài)對比說明的端三，感覺也有一些復(fù)雜需要經(jīng)過幾次的變換（需要對紅黑樹轉(zhuǎn)換成左傾紅黑樹再轉(zhuǎn)換成2-3）。我這里就結(jié)合兩種說明鹃彻，先根據(jù)大部分資料中提到的規(guī)則來變換郊闯，再對這些變換的核心思想通過和2-3-4樹的對比來加以說明。
首先這里需要明確的是紅黑樹在插入時蛛株，新的節(jié)點永遠(yuǎn)都是紅色的团赁。從紅黑樹的角度上說明因為紅黑樹中插入紅色節(jié)點才不會讓紅黑樹的結(jié)構(gòu)發(fā)生變化（所有路徑黑色節(jié)點數(shù)不發(fā)生變化）。從2-3-4樹的角度上看插入節(jié)點為紅色的意思就是新的節(jié)點永遠(yuǎn)都是第一時間想著“并入”到指定的節(jié)點之中谨履，這和2-3-4樹的思想是一致的欢摄。
首先分析紅黑樹插入節(jié)點時最簡單的情況，也就是被插入的新節(jié)點的父節(jié)點為黑色笋粟，這種情況從2-3-4樹的角度上可以理解成新節(jié)點直接被“并入”到老節(jié)點之中怀挠，結(jié)構(gòu)沒有發(fā)生變化，自然也不需要什么操作害捕。從紅黑樹的角度上來講绿淋，向黑色節(jié)點下面插入紅色子節(jié)點自然不會影響紅黑樹中的任一一個性質(zhì)（沒有連續(xù)紅色節(jié)點，黑色節(jié)點數(shù)也沒有發(fā)生變化）尝盼。這種情況的具體操作邏輯如下圖：
如圖吞滞，這就是紅黑樹中插入時最簡單的情況，下面將會繼續(xù)分情況說明插入時變換的操作以及操作對應(yīng)的2-3-4樹的比較盾沫。
情況一
狀態(tài)：
- 新插入節(jié)點的父節(jié)點為紅色裁赠；
- 新插入節(jié)點的祖父的另外一個子節(jié)點（叔叔節(jié)點）也為紅色。
操作：
- 將新插入節(jié)點的父節(jié)點從紅色染成黑色疮跑；
- 將新插入節(jié)點的祖父的另外一個子節(jié)點（叔叔節(jié)點）從紅色染成黑色组贺；
- 將新插入節(jié)點的祖父節(jié)點從黑色染成紅色；
理解：
這一系列操作看著只有一頓變色祖娘，也沒有對樹進(jìn)行旋轉(zhuǎn)失尖，那它的這一頓變色究竟有什么意義？先整理一下在操作變色以前樹的結(jié)構(gòu)是怎么樣的一種情況渐苏。
上圖就是當(dāng)前情況一的紅黑樹狀態(tài)掀潮，新插入的節(jié)點為“40”。接下來根據(jù)情況一對應(yīng)的操作看看變換以后紅黑樹的狀態(tài)琼富，以及變換前后它們和2-3-4樹之間的關(guān)系仪吧。
（注：上圖已經(jīng)把葉子節(jié)點都去掉了，因為葉子節(jié)點對分析沒有什么幫助鞠眉，而且圖畫起來也比較麻煩薯鼠。另外紅黑樹轉(zhuǎn)2-3-4樹時也只做了對分析有關(guān)的一部分變換择诈。后面的圖也會去掉葉子節(jié)點來分析）
如上圖【步驟1】，根據(jù)上述規(guī)則變換以后父節(jié)點“25”出皇，叔叔節(jié)點“35”將都變成黑色羞芍，而祖父節(jié)點“30”變成紅色；如果只根據(jù)【步驟1】很難看出紅黑樹經(jīng)過顏色變化到底發(fā)生了什么情況郊艘，那根據(jù)變化前后紅黑樹對應(yīng)的2-3-4樹來一起分析荷科。
根據(jù)上圖【步驟2】結(jié)合之前紅黑樹和2-3-4樹對應(yīng)轉(zhuǎn)換關(guān)系，紅節(jié)點向上連接的線為紅線纱注，紅線連接的節(jié)點可以組成一個node畏浆，那么可以看出在變化前節(jié)點“25”，“30”狞贱，“35”形成的是一個4node刻获。而這個時候向紅黑樹新插入節(jié)點“40”的操作也就等同于向“25”，“30”斥滤，“35”組成的4node中插入一個節(jié)點“40”将鸵。
如圖【步驟4】在向4node中插入節(jié)點“40”后會發(fā)生“進(jìn)位”（在2-3-4中向4node中插入節(jié)點的一系列的操作在前面一片文章中已經(jīng)做了介紹，如果有一些遺忘的可以返回去再看看）佑颇，而被“進(jìn)位”的是節(jié)點“30”。那么當(dāng)前可以理解為被“進(jìn)位”的節(jié)點“30”就是一個新插入的節(jié)點了草娜。
這里為什么可以把進(jìn)位的節(jié)點理解成一個新插入的節(jié)點挑胸？從兩個角度來分析：
首先從紅黑樹的角度理解，通過變化顏色（就是上述對新插入節(jié)點的父節(jié)點和叔叔節(jié)點的變色）讓以節(jié)點“30”為根節(jié)點的子樹中黑色節(jié)點的個數(shù)和變化顏色以前保持一致宰闰，那么自然將以節(jié)點“30”為根的子樹被插入到它的父親節(jié)點下面后茬贵，黑色節(jié)點到數(shù)量也不會發(fā)生變化，而這個時候如果出現(xiàn)一些不符合紅黑樹要求的情況移袍，就需要按照情況來分析解決解藻，怎么解決？就和一個新節(jié)點插入時的解決方案一樣葡盗。因此這里可以理解成把節(jié)點“30”當(dāng)作一個新的節(jié)點來插入到它的父節(jié)點下面螟左，然后再做具體分析。
從2-3-4樹的角度理解觅够，被“進(jìn)位”的那個節(jié)點也就是被分裂出去的節(jié)點可以被理解為一個新節(jié)點來“合并”到它的父親節(jié)點中（分裂完成子樹的高度沒有發(fā)生變化）胶背。當(dāng)然如果父親節(jié)點也是4node那就繼續(xù)分裂，這個時候“進(jìn)位”的就是父親節(jié)點4node中發(fā)生進(jìn)位分裂的那個節(jié)點數(shù)據(jù)了喘先，就這樣層層遞歸直到被分裂節(jié)點的數(shù)據(jù)能夠被合并到它的父節(jié)點中或到達(dá)根節(jié)點钳吟。
當(dāng)上面節(jié)點“進(jìn)位”完成，那就繼續(xù)上述分析下一個步驟——一個新插入的節(jié)點被加入到一個黑色的節(jié)點下面這一情況窘拯，而這種情況通過之前分析可得知不做任何變化红且，具體邏輯如圖【步驟5】坝茎。對于2-3-4樹來說就是相當(dāng)于節(jié)點“30”被合并到原來的根節(jié)點“20”中，形成一個新的3node根節(jié)點“20”暇番，“30”景东。可以發(fā)現(xiàn)之前紅黑樹一頓變換顏色的操作奔誓，看著樹結(jié)構(gòu)沒有發(fā)生變化實則已經(jīng)發(fā)生了進(jìn)位斤吐，2-3-4樹已經(jīng)發(fā)生了很大的變化，根節(jié)點已經(jīng)從2node變換成3node了厨喂。而上述的規(guī)則中的變色其實是通過改變節(jié)點的顏色間接的改變了連線的顏色從而最終改變了節(jié)點的顏色和措；
總結(jié)：
根據(jù)上述分析情況一變色操作即可以理解成一種“進(jìn)位”，將原本由父蜕煌，祖父派阱，叔叔組成的4node進(jìn)行“進(jìn)位”以后再做添加。
思考：
上面描述的情況其實只是其中的一種情況斜纪。還有一種情況贫母，就是當(dāng)前添加節(jié)點的祖父節(jié)點的父節(jié)點是紅色的，那通過上述操作以后祖父節(jié)點變成紅色了）那這時祖父節(jié)點和祖父的父節(jié)點不就形成了兩個紅色的節(jié)點了盒刚？那就不符合紅黑樹的規(guī)則了腺劣。而出現(xiàn)這種情況又需要怎么變換？這個時候就涉及到下面要分析的情況二了因块。
情況二
狀態(tài)：
- 當(dāng)前新插入節(jié)點的父節(jié)點是祖父節(jié)點的右子樹橘原；
- 當(dāng)前新插入節(jié)點是父親節(jié)點的右子；
- 新插入節(jié)點的父節(jié)點是紅色涡上；
- 新插入節(jié)點的祖父節(jié)點的另外一個子節(jié)點（叔叔節(jié)點）是黑色趾断；
操作：
- 將新插入節(jié)點的父節(jié)點從紅色設(shè)為黑色；
- 將新插入的祖父節(jié)點從黑色設(shè)為紅色吩愧；
- 以祖父節(jié)點為支點左旋
理解：
情況二看著條件和操作感覺非常的復(fù)雜一會兒要變色一會兒要旋轉(zhuǎn)芋酌，不僅要操作父節(jié)點還要操作祖父節(jié)點。還是一樣先上圖看看具體是什么情況雁佳。
這里我順帶的把情況二出現(xiàn)的其中一種場景也畫了一下脐帝，為了一起把分析情況一時出現(xiàn)的另外一種情況也一起分析了（本質(zhì)上都是情況二）。如圖甘穿，根據(jù)情況一的分析中我們在變色完成以后即可以把進(jìn)位的節(jié)點“35”理解成一個新插入的節(jié)點腮恩。這個時候就已經(jīng)全部滿足上述情況二中狀態(tài)描述的情況了，也就是出現(xiàn)來兩個連續(xù)的紅色節(jié)點温兼。
這里我們先不急著變化秸滴，先看一下情況二的結(jié)構(gòu)。
這個時候出現(xiàn)了不穩(wěn)定4node募判。在分析插入操作之前我們已經(jīng)分析了紅黑樹中出現(xiàn)不穩(wěn)定4node的時候需要怎么旋轉(zhuǎn)荡含，這里再重新回顧一下咒唆。
好了現(xiàn)在回過頭來看看，是不是我們之前把不穩(wěn)定的4node轉(zhuǎn)為穩(wěn)定4node的過程就是情況二操作的描述過程释液。
總結(jié)：
情況二中一系列的描述以及操作總結(jié)起來其實就是將一個不穩(wěn)定的4node狀態(tài)的紅黑樹轉(zhuǎn)化成一個穩(wěn)定的4node狀態(tài)節(jié)點全释。因此這里我也極其不建議去記當(dāng)前的情況和面對當(dāng)前情況需要做的變換操作第一步第二步第三步等等，我們只需要知道在什么狀態(tài)下我們需要讓它變成什么狀態(tài)（如：“不穩(wěn)定狀態(tài)”變?yōu)椤胺€(wěn)定狀態(tài)”）误债。
情況三
情況三其實和情況二的本質(zhì)是一樣的浸船，這里只是多出一步將“規(guī)則”的4node整理成“規(guī)則”的4node。這里引入一個“規(guī)則”寝蹈，“不規(guī)則”這么兩個概念李命，那就先說明一下什么是“規(guī)則”的4node，就是黑節(jié)點連接的兩個紅色節(jié)點在一條直接上箫老，或者兩個紅色節(jié)點位于黑色節(jié)點的兩邊封字。我們上述說的都是規(guī)則的4node（雖然它們有一些是不穩(wěn)定）。而不規(guī)則的呢耍鬓？如下圖：（基于不穩(wěn)定4node阔籽，類似一個左右箭頭的形狀）
上圖就是不規(guī)則的4node狀態(tài)。那怎么形成規(guī)則（不穩(wěn)定）的4node牲蜀？只要旋轉(zhuǎn)一下就可以了笆制，具體如下圖：
好了了解了怎么把不規(guī)則4node轉(zhuǎn)成規(guī)則（不穩(wěn)定）的4node以后就可以繼續(xù)分析情況三了。
（注：上述的“規(guī)則”各薇，“不規(guī)則”完全是個人的理解项贺，不是官方的定義，是我自己定義的名稱）
狀態(tài)：
- 當(dāng)前插入節(jié)點的父節(jié)點是祖父節(jié)點的右子樹峭判；
- 當(dāng)前新插入節(jié)點是父親節(jié)點的左子；
- 新插入節(jié)點的父節(jié)點是紅色棕叫；
- 新插入節(jié)點的祖父節(jié)點的另外一個子節(jié)點（叔叔節(jié)點）是黑色林螃；
操作：
- 將新插入節(jié)點的父節(jié)點右旋，并將父親節(jié)點定義為新插入節(jié)點
- 將新插入節(jié)點的父節(jié)點從紅色設(shè)為黑色俺泣；
- 將新插入的祖父節(jié)點從黑色設(shè)為紅色疗认；
- 以祖父節(jié)點為支點左旋
理解：
仔細(xì)觀察狀態(tài)都只和情況二有少許的不同，直接看上面的描述很難明白是怎么回事伏钠，那就繼續(xù)用圖片來說明吧横漏。
仍然繼續(xù)剛剛的那個例子但是有稍作修改，這里把原來的節(jié)點“12”拿掉了這樣節(jié)點“15”的左子就變成了一個黑色的NIL節(jié)點熟掂，然后繼續(xù)往這個紅黑樹中插入一個大小為“16”的節(jié)點缎浇。這樣就是當(dāng)前分析的情況三了。是不是非常像情況二的樣子（如果插入的節(jié)點大小為“19”那就是情況二了）赴肚。仔細(xì)看這里邊是不是存在一個不規(guī)則的4node素跺。而看到不規(guī)則的4node在做變換以前首先就需要通過樹的旋轉(zhuǎn)讓它成為一個規(guī)則的4node二蓝。因此具體操作如下：
當(dāng)?shù)玫揭粋€規(guī)則的4node時，接下來你根據(jù)上述操作會發(fā)現(xiàn)其實和情況二的操作是一樣的指厌。這里我就不具體再做說明了刊愚，不懂的可以回到情況二對比著看看，下面直接放個圖：
總結(jié)：
情況三本質(zhì)上其實就是情況二的另一種狀態(tài)踩验，多出的一步其實就是讓“不規(guī)則”的4node轉(zhuǎn)換成“規(guī)則”的4node鸥诽，剩下的邏輯就是得到一個不穩(wěn)定的4node，然后通過變色旋轉(zhuǎn)得到一個穩(wěn)定的4node箕憾。這里的轉(zhuǎn)換因為都是并入節(jié)點且變色旋轉(zhuǎn)都是為了維護(hù)紅黑樹的性質(zhì)牡借，本質(zhì)就是為了下次插入（或刪除）做好準(zhǔn)備，而這里對應(yīng)夠2-3-4樹其實結(jié)構(gòu)上是沒有發(fā)生變化的（沒有發(fā)生進(jìn)位）厕九。
紅黑樹插入總結(jié)
通過紅黑樹和2-3-4樹對比分析可以總結(jié)出紅黑樹蓖捶，在插入時如果發(fā)生“進(jìn)位”，則是通過變色來完成節(jié)點數(shù)據(jù)的分裂扁远，而如果是并入操作俊鱼，則是通過將“不規(guī)則”轉(zhuǎn)為“規(guī)則”4node，而“規(guī)則”4node不穩(wěn)定狀態(tài)通過旋轉(zhuǎn)變色變成穩(wěn)定4node狀態(tài)畅买。其實核心只要記住一句話“變色分裂并闲，不規(guī)則轉(zhuǎn)規(guī)則，不穩(wěn)定轉(zhuǎn)穩(wěn)定”谷羞，并且記住那些基礎(chǔ)的不穩(wěn)定以及不規(guī)則形狀的特征以及變換方法就可以很簡單的記憶紅黑樹插入時的操作了帝火。這也是為什么我在講插入之前先說明一下紅黑樹局部調(diào)整的方法，因為插入操作的邏輯基本都是圍繞這個局部調(diào)整方法（不穩(wěn)定轉(zhuǎn)穩(wěn)定）做出變化的湃缎。
對紅黑樹刪除的分析因為篇幅原因就放到后面一篇來講解來犀填。如果對上述分析說明有什么疑問的或者有什么建議的都可以留言，大家一起交流學(xué)習(xí)嗓违。
