紅黑樹(shù)（Red Black Tree)
紅黑樹(shù)也是一種自平衡的二叉搜索樹(shù)醒颖，紅黑樹(shù)必須滿足一下5條性質(zhì)：
1.節(jié)點(diǎn)是RED或者BLCAK
2.根節(jié)點(diǎn)是BLACK
3.葉子節(jié)點(diǎn)（外部節(jié)點(diǎn)音诈，空節(jié)點(diǎn)）都是BLACK
4.RED節(jié)點(diǎn)的子節(jié)點(diǎn)都是BLACK，RED節(jié)點(diǎn)的父節(jié)都是BLACK吼和，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑上不能有2個(gè)連續(xù)的RED節(jié)點(diǎn)
5.從任意一個(gè)節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的BLACK節(jié)點(diǎn)
請(qǐng)問(wèn)下面這棵是紅黑樹(shù)么？
答案是不是的，因?yàn)椴粷M足上面所說(shuō)的性質(zhì)5:從任意節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同的BLACK節(jié)點(diǎn)影兽，路徑55->53-null,這條路徑如果不包含null這個(gè)葉子節(jié)點(diǎn)的話，那么就只有兩個(gè)BLACK節(jié)點(diǎn)莱革，而其他的是有3個(gè)的BLACK節(jié)點(diǎn)
紅黑樹(shù)的等價(jià)變換
紅黑樹(shù)和4階B樹(shù)（2-3-4樹(shù)）具有等價(jià)性峻堰，BLACK節(jié)點(diǎn)與它的RED子節(jié)點(diǎn)融合在一起，形成一個(gè)B樹(shù)節(jié)點(diǎn)盅视，紅黑樹(shù)的BLACK節(jié)點(diǎn)個(gè)數(shù)與4階B樹(shù)的節(jié)點(diǎn)總個(gè)數(shù)相等
幾個(gè)相關(guān)的專(zhuān)業(yè)名字
parent：父節(jié)點(diǎn)
sibling：兄弟節(jié)點(diǎn)
uncle：叔父節(jié)點(diǎn)（parent的兄弟節(jié)點(diǎn)）
grand：祖父節(jié)點(diǎn)（parent的父節(jié)點(diǎn)）
紅黑樹(shù)的添加
從B樹(shù)中我們可以知道捐名，新元素必定是添加到葉子節(jié)點(diǎn)中，4階B樹(shù)的多有節(jié)點(diǎn)的元素個(gè)數(shù)都符合闹击，建議新添加的節(jié)點(diǎn)默認(rèn)為RED镶蹋，這樣能夠讓紅黑樹(shù)的性質(zhì)星空滿足（性質(zhì)1，2赏半，3贺归，5都滿足，就只有性質(zhì)4不一定滿足）断箫，另外如果添加的是根節(jié)點(diǎn)拂酣，直接染成BLACK即可
添加的所有情況（12種）
為什么是12種情況呢？因?yàn)樘砑釉囟际翘砑拥饺~子節(jié)點(diǎn)仲义，你可以想一下踱葛，葉子節(jié)點(diǎn)和父節(jié)點(diǎn)的分布情況有哪幾種丹莲，分別有紅黑紅，黑紅尸诽，紅黑甥材，黑如下圖：
可以從圖中看到最后兩層的分布形式，基于這種情況下性含，我們可以有12種添加元素的方式洲赵，如下圖所展示
前面已經(jīng)說(shuō)過(guò)了，如果添加的節(jié)點(diǎn)是紅色就滿足了4條性質(zhì)商蕴，接下來(lái)我們就是要滿足性質(zhì)4叠萍，從上述12種情形中，我們可以看到4種情形是滿足性質(zhì)4的(parent為BLACK)绪商，情形分別是情形5苛谷，情形10，情形11格郁，情形12腹殿；那么如果是這4種情況我們就是不用左任何額外處理的，如果是剩下的那8種(parent為RED)例书，我們就需要額外處理了
先處理情形7和情形8锣尉，這兩種情況分別符合RR和LL的情況，處理的步驟是判斷uncle 如果不是RED决采，就執(zhí)行下面步驟：1.parent染成BLACK自沧，grand染成RED；2.grand進(jìn)行單旋轉(zhuǎn)操作树瞭，如果是LL拇厢，就右旋轉(zhuǎn)，如果是RR晒喷，就左旋轉(zhuǎn)孝偎；
圖形展示如下：（情形7是RR，情形8是LL）
再處理情形6和情形9厨埋，分別符合RL和LR情況，處理方式：判定條件是uncle 不是RED捐顷，處理步驟1.自己染成BLACK荡陷，grand染成RED，2.進(jìn)行雙旋操作迅涮，LR：parent左旋轉(zhuǎn)废赞，grand右旋轉(zhuǎn)，RL：parent右旋轉(zhuǎn)叮姑，grand左旋轉(zhuǎn)
上圖：
目前為止唉地，現(xiàn)在只剩下4種情況据悔，是情形1，情形2耘沼，情形3极颓，情形4
情形1:修復(fù)性質(zhì)4-上溢(LL)
判定條件：uncle是RED，parent群嗤，uncle染成BLACK菠隆，grand向上合并，然后grand染成RED狂秘，當(dāng)作是新添加的節(jié)點(diǎn)進(jìn)行處理骇径，如果grand向上合并時(shí)候，繼續(xù)發(fā)生了上溢者春，那么繼續(xù)按照上溢的方式處理破衔，若上溢持續(xù)到根節(jié)點(diǎn)，只需將根節(jié)點(diǎn)染成BLACK钱烟；
此時(shí)38是parent晰筛，55是grand，80是uncle忠售，根據(jù)前面說(shuō)的传惠，parent,uncle染成black，grand向上合并稻扬，染成RED
剩余3種情形上溢RR卦方，上溢LR，上溢RL泰佳，都是和上溢LL一樣的處理方式盼砍，這里不在展示了，接下來(lái)描述一下刪除
紅黑樹(shù)的刪除
刪除也是分為好幾種情況的逝她，下面一一說(shuō)明：
刪除-RED節(jié)點(diǎn)
直接刪除浇坐，不用做任何調(diào)整，因?yàn)閯h除RED不會(huì)紅黑樹(shù)的性質(zhì)黔宛，前面已經(jīng)說(shuō)過(guò)近刘，刪除的節(jié)點(diǎn)都是在葉子節(jié)點(diǎn)；
刪除-BLACK節(jié)點(diǎn)
有3種情形臀晃，擁有2個(gè)RED子節(jié)點(diǎn)的BLACK節(jié)點(diǎn)觉渴，這種可以忽略，因?yàn)椴豢赡苤苯颖粍h除徽惋，因?yàn)榍懊嬲f(shuō)過(guò)刪除的都是子節(jié)點(diǎn)案淋，既然在有子節(jié)點(diǎn)，肯定是在子節(jié)點(diǎn)中刪除险绘，然后子節(jié)點(diǎn)是紅色的話踢京，那就不用處理誉碴，所以這里需要處理的只有擁有一個(gè)RED子節(jié)點(diǎn)的BLACK節(jié)點(diǎn)，和BLACK葉子節(jié)點(diǎn)瓣距，如下圖所示：
上面說(shuō)過(guò)刪除擁有兩個(gè)RED子節(jié)點(diǎn)的BLACK不需要理會(huì)黔帕，也就是說(shuō)上面的情形1，不用我們?nèi)ス芾碇祭裕@里我們看一下情形2的情況先蹬屹，因?yàn)榍樾?可以拆分出多種情況
情形2的第一種情況：sibling為BLAKCK并且有RED子節(jié)點(diǎn)
這種方式的處理可以理解成為：判定條件：用以替代的子節(jié)點(diǎn)是RED，將替代的子節(jié)點(diǎn)染成BLACK白华，即可以保持紅黑樹(shù)的性質(zhì)慨默，具體步驟可以立即成為，BLAKCK葉子節(jié)點(diǎn)被刪除后弧腥，會(huì)導(dǎo)致B樹(shù)節(jié)點(diǎn)下溢厦取，比如上面刪除的88，如果sibling至少有一個(gè)RED子節(jié)點(diǎn)管搪，首先根據(jù)相關(guān)旋轉(zhuǎn)條件進(jìn)行相應(yīng)旋轉(zhuǎn)操作虾攻，旋轉(zhuǎn)之后的中心節(jié)點(diǎn)繼承parent的顏色，旋轉(zhuǎn)之后的左右節(jié)點(diǎn)染為BLACK
情形2的第二種情況：sibling為BLAKCK沒(méi)有RED子節(jié)點(diǎn)
這種情況的判定條件是：sibling沒(méi)有一個(gè)RED子節(jié)點(diǎn)更鲁，處理步驟是sibling霎箍，染成RED，parent染成BLACK就可以了澡为，如果parent是BLACK漂坏，下溢之后導(dǎo)致parent也下溢，這個(gè)時(shí)候只需要把parent當(dāng)作被刪除的節(jié)點(diǎn)處理就可以了（上圖下面一種情況）
情形2的第三種情況：sibling為RED
如果sibling是RED媒至，sibling染成BLACK顶别，parent染成RED，進(jìn)行旋轉(zhuǎn)拒啰，于是情況就又回到sibling是BLACK的情況了驯绎，下面就按照前面的情況進(jìn)行處理就可以了
紅黑樹(shù)暫時(shí)先到這里吧，后續(xù)有學(xué)到新的我會(huì)再補(bǔ)充上來(lái)的
