要學(xué)習(xí)紅黑二叉樹仰猖，就得先了解二叉樹是什么，二叉樹是有限個(gè)元素得集合,這些元素集合構(gòu)成樹神得，二叉樹允許集合元素個(gè)數(shù)為0厘惦，此時(shí)他就是一個(gè)空樹，對(duì)于元素個(gè)數(shù)大于0的二叉樹哩簿，它會(huì)有一個(gè)根節(jié)點(diǎn)宵蕉，剩下下的元素被組成 2個(gè)二叉樹酝静，分別稱為左子樹和右子樹。二叉樹它滿足以下兩個(gè)條件：

1.每個(gè)結(jié)點(diǎn)他最多有兩個(gè)子結(jié)點(diǎn)

?2羡玛、左子節(jié)點(diǎn)一定是小于或等于其父節(jié)點(diǎn)别智，右子結(jié)點(diǎn)一定是大于或等于其父結(jié)點(diǎn)的

對(duì)于一系列元素來說，構(gòu)成一個(gè)二叉樹稼稿，它的形式是多樣的 薄榛，只要滿足上面條件即可，那么它可能構(gòu)成一個(gè)完整的二叉樹让歼，即各個(gè)結(jié)點(diǎn)和其子節(jié)點(diǎn)都存在敞恋，也或者它會(huì)完全是一個(gè)線性的，即根節(jié)點(diǎn)是最小值谋右，其左子樹為空且樹中不存在左子節(jié)點(diǎn) 耳舅。前者是最優(yōu)的方案，獲取元素平均搜索次數(shù)也是最少的倚评，后者和鏈表是一樣的，平均搜索次數(shù)是最多的馏予，如果是最后一個(gè)值天梧，則需要將整個(gè)樹的節(jié)點(diǎn)都過一遍，無疑這種方式是最耗時(shí)的霞丧。

為了保證元素在形成樹時(shí)不會(huì)出現(xiàn)后者的這種情況呢岗，在原先二叉樹的基礎(chǔ)上增加了一些條件限制，來對(duì)元素的插入或刪除時(shí)保持樹的飽和蛹尝。紅黑二叉樹是其中一種后豫，紅黑二叉樹中對(duì)每個(gè)結(jié)點(diǎn)元素新增了顏色的屬性，非黑即紅突那。紅黑二叉樹不僅要滿足二叉樹的定義挫酿，以下幾個(gè)條件也需要其滿足：

（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)必須是黑色的猜丹，也就是說不可能出現(xiàn)兩個(gè)連續(xù)的紅色節(jié)點(diǎn)芝加，不過兩個(gè)連續(xù)的黑色節(jié)點(diǎn)是可能出現(xiàn)的

（5）從任意一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的葉子節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

在構(gòu)建一個(gè)紅黑樹時(shí)射窒，不管是新插入元素還是刪除元素都有可能破壞4藏杖、5限制條件将塑，所以在我們新增或刪除元素節(jié)點(diǎn)時(shí)，我們需要操作樹中的結(jié)點(diǎn)制市，讓其結(jié)點(diǎn)顏色屬性滿足4抬旺、5限制條件。

新插入的元素結(jié)點(diǎn)一定是在紅黑樹的最低端的祥楣，且插入的元素初始顏色屬性為紅色(為紅色在有的情況下不需要調(diào)整原樹的顏色屬性)开财；

了解一下左旋和有旋的概念，后面會(huì)用到

左旋

右旋

截的別人的圖片误褪，感覺很直觀责鳍；

在我們插入一個(gè)新的元素結(jié)點(diǎn)時(shí)，我們會(huì)遍歷樹兽间，找到新增結(jié)點(diǎn)的插入位置(和二叉樹的插入是相同的)历葛，插入元素后默認(rèn)顏色為紅色，我們對(duì)樹做紅黑樹的限制校驗(yàn)嘀略，如果不滿足恤溶，我們就需要調(diào)整樹的結(jié)點(diǎn)顏色或通過上面說的左旋和右旋來調(diào)整結(jié)點(diǎn)位置來保證紅黑樹限制成立，主要有下面的情況

1帜羊、新增元素結(jié)點(diǎn)是根結(jié)點(diǎn)咒程，設(shè)置該結(jié)點(diǎn)元素為黑色，滿足限制條件(2);

2讼育、父結(jié)點(diǎn)為黑色帐姻，插入結(jié)點(diǎn)后不做任何調(diào)整（插入結(jié)點(diǎn)為紅色，滿足條件4 奶段，原先經(jīng)過父結(jié)點(diǎn)的最短簡(jiǎn)單路徑的黑色結(jié)點(diǎn)樹沒有減少或增加饥瓷，滿足條件5，所以不需修改）

3痹籍、父結(jié)點(diǎn)是紅色呢铆，此時(shí)父節(jié)點(diǎn)的兄弟結(jié)點(diǎn)(也叫叔叔結(jié)點(diǎn))也是紅色，此時(shí)爺爺結(jié)點(diǎn)一定是黑色的(條件4)蹲缠，這種情況由于新增的結(jié)點(diǎn)為紅色刺洒，不滿足條件4，此時(shí)需要做調(diào)整吼砂，將父結(jié)點(diǎn)和叔叔結(jié)點(diǎn)同時(shí)變?yōu)楹谏婧剑藭r(shí)經(jīng)過父結(jié)點(diǎn)和叔叔結(jié)點(diǎn)的簡(jiǎn)單路徑多了一個(gè)黑色結(jié)點(diǎn)，不滿足條件5渔肩，經(jīng)過父結(jié)點(diǎn)和叔叔結(jié)點(diǎn)的簡(jiǎn)單路徑肯定經(jīng)過爺爺結(jié)點(diǎn)因俐，且經(jīng)過爺爺結(jié)點(diǎn)的也只有父結(jié)點(diǎn)和叔叔結(jié)點(diǎn)，所以將爺爺結(jié)點(diǎn)變成紅色，這樣所有簡(jiǎn)單路徑上的黑色結(jié)點(diǎn)個(gè)數(shù)又一致了抹剩；此時(shí)其實(shí)情況又回到了新增結(jié)點(diǎn)的最初情況撑帖，只不過現(xiàn)在需要判斷紅黑樹限制的結(jié)點(diǎn)變成了爺爺結(jié)點(diǎn)，將爺爺結(jié)點(diǎn)(此時(shí)是紅色)看做新增結(jié)點(diǎn)遞歸處理

4澳眷、父結(jié)點(diǎn)是紅色胡嘿，此時(shí)叔叔結(jié)點(diǎn)是黑色，此時(shí)爺爺結(jié)點(diǎn)一定也是黑色的(條件4) 钳踊，此時(shí)情況稍微多點(diǎn)衷敌，需要用到左旋和右旋的操作；

情況1拓瞪、新增紅色結(jié)點(diǎn)是父結(jié)點(diǎn)的左孩子缴罗，且父結(jié)點(diǎn)也是爺爺?shù)淖蠛⒆樱藭r(shí)祭埂，不滿足條件4面氓，新增結(jié)點(diǎn)和父結(jié)點(diǎn)都為紅色，將父結(jié)點(diǎn)修改為黑色蛆橡，條件4滿足舌界，經(jīng)過父結(jié)點(diǎn)的簡(jiǎn)單路徑增加了一個(gè)黑色結(jié)點(diǎn)，不滿足條件5泰演；對(duì)爺爺結(jié)點(diǎn)做右旋處理禀横，父結(jié)點(diǎn)移至爺爺結(jié)點(diǎn)變成爺爺結(jié)點(diǎn)，爺爺結(jié)點(diǎn)移至叔叔結(jié)點(diǎn)變成叔叔結(jié)點(diǎn)粥血，新增結(jié)點(diǎn)移至父結(jié)點(diǎn)變成父結(jié)點(diǎn)(在樹結(jié)構(gòu)中的位置發(fā)生變化，我們對(duì)其的命名也發(fā)生變化酿箭，防止后續(xù)描述發(fā)生歧義)复亏。此時(shí)經(jīng)過爺爺結(jié)點(diǎn)的左子樹簡(jiǎn)單路徑黑色結(jié)點(diǎn)個(gè)數(shù)減少一個(gè)，右子樹卻新增了一個(gè)缭嫡，將叔叔結(jié)點(diǎn)（原爺爺結(jié)點(diǎn)元素）變紅色缔御，此時(shí)叔叔結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色的，兩個(gè)子結(jié)點(diǎn)也是黑色的妇蛀，將其變成紅色耕突，不違反條件4，又能平衡簡(jiǎn)單路徑的黑色結(jié)點(diǎn)樹评架，滿足條件5 眷茁。

情況2、新增紅色結(jié)點(diǎn)是父結(jié)點(diǎn)的右孩子纵诞，且父結(jié)點(diǎn)是爺爺結(jié)點(diǎn)的左孩子上祈，此時(shí)，不滿足條件4，新增結(jié)點(diǎn)和父結(jié)點(diǎn)都為紅色登刺。將父結(jié)點(diǎn)做左旋處理籽腕，就變成了情況1，繼續(xù)按照情況1的處理方式去調(diào)整纸俭。

情況3皇耗、新增紅色結(jié)點(diǎn)是父結(jié)點(diǎn)的右孩子，且父結(jié)點(diǎn)也是爺爺結(jié)點(diǎn)的右孩子揍很，此時(shí)郎楼，不滿足條件4，新增結(jié)點(diǎn)和父結(jié)點(diǎn)都為紅色女轿，將父結(jié)點(diǎn)修改為黑色箭启，條件4滿足，經(jīng)過父結(jié)點(diǎn)的簡(jiǎn)單路徑增加一個(gè)黑色結(jié)點(diǎn)蛉迹，不滿足條件5傅寡；對(duì)爺爺結(jié)點(diǎn)做左旋處理，父結(jié)點(diǎn)移至爺爺結(jié)點(diǎn)變成爺爺結(jié)點(diǎn)北救，爺爺結(jié)點(diǎn)移至叔叔結(jié)點(diǎn)變成叔叔結(jié)點(diǎn)荐操，新增結(jié)點(diǎn)移至父結(jié)點(diǎn)變成父結(jié)點(diǎn)(在樹結(jié)構(gòu)中的位置發(fā)生變化，我們對(duì)其的命名也發(fā)生變化珍策，防止后續(xù)描述發(fā)生歧義)托启。此時(shí)經(jīng)過爺爺結(jié)點(diǎn)的右子樹簡(jiǎn)單路徑黑色結(jié)點(diǎn)個(gè)數(shù)減少一個(gè)，右子樹卻新增了一個(gè)攘宙，將叔叔結(jié)點(diǎn)（原爺爺結(jié)點(diǎn)元素）變紅色屯耸，此時(shí)叔叔結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色的，兩個(gè)子結(jié)點(diǎn)也是黑色的蹭劈，將其變成紅色疗绣，不違反條件4，又能平衡簡(jiǎn)單路徑的黑色結(jié)點(diǎn)樹铺韧，滿足條件5 多矮。

情況4、新增紅色結(jié)點(diǎn)是父結(jié)點(diǎn)的左孩子哈打，且父結(jié)點(diǎn)是爺爺結(jié)點(diǎn)的右孩子塔逃，此時(shí)，不滿足條件4料仗，新增結(jié)點(diǎn)和父結(jié)點(diǎn)都為紅色湾盗。將父結(jié)點(diǎn)做右旋處理，就變成了情況3立轧，繼續(xù)按照情況3的處理方式去調(diào)整淹仑；

以上是紅黑樹新增結(jié)點(diǎn)的處理丙挽。

下面來理一理刪除：

什么叫后繼結(jié)點(diǎn) ：后繼節(jié)點(diǎn)一共有兩種情況，一種情況是當(dāng)前節(jié)點(diǎn)有右子樹匀借，那么當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)一定在它的右子樹上颜阐，在右子樹的最左邊 ，即為右子樹的最小值吓肋；第二種情況是凳怨，當(dāng)前結(jié)點(diǎn)沒有右子樹，那么就依次往上找是鬼，找到一種情況是當(dāng)前節(jié)點(diǎn)是它的父親節(jié)點(diǎn)的左孩子的時(shí)候肤舞，那么這個(gè)父親節(jié)點(diǎn)就是我原始節(jié)點(diǎn)的后繼節(jié)點(diǎn)

紅黑樹的刪除會(huì)有以下情況?

1、刪除的結(jié)點(diǎn)無子結(jié)點(diǎn)

2均蜜、刪除的結(jié)點(diǎn)只有左子樹或右子樹

3李剖、刪除的結(jié)點(diǎn)左右子樹都存在

針對(duì)第3種情況，如果左右子樹都存在的話囤耳，我們會(huì)尋找刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)篙顺，然后將后繼結(jié)點(diǎn)的值賦給刪除結(jié)點(diǎn)，再將后繼結(jié)點(diǎn)刪除充择，這種情況下的后繼結(jié)點(diǎn)即為刪除結(jié)點(diǎn)的右子樹的最左邊德玫；實(shí)際上就是變成了刪除后繼結(jié)點(diǎn)，又變成了第一二種情況椎麦，所以實(shí)際上就有這兩種情況了宰僧。

情況1 、 刪除的結(jié)點(diǎn)無子結(jié)點(diǎn)观挎；

? ? ? ? 1.1? 琴儿、刪除結(jié)點(diǎn)為紅色? ?，直接刪除即可嘁捷，因?yàn)槭羌t色結(jié)點(diǎn)造成，所以不影響紅黑樹的4和5條件；

? ? ? ? 1.2 普气、刪除結(jié)點(diǎn)為黑色且為左孩子，兄弟結(jié)點(diǎn)為紅色佃延，此時(shí)父結(jié)點(diǎn)為黑色现诀，根據(jù)紅黑樹的性質(zhì)，兄弟結(jié)點(diǎn)的左結(jié)點(diǎn)SL和右結(jié)點(diǎn)SR都為黑色且不能為空履肃，刪除后仔沿，父結(jié)點(diǎn)修改為紅色，兄弟結(jié)點(diǎn)修改為黑色尺棋，對(duì)父結(jié)點(diǎn)做左旋處理封锉，SL結(jié)點(diǎn)變成了原父結(jié)點(diǎn)的右孩子(黑色)，原父結(jié)點(diǎn)左孩子為空孩子，此條路徑會(huì)少一個(gè)黑色結(jié)點(diǎn)成福，不滿足條件5碾局，再對(duì)原父結(jié)點(diǎn)做左旋處理，SL結(jié)點(diǎn)替代原父結(jié)點(diǎn)位置即可奴艾。

? ? ? ? 1.3净当、刪除結(jié)點(diǎn)為黑色且為左孩子，兄弟結(jié)點(diǎn)為黑色

? ? ? ? ? ? ? ? 1蕴潦、兄弟結(jié)點(diǎn)左孩子SL為紅色時(shí) 像啼，刪除結(jié)點(diǎn)后，左子樹減少一個(gè)黑色潭苞，需要左結(jié)點(diǎn)新增個(gè)黑色結(jié)點(diǎn)忽冻，兄弟結(jié)點(diǎn)右旋，SL結(jié)點(diǎn)代替兄弟結(jié)點(diǎn)此疹，將SL修改為父結(jié)點(diǎn)的顏色僧诚，父節(jié)點(diǎn)修改為黑色，對(duì)父結(jié)點(diǎn)左旋秀菱，此時(shí)振诬，左子樹新增了一個(gè)黑色結(jié)點(diǎn)，右子樹的黑色結(jié)點(diǎn)樹不變衍菱。

? ? ? ? ? ? ? ? 2赶么、兄弟結(jié)點(diǎn)右孩子SR為紅色時(shí) ，刪除結(jié)點(diǎn)后脊串，左子樹減少一個(gè)黑色辫呻，需要左結(jié)點(diǎn)新增個(gè)黑色結(jié)點(diǎn)，將兄弟結(jié)點(diǎn)由黑色改為父結(jié)點(diǎn)的顏色琼锋，將SR由紅色改為黑色放闺，將父節(jié)點(diǎn)的顏色改為黑色，再將父節(jié)點(diǎn)左旋轉(zhuǎn)缕坎；此時(shí)怖侦，左子樹新增了一個(gè)黑色結(jié)點(diǎn)，右子樹的黑色結(jié)點(diǎn)樹不變谜叹。

? ? ? ? ? ? ? ? 3匾寝、兄弟結(jié)點(diǎn)的兩個(gè)孩子都為黑色，父結(jié)點(diǎn)為紅色荷腊，刪除結(jié)點(diǎn)后艳悔，左子樹減少一個(gè)黑色，需要左結(jié)點(diǎn)路徑新增個(gè)黑色結(jié)點(diǎn)女仰，? ? ?父結(jié)點(diǎn)修改為黑色猜年，再將兄弟結(jié)點(diǎn)修改為紅色即可抡锈。

? ????????????? 4、兄弟結(jié)點(diǎn)的兩個(gè)孩子都為黑色乔外，父結(jié)點(diǎn)為黑床三，刪除結(jié)點(diǎn)后，左子樹減少一個(gè)黑色袁稽，此種情況下無法通過修改結(jié)點(diǎn)顏色屬性和旋轉(zhuǎn)來達(dá)到左子樹增加黑色結(jié)點(diǎn)的目的勿璃，所以只能將兄弟結(jié)點(diǎn)改為紅色，將左右子數(shù)經(jīng)過黑色結(jié)點(diǎn)樹都減1推汽，在對(duì)父結(jié)點(diǎn)左迭代處理补疑，

? ? ? ? 1.4、刪除結(jié)點(diǎn)為黑色且為右孩子歹撒，兄弟結(jié)點(diǎn)為紅色莲组，此時(shí)父結(jié)點(diǎn)為黑色，根據(jù)紅黑樹的性質(zhì)暖夭，兄弟結(jié)點(diǎn)的左結(jié)點(diǎn)SL和右結(jié)點(diǎn)SR都為黑色且不能為空锹杈，刪除后，父結(jié)點(diǎn)修改為紅色迈着，兄弟結(jié)點(diǎn)修改為黑色竭望，對(duì)父結(jié)點(diǎn)做右旋處理，SR結(jié)點(diǎn)變成了原父結(jié)點(diǎn)的左孩子(黑色)裕菠，原父結(jié)點(diǎn)右孩子為空孩子咬清，此條路徑會(huì)少一個(gè)黑色結(jié)點(diǎn)，不滿足條件5奴潘，再對(duì)原父結(jié)點(diǎn)做右旋處理旧烧，SR結(jié)點(diǎn)替代原父結(jié)點(diǎn)位置即可。

? ? 1.5? 刪除結(jié)點(diǎn)為黑色且為右孩子画髓，兄弟結(jié)點(diǎn)為黑色

? ???????1掘剪、兄弟結(jié)點(diǎn)左孩子SR為紅色時(shí) ，刪除結(jié)點(diǎn)后奈虾，右子樹減少一個(gè)黑色夺谁，需右結(jié)點(diǎn)新增個(gè)黑色結(jié)點(diǎn)，兄弟結(jié)點(diǎn)左旋肉微，SR結(jié)點(diǎn)代替兄弟結(jié)點(diǎn)匾鸥，將SR修改為父結(jié)點(diǎn)的顏色，父節(jié)點(diǎn)修改為黑色浪册，對(duì)父結(jié)點(diǎn)右旋扫腺，此時(shí)岗照，右子樹新增了一個(gè)黑色結(jié)點(diǎn)村象，左子樹的黑色結(jié)點(diǎn)樹不變笆环。

? ? ? ? ? ? ? ? 2、兄弟結(jié)點(diǎn)左孩子SL為紅色時(shí) 厚者，刪除結(jié)點(diǎn)后躁劣，右子樹減少一個(gè)黑色，需要右結(jié)點(diǎn)新增個(gè)黑色結(jié)點(diǎn)库菲，將兄弟結(jié)點(diǎn)由黑色改為父結(jié)點(diǎn)的顏色账忘，將SL由紅色改為黑色，將父節(jié)點(diǎn)的顏色改為黑色熙宇，再將父結(jié)點(diǎn)節(jié)點(diǎn)右旋轉(zhuǎn)鳖擒；此時(shí)，左子樹新增了一個(gè)黑色結(jié)點(diǎn)烫止，右子樹的黑色結(jié)點(diǎn)樹不變蒋荚。

????????????3、兄弟結(jié)點(diǎn)的兩個(gè)孩子都為黑色馆蠕，父結(jié)點(diǎn)為紅色期升，刪除結(jié)點(diǎn)后，右子樹減少一個(gè)黑色互躬，需要左結(jié)點(diǎn)路徑新增個(gè)黑色結(jié)點(diǎn)播赁，? ? ?父結(jié)點(diǎn)修改為黑色，再將兄弟結(jié)點(diǎn)修改為紅色即可。

? ? ? ? ? ? ? 4、兄弟結(jié)點(diǎn)的兩個(gè)孩子都為黑色抚垄，父結(jié)點(diǎn)為黑甚负，刪除結(jié)點(diǎn)后，右子樹減少一個(gè)黑色输枯，此種情況下無法通過修改結(jié)點(diǎn)顏色屬性和旋轉(zhuǎn)來達(dá)到右子樹增加黑色結(jié)點(diǎn)的目的，所以只能將兄弟結(jié)點(diǎn)改為紅色，將左右子數(shù)經(jīng)過黑色結(jié)點(diǎn)樹都減1沼瘫，在對(duì)父結(jié)點(diǎn)做迭代處理；

1.4和1.5情況差不多咙俩，只是做左旋右旋的選擇不同

情況2耿戚、刪除的結(jié)點(diǎn)只有一個(gè)子結(jié)點(diǎn)；

? ? ? ? 2.1阿趁、刪除的結(jié)點(diǎn)為紅色膜蛔，用子結(jié)點(diǎn)替換掉該要?jiǎng)h除的結(jié)點(diǎn)，因?yàn)槭羌t色結(jié)點(diǎn)脖阵，所以不影響紅黑樹的4和5條件皂股；

? ? ? ? 2.2 、刪除的結(jié)點(diǎn)為黑色命黔，用子結(jié)點(diǎn)替換掉該要?jiǎng)h除的結(jié)點(diǎn)呜呐，如果子結(jié)點(diǎn)為紅色時(shí)就斤，修改子結(jié)點(diǎn)顏色為紅色；

? ? ? ? 2.3? 刪除的結(jié)點(diǎn)為黑色蘑辑，用子結(jié)點(diǎn)替換掉該要?jiǎng)h除的結(jié)點(diǎn)洋机，子結(jié)點(diǎn)為黑色，處理情況和情況1的1.2洋魂、1.3绷旗、1.4、1.5情況類似副砍。