????作為一名年輕的叫獅撩笆，開(kāi)發(fā)斜杠能力，做一名斜杠青年缸浦，小編私以為還是很重要的夕冲，沒(méi)有什么工作是絕對(duì)的穩(wěn)定，真正穩(wěn)定的裂逐，是你的才華和能力歹鱼。這一周，小編在工作之余卜高，上網(wǎng)翻閱了各種資料弥姻，認(rèn)識(shí)了一遍紅黑樹(shù)南片，并把查閱到的這些資料整理歸納了一遍，至少也是一種知識(shí)的存檔庭敦。
一疼进、導(dǎo)論
????R-B Tree，全稱(chēng)是Red-Black Tree螺捐，又稱(chēng)為“紅黑樹(shù)”颠悬，是一種特殊的二叉查找樹(shù)。紅黑樹(shù)的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色定血，可以是紅(Red)或黑(Black)赔癌。紅黑樹(shù)（Red Black Tree） 是一種自平衡二叉查找樹(shù)，是在計(jì)算機(jī)科學(xué)中用到的一種數(shù)據(jù)結(jié)構(gòu)澜沟，典型的用途是實(shí)現(xiàn)關(guān)聯(lián)數(shù)組灾票。它是在1972年由Rudolf Bayer發(fā)明的，當(dāng)時(shí)被稱(chēng)為平衡二叉B樹(shù)（symmetric binary B-trees）茫虽。后來(lái)刊苍，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的“紅黑樹(shù)”。
二濒析、基本性質(zhì)
? ??在算法導(dǎo)論里正什，是這樣去定義一棵紅黑樹(shù)的：
????（1）每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色号杏。
????（2）根節(jié)點(diǎn)是黑色婴氮。
????（3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色【注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)盾致！】
????（4）如果一個(gè)節(jié)點(diǎn)是紅色的主经，則它的子節(jié)點(diǎn)必須是黑色的。
????（5）對(duì)于每個(gè)節(jié)點(diǎn)庭惜，從該節(jié)點(diǎn)到其子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑色節(jié)點(diǎn)【也就是說(shuō)從根節(jié)點(diǎn)（如下圖13根節(jié)點(diǎn)）到其所有的nil黑節(jié)點(diǎn)路徑里的黑節(jié)點(diǎn)數(shù)就是一樣的罩驻。確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍。因而护赊，紅黑樹(shù)是相對(duì)是接近平衡的二叉樹(shù)惠遏。】
????對(duì)于紅黑樹(shù)來(lái)說(shuō)骏啰，任意節(jié)點(diǎn)到空的葉子節(jié)點(diǎn)的所有路徑中爽哎，沒(méi)有一條路徑會(huì)大于其他路徑的兩倍（換句話說(shuō)就是任何一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差不會(huì)超過(guò)二者中較低那個(gè)的一倍）
????紅黑樹(shù)使用紅黑二色進(jìn)行“著色”，目的是利用顏色值作為二叉樹(shù)的平衡對(duì)稱(chēng)性的檢查器一，只要插入的節(jié)點(diǎn)“著色”滿(mǎn)足紅黑二色的規(guī)定，最短路徑與最長(zhǎng)路徑不會(huì)相差的太遠(yuǎn)厨内，紅黑樹(shù)的節(jié)點(diǎn)分布就能大體上達(dá)至均衡祈秕。
三渺贤、紅黑樹(shù)的應(yīng)用
????紅黑樹(shù)的應(yīng)用比較廣泛，主要是用它來(lái)存儲(chǔ)有序的數(shù)據(jù)请毛，它的時(shí)間復(fù)雜度是O(logn)志鞍，效率非常之高。
????例如方仿，Java集合中的TreeSet和TreeMap固棚，C++ STL中的set、map仙蚜，以及Linux虛擬內(nèi)存的管理此洲，都是通過(guò)紅黑樹(shù)去實(shí)現(xiàn)的。
四委粉、紅黑樹(shù)的時(shí)間復(fù)雜度和相關(guān)證明
????紅黑樹(shù)的時(shí)間復(fù)雜度為:?O(logn)
????下面通過(guò)“數(shù)學(xué)歸納法”對(duì)紅黑樹(shù)的時(shí)間復(fù)雜度進(jìn)行證明呜师。
? ??證明：
????“一棵含有n個(gè)節(jié)點(diǎn)的紅黑樹(shù)的高度至多為2log(n+1)”轉(zhuǎn)換一下就是“高度為h的紅黑樹(shù)，它的包含的內(nèi)節(jié)點(diǎn)個(gè)數(shù)至少為 2^(h/2)-1個(gè)”贾节。
????我們只需要證明后面那個(gè)命題汁汗，即可證明原命題為真；即只需證明“高度為h的紅黑樹(shù)栗涂，它的包含的內(nèi)節(jié)點(diǎn)個(gè)數(shù)至少為 2^(h/2)-1個(gè)”知牌。
????從某個(gè)節(jié)點(diǎn)x出發(fā)（不包括該節(jié)點(diǎn)）到達(dá)一個(gè)它子孫外部節(jié)點(diǎn)的任意一條路徑上，黑色節(jié)點(diǎn)的個(gè)數(shù)稱(chēng)為該節(jié)點(diǎn)的黑高度(x's black height)斤程，記為bh(x)角寸。關(guān)于bh(x)有兩點(diǎn)需要說(shuō)明：
? ??第1點(diǎn)：根據(jù)紅黑樹(shù)的“特性(5)，即從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫外部節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)”可知暖释，從節(jié)點(diǎn)x出發(fā)到達(dá)的所有的葉節(jié)點(diǎn)具有相同數(shù)目的黑節(jié)點(diǎn)袭厂。這也就意味著，bh(x)的值是唯一的球匕！
? ??第2點(diǎn)：根據(jù)紅黑色的“特性(4)纹磺，即如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的”可知亮曹，從節(jié)點(diǎn)x出發(fā)達(dá)到葉節(jié)點(diǎn)“所經(jīng)歷的黑節(jié)點(diǎn)數(shù)目”>= “所經(jīng)歷的紅節(jié)點(diǎn)的數(shù)目”橄杨。假設(shè)x是根節(jié)點(diǎn)，則可以得出結(jié)論“bh(x) >= h/2”照卦。進(jìn)而式矫，我們只需證明“高度為h的紅黑樹(shù)，它的包含的內(nèi)節(jié)點(diǎn)個(gè)數(shù)至少為 2^bh(x)-1個(gè)”即可役耕。
????到這里采转，我們將需要證明的定理已經(jīng)由“一棵含有n個(gè)節(jié)點(diǎn)的紅黑樹(shù)的高度至多為2log(n+1)”轉(zhuǎn)變成只需要證明“高度為h以x為根的紅黑樹(shù)，它的包含的內(nèi)節(jié)點(diǎn)個(gè)數(shù)至少為 2^bh(x)-1個(gè)”。
????下面通過(guò)"數(shù)學(xué)歸納法“開(kāi)始論證高度為h以x為根的紅黑樹(shù)故慈，它的包含的內(nèi)節(jié)點(diǎn)個(gè)數(shù)至少為 2^bh(x)-1個(gè)”板熊。
（1）當(dāng)樹(shù)的高度h=0時(shí)，內(nèi)節(jié)點(diǎn)個(gè)數(shù)是0察绷，bh(x) 為0干签，2^bh(x)-1 也為 0。顯然拆撼，原命題成立容劳。
（2）考慮x的左右子節(jié)點(diǎn)，它們包含的節(jié)點(diǎn)個(gè)數(shù)至少為 2^(bh(x)-1)-1闸度。推導(dǎo)理由如下：對(duì)于節(jié)點(diǎn)x(x為根節(jié)點(diǎn))竭贩，其黑高度為bh(x)。對(duì)于節(jié)點(diǎn)x的左右子樹(shù)筋岛，當(dāng)它們?yōu)榧t色時(shí)娶视，黑高度為 bh(x)；當(dāng)它們?yōu)楹谏珪r(shí)睁宰，黑高度為bh(x)-1肪获。因此，x的左右子節(jié)點(diǎn)所包含的節(jié)點(diǎn)個(gè)數(shù)至少為2^(bh(x)-1)-1（因?yàn)楹诟叨茸钌贋閎h(x)-1）柒傻。
（3）根據(jù)（2）孝赫，我們已知“x的左右子樹(shù)，即高度為 h-1 的節(jié)點(diǎn)红符，它包含的節(jié)點(diǎn)至少為 2^(bh(x)-1)-1 個(gè)”青柄；所以，節(jié)點(diǎn)x所包含的節(jié)點(diǎn)至少為 (2^(bh(x)-1)-1 ) + (2^( bh(x)-1)-1) + 1 = 2^bh(x)-1预侯。即節(jié)點(diǎn)x所包含的節(jié)點(diǎn)至少為 2^bh(x)-1致开。
????因此，原命題成立萎馅。
????由（1）双戳、（2）得出，“高度為h的紅黑樹(shù)糜芳，它的包含的內(nèi)節(jié)點(diǎn)個(gè)數(shù)至少為 2^bh(x)-1個(gè)”飒货。
????因此，“一棵含有n個(gè)節(jié)點(diǎn)的紅黑樹(shù)的高度至多為2log(n+1)”峭竣。
? ??因此塘辅，從根節(jié)點(diǎn)到任意節(jié)點(diǎn)最多經(jīng)歷2log(n+1)步，因此紅黑樹(shù)的時(shí)間復(fù)雜度為O(lgn)皆撩。
五扣墩、樹(shù)的平衡性的修正方法
????紅黑樹(shù)主要的特征：
????① 節(jié)點(diǎn)都有顏色；
????② 在插入和刪除的過(guò)程中，要遵循保持這些顏色的不同排列的規(guī)則沮榜。
????首先第一個(gè)特征很好解決盘榨，在節(jié)點(diǎn)類(lèi)中添加一個(gè)數(shù)據(jù)字段，例如boolean型變量蟆融，以此來(lái)表示節(jié)點(diǎn)的顏色信息。第二個(gè)特征比較復(fù)雜守呜，紅黑樹(shù)有它的幾個(gè)規(guī)則型酥，如果遵循這些規(guī)則，那么樹(shù)就是平衡的查乒。
????在紅黑樹(shù)中插入的節(jié)點(diǎn)都是紅色的弥喉，這不是偶然的，因?yàn)椴迦胍粋€(gè)紅色節(jié)點(diǎn)比插入一個(gè)黑色節(jié)點(diǎn)違背紅-黑規(guī)則的可能性更小玛迄。原因是：插入黑色節(jié)點(diǎn)總會(huì)改變黑色高度（違背規(guī)則4）由境，但是插入紅色節(jié)點(diǎn)只有一半的機(jī)會(huì)會(huì)違背規(guī)則3。另外違背規(guī)則3比違背規(guī)則4要更容易修正蓖议。紅黑樹(shù)在插入后可能會(huì)導(dǎo)致樹(shù)的不平衡虏杰，所以要進(jìn)行分析，看是否需要變色勒虾，左旋纺阔，右旋。
????1修然、變色
????改變節(jié)點(diǎn)顏色比較容易理解笛钝，因?yàn)樗`背了規(guī)則3。
????2愕宋、左旋
????左旋是將E的右子樹(shù)繞E逆時(shí)針旋轉(zhuǎn)玻靡，使得E的右子樹(shù)成為E的父親，同時(shí)修改相關(guān)節(jié)點(diǎn)的引用中贝，旋轉(zhuǎn)之后囤捻，要求二叉查找樹(shù)的屬性依然滿(mǎn)足。
????左旋有個(gè)很萌萌噠的動(dòng)態(tài)示意圖雄妥，可以方便理解：
????3最蕾、右旋
????右旋是將S的左子樹(shù)繞S順時(shí)針旋轉(zhuǎn)，使得S的左子樹(shù)成為S的父親老厌，同時(shí)注意修改相關(guān)節(jié)點(diǎn)的引用瘟则，旋轉(zhuǎn)之后要求仍然滿(mǎn)足搜索樹(shù)的屬性。
????當(dāng)然咯枝秤，右旋也有個(gè)萌萌的動(dòng)態(tài)圖：
六醋拧、紅黑樹(shù)的插入
????① 插入節(jié)點(diǎn)為根節(jié)點(diǎn)
????由于原樹(shù)為空，所以只會(huì)違反紅黑樹(shù)的規(guī)則2，所以只要把根節(jié)點(diǎn)涂黑即可丹壕；
????② 插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的
????那不會(huì)違背紅黑樹(shù)的規(guī)則庆械，什么也不需要做；
????③?當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色菌赖，且當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)的另一個(gè)節(jié)點(diǎn)（叔叔節(jié)點(diǎn)）也是紅色缭乘。
? ??處理策略：
????（01）父節(jié)點(diǎn)設(shè)置黑色
????（02）叔叔節(jié)點(diǎn)設(shè)置黑色
????（03）祖父節(jié)點(diǎn)設(shè)置紅色
????（04）設(shè)置祖父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)
????（5）未完，然后又將爺爺節(jié)點(diǎn)當(dāng)作插入節(jié)點(diǎn)看待琉用，一直進(jìn)行上述操作堕绩。直到當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)，然后將根節(jié)點(diǎn)變成黑色邑时。
? ??④當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色奴紧，叔叔節(jié)點(diǎn)是黑色
? ??1）父親節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左孩子，新插入節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子（左左）
? ??處理策略：
????（01）將父親節(jié)點(diǎn)和爺爺節(jié)點(diǎn)顏色互換（父節(jié)點(diǎn)變?yōu)楹谏穑瑺敔敼?jié)點(diǎn)變?yōu)榧t色）
????（02）設(shè)祖父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)黍氮，對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行一次右旋
????2）父親節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右孩子，新插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右孩子（右右）
? ??處理策略：
????（01）將父親節(jié)點(diǎn)和爺爺節(jié)點(diǎn)顏色互換（父節(jié)點(diǎn)變?yōu)楹谏掣。瑺敔敼?jié)點(diǎn)變?yōu)榧t色）
????（02）對(duì)爺爺節(jié)點(diǎn)進(jìn)行一次左旋
????3）父親節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左孩子沫浆，新插入節(jié)點(diǎn)為父節(jié)點(diǎn)的右孩子（左右）
? ??處理策略：
????對(duì)父親節(jié)點(diǎn)進(jìn)行一次左旋，然后就變成了情況1）脑题，按照情況1）再進(jìn)行處理
? ?4）父親節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右孩子件缸，新插入節(jié)點(diǎn)為父節(jié)點(diǎn)的左孩子（右左）
? ??處理策略：
????對(duì)父親節(jié)點(diǎn)進(jìn)行一次右旋，然后就變成了情況2）叔遂，按照情況2）再進(jìn)行處理
????接下來(lái)他炊，我們通過(guò)一個(gè)例子來(lái)看看如何通過(guò)插入數(shù)據(jù)來(lái)生成一棵紅黑樹(shù)。這里已艰，我們插入的數(shù)據(jù)為275痊末、711、260哩掺、515凿叠、442、800嚼吞、900盒件、50、270舱禽、20炒刁、30。
? ??插入275誊稚，滿(mǎn)足①
????根節(jié)點(diǎn)翔始，涂為黑色罗心。
? ??插入711，滿(mǎn)足②
? ??插入260城瞎，滿(mǎn)足②
? ??插入515
????滿(mǎn)足情況③
????第一步設(shè)置父節(jié)點(diǎn)711設(shè)置黑色渤闷，第二步叔叔節(jié)點(diǎn)260設(shè)置黑色、第三步設(shè)置祖父節(jié)點(diǎn)275設(shè)置紅色脖镀，第四步設(shè)置祖父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)飒箭。
????由于當(dāng)前節(jié)點(diǎn)275為根節(jié)點(diǎn)，修改為黑色蜒灰。
? ??插入442
????滿(mǎn)足情況④中的1）补憾，第一步將父親節(jié)點(diǎn)515和爺爺節(jié)點(diǎn)711顏色互換（父節(jié)點(diǎn)變?yōu)楹谏瑺敔敼?jié)點(diǎn)變?yōu)榧t色）卷员，然后對(duì)爺爺節(jié)點(diǎn)711進(jìn)行一次右旋。
? ??插入800
????滿(mǎn)足情況③腾务，第一步設(shè)置父節(jié)點(diǎn)711設(shè)置黑色毕骡，第二步叔叔節(jié)點(diǎn)442設(shè)置黑色、第三步設(shè)置祖父節(jié)點(diǎn)515設(shè)置紅色岩瘦，第四步設(shè)置祖父節(jié)點(diǎn)515為當(dāng)前節(jié)點(diǎn)未巫。
? ??插入900
????滿(mǎn)足情況④中的2）
????第一步將父節(jié)點(diǎn)800與祖父節(jié)點(diǎn)711的顏色進(jìn)行交換。
????第二步設(shè)置祖父節(jié)點(diǎn)711作為新的當(dāng)前節(jié)點(diǎn)启昧，以當(dāng)前節(jié)點(diǎn)為支點(diǎn)左旋叙凡。調(diào)整得到下圖
? ??插入50，270密末，保持不變
? ??插入20
????滿(mǎn)足情況③，進(jìn)行調(diào)整如下：
? ??插入30
????滿(mǎn)足情況④中的3）严里，第一步對(duì)父親節(jié)點(diǎn)20進(jìn)行一次左旋新啼，得到下圖
????滿(mǎn)足情況④中的1），第一步將父親節(jié)點(diǎn)30和爺爺節(jié)點(diǎn)50顏色互換（父節(jié)點(diǎn)變?yōu)楹谏材耄瑺敔敼?jié)點(diǎn)變?yōu)榧t色）燥撞，然后對(duì)爺爺節(jié)點(diǎn)50進(jìn)行一次右旋。
????插入過(guò)程完畢迷帜。
七物舒、紅黑樹(shù)的刪除
????相較于插入操作，紅黑樹(shù)的刪除操作則要更為復(fù)雜一些戏锹。刪除操作首先要確定待刪除節(jié)點(diǎn)有幾個(gè)孩子冠胯。
? ??刪除一個(gè)節(jié)點(diǎn)有以下四種情況：
????① 刪除的節(jié)點(diǎn)沒(méi)有孩子
????② 刪除的節(jié)點(diǎn)只有左子樹(shù)
????③ 刪除的節(jié)點(diǎn)只有右子樹(shù)
????④ 刪除的節(jié)點(diǎn)擁有左子樹(shù)和右子樹(shù)
????其實(shí)只有上面前三種情況，對(duì)于第④種情況景用，可以找到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)涵叮，用這個(gè)節(jié)點(diǎn)的值替代待刪除節(jié)點(diǎn)惭蹂，接著情況轉(zhuǎn)變?yōu)閯h除這個(gè)直接后繼節(jié)點(diǎn)，情況也變?yōu)榍叭N之一割粮。
????對(duì)于情況②和③盾碗，也就是待刪除的節(jié)點(diǎn)只有左子樹(shù)或這有右子樹(shù)的情況，有很多組合在紅黑樹(shù)中是不可能出現(xiàn)的舀瓢，因?yàn)樗麄冞`背了紅黑樹(shù)的性質(zhì)廷雅。
????情況②和③中不存在的情況有（其中D表示要?jiǎng)h除的節(jié)點(diǎn)，DL和DR分別表示左子和右子）：
????上述情況都違背了紅黑樹(shù)的性質(zhì)5【對(duì)于每個(gè)節(jié)點(diǎn)京髓，從該節(jié)點(diǎn)到其子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑色節(jié)點(diǎn)】航缀。
????上述兩種情況明顯違背了性質(zhì)4【如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的】堰怨。
????我們把刪除的節(jié)點(diǎn)分為兩大類(lèi)：刪除紅色節(jié)點(diǎn)和黑色節(jié)點(diǎn)芥玉。
? ??1、刪除紅色節(jié)點(diǎn)
? ??1.1 刪除紅色的葉子節(jié)點(diǎn)（D表示待刪除的節(jié)點(diǎn)备图，P表示其父親節(jié)點(diǎn)）
????上面這兩種情況其實(shí)處理方式都一樣灿巧，直接刪除D就好！
? ??1.2 刪除的紅色節(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)
????上述兩種情況明顯違背了紅黑樹(shù)的性質(zhì)4【如果一個(gè)節(jié)點(diǎn)是紅色的揽涮，則它的子節(jié)點(diǎn)必須是黑色的】抠藕，根本不存在這種情況。
? ??1.3 刪除的紅色節(jié)點(diǎn)有左右子樹(shù)（或左右孩子）
????假設(shè)刪除節(jié)點(diǎn)為X蒋困，先找到該節(jié)點(diǎn)的左孩子節(jié)點(diǎn)DL盾似，若DL為葉子節(jié)點(diǎn)，則直接交換DL與X的值雪标，再刪除DL節(jié)點(diǎn)零院；否則從DL的后繼節(jié)點(diǎn)中找到最大值節(jié)點(diǎn)S【從右子樹(shù)查找】，交換S節(jié)點(diǎn)與要?jiǎng)h除節(jié)點(diǎn)X的數(shù)值汰聋，再刪除新的S節(jié)點(diǎn)【此時(shí)的S節(jié)點(diǎn)一定是葉子節(jié)點(diǎn)】门粪，如果該S節(jié)點(diǎn)為紅色，直接刪除烹困，否則進(jìn)行下一步的情況判斷玄妈。 ??
????2、刪除黑色節(jié)點(diǎn)
? ??2.1刪除的黑色節(jié)點(diǎn)有左右子樹(shù)
????假設(shè)刪除節(jié)點(diǎn)為X髓梅，找到該節(jié)點(diǎn)的左孩子節(jié)點(diǎn)DL拟蜻，若DL為葉子節(jié)點(diǎn)，則直接交換DL與X的值枯饿，再刪除DL節(jié)點(diǎn)酝锅；否則從該節(jié)點(diǎn)DL的后繼節(jié)點(diǎn)中找到最大值節(jié)點(diǎn)S【從右子樹(shù)查找】，交換S節(jié)點(diǎn)與要?jiǎng)h除節(jié)點(diǎn)X的數(shù)值奢方，再刪除新的S節(jié)點(diǎn)【此時(shí)的S節(jié)點(diǎn)一定是葉子節(jié)點(diǎn)】搔扁，如果該S節(jié)點(diǎn)為紅色爸舒，直接刪除，否則進(jìn)行下一步的情況判斷稿蹲。?
? ??2.2刪除的黑色節(jié)點(diǎn)僅有左子樹(shù)或者僅有右子樹(shù)
????排除上述的情況扭勉，只存在以下兩種情形：
? ??處理方法：用D的孩子（左或右）替換D，并將D孩子的顏色改成黑色即可（因?yàn)槁窂缴仙倭艘粋€(gè)黑節(jié)點(diǎn)苛聘，所已將紅節(jié)點(diǎn)變成黑節(jié)點(diǎn)以保持紅黑樹(shù)的性質(zhì)）涂炎。
? ??2.3刪除黑色的葉子節(jié)點(diǎn)
????對(duì)于這種情況，相對(duì)復(fù)雜设哗，我們可以分為5種情況來(lái)討論：
? ??2.3.1：兄弟節(jié)點(diǎn)為黑色唱捣，且遠(yuǎn)侄子節(jié)點(diǎn)為紅色。
? ??①?D為左孩子對(duì)的情況网梢，這時(shí)D的遠(yuǎn)侄子節(jié)點(diǎn)為S的右孩子震缭。
????沒(méi)有上色的節(jié)點(diǎn)表示黑色紅色均可，注意如果SL為黑色战虏，則SL必為NULL節(jié)點(diǎn)蛀序。
????這個(gè)時(shí)候，如果我們刪除D活烙，這樣經(jīng)過(guò)D的子節(jié)點(diǎn)（NULL節(jié)點(diǎn)）的路徑的黑色節(jié)點(diǎn)個(gè)數(shù)就會(huì)減1，但是我們看到S的孩子中有紅色的節(jié)點(diǎn)遣鼓，如果我們能把這棵紅色的節(jié)點(diǎn)移動(dòng)到左側(cè)啸盏，并把它改成黑色，那么就滿(mǎn)足要求了骑祟，這也是為什么P的顏色無(wú)關(guān)回懦，因?yàn)檎{(diào)整過(guò)程只在P整棵子樹(shù)的內(nèi)部進(jìn)行。
????調(diào)整過(guò)程為次企，將P和S的顏色對(duì)調(diào)怯晕，然后對(duì)P樹(shù)進(jìn)行類(lèi)似AVL樹(shù)RR型的操作，最后把SR節(jié)點(diǎn)變成黑色缸棵，并刪除D即可舟茶。
? ??②?D為右孩子的情況，此時(shí)D的遠(yuǎn)侄子為S的左孩子堵第。
????同樣吧凉，將P和S的顏色對(duì)調(diào)，然后再對(duì)P樹(shù)進(jìn)行類(lèi)似AVL樹(shù)LL型的操作踏志，最后將SL變成黑色阀捅，并刪掉D即可。結(jié)果如下圖：
? ??2.3.2：父親節(jié)p為紅色针余，兄弟節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的兩個(gè)孩子（只能是NULL節(jié)點(diǎn)）都為黑色的情況饲鄙。
????如果刪除D凄诞，那經(jīng)過(guò)P到D的子節(jié)點(diǎn)NULL的路徑上黑色就少了一個(gè)，這個(gè)時(shí)候我們可以把P變成黑色忍级，這樣刪除D后經(jīng)過(guò)D子節(jié)點(diǎn)（NULL節(jié)點(diǎn)）路徑上的黑色節(jié)點(diǎn)就和原來(lái)一樣了帆谍。但是這樣會(huì)導(dǎo)致經(jīng)過(guò)S的子節(jié)點(diǎn)（NULL節(jié)點(diǎn)）的路徑上的黑色節(jié)點(diǎn)數(shù)增加一個(gè)，所以這個(gè)時(shí)候可以再將S節(jié)點(diǎn)變成紅色颤练，這樣路徑上的黑色節(jié)點(diǎn)數(shù)就和原來(lái)一樣啦既忆！
????所以做法是，將父親節(jié)點(diǎn)P改成黑色嗦玖，將兄弟節(jié)點(diǎn)S改成紅色患雇，然后刪除D即可。如下圖：
? ??2.3.3：父親節(jié)點(diǎn)p宇挫，兄弟節(jié)點(diǎn)s和兄弟節(jié)點(diǎn)的兩個(gè)孩子（只能為NULL節(jié)點(diǎn)）都為黑色的情況
????方法是將兄弟節(jié)點(diǎn)S的顏色改成紅色苛吱，這樣刪除D后P的左右兩支的黑節(jié)點(diǎn)數(shù)就相等了，但是經(jīng)過(guò)P的路徑上的黑色節(jié)點(diǎn)數(shù)會(huì)少1器瘪，這個(gè)時(shí)候翠储，我們?cè)僖訮為起始點(diǎn)，繼續(xù)根據(jù)情況進(jìn)行平衡操作（這句話的意思就是把P當(dāng)成D（只是不要再刪除P了）橡疼，再看是那種情況援所，再進(jìn)行對(duì)應(yīng)的調(diào)整，這樣一直向上欣除，直到新的起始點(diǎn)為根節(jié)點(diǎn)）住拭。結(jié)果如下圖：
? ??2.3.4：兄弟節(jié)點(diǎn)S為黑色，遠(yuǎn)侄子節(jié)點(diǎn)為黑色历帚，近侄子節(jié)點(diǎn)為紅色
? ??①?D為左孩子的情況滔岳，此時(shí)近侄子節(jié)點(diǎn)為S的左孩子
????做法是，將SL右旋挽牢，并將S和SL的顏色互換谱煤，這個(gè)時(shí)候就變成了情況2.3.1中的?①。
? ? 根據(jù)2.3.1中的?①再進(jìn)行節(jié)點(diǎn)的刪除禽拔。
?????②?D為右孩子的情況刘离，此時(shí)近侄子節(jié)點(diǎn)為S的右孩子
????做法是將S和SR顏色對(duì)調(diào)，然后對(duì)SR進(jìn)行左旋操作睹栖，這樣就變成了情況2.3.1中?的②??寥闪，結(jié)果如下圖：
? ? 根據(jù)2.3.1中的②?再進(jìn)行節(jié)點(diǎn)的刪除。
? ??2.3.5：待刪除節(jié)點(diǎn)D的兄弟節(jié)點(diǎn)S為紅色
? ??①?D是左節(jié)點(diǎn)的情況
????調(diào)整做法是將父親節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的顏色互換磨淌，也就是p變成紅色疲憋，S變成黑色，然后將P樹(shù)進(jìn)行AVL樹(shù)種的RR型操作梁只，結(jié)果如下圖：
????這個(gè)時(shí)候我們會(huì)發(fā)現(xiàn)缚柳，D的兄弟節(jié)點(diǎn)變成了黑色埃脏，這樣就成情況2.3.2。
? ??②?D是右節(jié)點(diǎn)的情況
????將P和S的顏色互換秋忙，也就是將P變成紅色彩掐，將S變成黑色，然后對(duì)P進(jìn)行類(lèi)似AVL樹(shù)的LL操作灰追。結(jié)果如下圖：
????此時(shí)D的兄弟節(jié)點(diǎn)變成了黑色堵幽，這樣就成了我們情況2.3.2。
? ??我們來(lái)看一個(gè)具體的刪除例子：
? ??刪除節(jié)點(diǎn)442
????節(jié)點(diǎn)442為左孩子弹澎。兄弟節(jié)點(diǎn)800為黑色朴下，且遠(yuǎn)侄子節(jié)點(diǎn)900為紅色评疗。滿(mǎn)足2.3.1中的情況①棍矛，調(diào)整過(guò)程為蕊爵，將父節(jié)點(diǎn)515和兄弟節(jié)點(diǎn)800的顏色對(duì)調(diào)冶忱，然后對(duì)父節(jié)點(diǎn)515進(jìn)行RR型的操作，也就是左旋酬诀。最后把遠(yuǎn)侄子節(jié)點(diǎn)900變成黑色颓影，并刪除D即可枫虏。結(jié)果如下：
? ??刪除節(jié)點(diǎn)270
????節(jié)點(diǎn)270為右孩子报强。兄弟節(jié)點(diǎn)30為黑色灸姊，且遠(yuǎn)侄子節(jié)點(diǎn)20為紅色。滿(mǎn)足2.3.1中的情況②秉溉，D為右孩子的情況厨钻。同樣，將父節(jié)點(diǎn)260和兄弟節(jié)點(diǎn)30的顏色對(duì)調(diào)坚嗜，然后再對(duì)以父節(jié)點(diǎn)260為根的樹(shù)進(jìn)行LL型的操作，也就是右旋诗充。最后將遠(yuǎn)侄子節(jié)點(diǎn)20變成黑色苍蔬，并刪掉節(jié)點(diǎn)270即可。結(jié)果如下圖：
? ??刪除節(jié)點(diǎn)711
? ??滿(mǎn)足1.1蝴蜓，直接刪除該節(jié)點(diǎn)碟绑，得到下圖
? ??刪除節(jié)點(diǎn)260
? ??滿(mǎn)足2.2，用節(jié)點(diǎn)260的右孩子50替換該節(jié)點(diǎn)茎匠，并將節(jié)點(diǎn)50的顏色改成黑色即可格仲，得到下圖
? ??刪除節(jié)點(diǎn)20
? ??滿(mǎn)足2.3.2，將父親節(jié)點(diǎn)30改成黑色诵冒，將兄弟節(jié)點(diǎn)50改成紅色凯肋，然后刪除節(jié)點(diǎn)20即可，結(jié)果如下：
? ??刪除節(jié)點(diǎn)50
? ??滿(mǎn)足1.1汽馋，直接刪除侮东，結(jié)果如下圖：
? ??刪除節(jié)點(diǎn)800
? ??滿(mǎn)足1.3圈盔，找到800的后繼節(jié)點(diǎn)的最大值，圖中為515悄雅，交換800與515的位置驱敲，并將新的值為800的節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)。得到下圖：
????繼續(xù)刪除交換得到的值為800的節(jié)點(diǎn)宽闲。
? ??滿(mǎn)足2.3.2众眨，將父親節(jié)點(diǎn)515改成黑色，將兄弟節(jié)點(diǎn)900改成紅色容诬，然后刪除800娩梨，調(diào)整結(jié)果如下
? ??刪除節(jié)點(diǎn)275
? ??滿(mǎn)足2.1，找到275的后繼節(jié)點(diǎn)的最小值放案，圖中為30姚建，交換275與30的位置，并將新的值為275的節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)吱殉。得到下圖：
????繼續(xù)刪除交換得到的值為275的節(jié)點(diǎn)
? ??滿(mǎn)足2.3.1中的情況①掸冤，調(diào)整得到下圖：
????其余情況大致如上，按照上述的方式去分析即可友雳。
八稿湿、源代碼
????本代碼為參考網(wǎng)上借鑒得來(lái)的代碼，截圖如下：
九押赊、總結(jié)
????紅黑樹(shù)是一種重要的二叉樹(shù)饺藤，應(yīng)用廣泛，但在很多數(shù)據(jù)結(jié)構(gòu)相關(guān)的書(shū)本中出現(xiàn)的次數(shù)并不多流礁。很多書(shū)中要么不說(shuō)涕俗，要么就一筆帶過(guò)，并不會(huì)進(jìn)行詳細(xì)的分析神帅，這可能是因?yàn)榧t黑樹(shù)比較復(fù)雜的緣故再姑。我在學(xué)習(xí)紅黑樹(shù)的時(shí)候也找了很多資料，但總體感覺(jué)講的都不太好找御，因此總結(jié)歸納了下元镀，希望有所幫助，當(dāng)然有錯(cuò)也請(qǐng)指正霎桅。
十栖疑、參考
1、紅黑樹(shù)原理分析（圖解） - 菜鳥(niǎo)28 - 博客園
2滔驶、紅黑樹(shù)之刪除節(jié)點(diǎn) - 青兒哥哥 - 博客園
3遇革、https://blog.csdn.net/qq_32924343/article/details/80893333
4、https://blog.csdn.net/qq_37169817/article/details/78880110
5、算法導(dǎo)論
【推薦：http://algoanim.ide.sk/index.php?page=showanim&id=63?該工具可以動(dòng)態(tài)演示紅黑樹(shù)轉(zhuǎn)換過(guò)程澳淑，可以暫停動(dòng)畫(huà)效果比原，一幀一幀的查看轉(zhuǎn)換過(guò)程，也可以放慢動(dòng)畫(huà)效果杠巡，這樣講思考前置量窘，通過(guò)動(dòng)畫(huà)結(jié)果來(lái)驗(yàn)證自己的想法】
