知識(shí)前提：二叉查找樹(shù) 平衡二叉樹(shù)
寫(xiě)的很簡(jiǎn)單，有點(diǎn)亂剛學(xué)了整理一下，算自己的一點(diǎn)筆記。把握從下至上的思想。
性質(zhì)
紅黑樹(shù)是一種含有紅黑結(jié)點(diǎn)并能保持平衡的二叉查找樹(shù)。它必須滿足下面性質(zhì)：
性質(zhì)1：每個(gè)結(jié)點(diǎn)要么是黑色，要么是紅色。
性質(zhì)2：根結(jié)點(diǎn)是黑色。
性質(zhì)3：每個(gè)空結(jié)點(diǎn)是黑色。
性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。（黑結(jié)點(diǎn)的子結(jié)點(diǎn)則不一定）
性質(zhì)5：從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
對(duì)結(jié)點(diǎn)的操作
左旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，右子結(jié)點(diǎn)的左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的右子結(jié)點(diǎn)，左子結(jié)點(diǎn)保持不變。左旋中的“左”，意味著“被旋轉(zhuǎn)的節(jié)點(diǎn)將變成一個(gè)左節(jié)點(diǎn)”。
右旋：以某個(gè)結(jié)點(diǎn)作為支點(diǎn)(旋轉(zhuǎn)結(jié)點(diǎn))，其左子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)，左子結(jié)點(diǎn)的右子結(jié)點(diǎn)變?yōu)樾D(zhuǎn)結(jié)點(diǎn)的左子結(jié)點(diǎn)，右子結(jié)點(diǎn)保持不變。右旋中的“右”，意味著“被旋轉(zhuǎn)的節(jié)點(diǎn)將變成一個(gè)右節(jié)點(diǎn)”。
變色：結(jié)點(diǎn)的顏色由紅變黑或由黑變紅。
查找過(guò)程和二叉樹(shù)一致
插入
查找插入位置后，將插入的結(jié)點(diǎn)著色為紅色，（不會(huì)違背"特性(5)"！少違背一條特性，就意味著我們需要處理的情況越少。）
平衡：
使插入點(diǎn)后依舊滿足性質(zhì)，插入只可能改變性質(zhì)性質(zhì)2或4或5。
思路：將紅色的節(jié)點(diǎn)移到根節(jié)點(diǎn)；然后，將根節(jié)點(diǎn)設(shè)為黑色，基于性質(zhì)5.
所有的情況見(jiàn)圖：
祖宗根節(jié)點(diǎn)必黑，允許黑連黑，不允許紅連紅；新增紅色，爸叔通紅就變色，爸紅叔黑就旋轉(zhuǎn)，那黑往那旋
刪除
????????刪除其實(shí)是由簡(jiǎn)到繁，用替代結(jié)點(diǎn)代替刪除結(jié)點(diǎn)，然后刪除替代結(jié)點(diǎn)，后面的情況都會(huì)在過(guò)程中轉(zhuǎn)換成前面的情況。也可以說(shuō)是從樹(shù)葉到樹(shù)根的一步步替換。
0度點(diǎn)直接刪除；
1度點(diǎn)刪除后用子結(jié)點(diǎn)代替；
2度點(diǎn)刪除后，用左子樹(shù)最大結(jié)點(diǎn)（即最右）或右子樹(shù)最?。醋钭螅┙Y(jié)點(diǎn)代替；
????????替換后，因?yàn)閯h除結(jié)點(diǎn)之后，可能會(huì)違背紅黑樹(shù)的特性。所以需要通過(guò)旋轉(zhuǎn)和變色來(lái)修正該樹(shù)，使之重新成為一棵紅黑樹(shù)。
????????記刪除結(jié)點(diǎn)的替換之前和替換之后的顏色為X，易得X只有“黑紅”，“黑黑”兩種情況，看看性質(zhì)，只有刪除黑色結(jié)點(diǎn)才能影響性質(zhì)進(jìn)入平衡模式，刪除紅色結(jié)點(diǎn)會(huì)不會(huì)影響性質(zhì)，（只有刪除紅色的葉子節(jié)點(diǎn)這種情況）。一切從簡(jiǎn)，刪除黑色結(jié)點(diǎn)后首先自我解決（看替代結(jié)點(diǎn)能否維持平衡），接著找兄弟借紅變黑
????????具體情況如下（p為替代結(jié)點(diǎn)，可為空，此時(shí)為直接刪除葉子結(jié)點(diǎn)）沒(méi)說(shuō)的都是不可能出現(xiàn)的情況。
????????一切從簡(jiǎn)，刪除黑色結(jié)點(diǎn)后首先自我解決（看替代結(jié)點(diǎn)能否維持平衡），接著找兄弟借紅變黑，再不行向上反應(yīng)，直至根結(jié)點(diǎn)。判斷的時(shí)候，先看待刪除的節(jié)點(diǎn)的顏色，再看兄弟節(jié)點(diǎn)的顏色，再看侄子節(jié)點(diǎn)的顏色（侄子節(jié)點(diǎn)先看遠(yuǎn)侄子再看近侄子）遠(yuǎn)侄子紅，近侄子無(wú)所謂，遠(yuǎn)侄子黑近侄子紅，最后看父親節(jié)點(diǎn)的顏色（重要性排序）。
