紅黑樹的性質(zhì)
1. 節(jié)點(diǎn)是 red 或者 black
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
5. red 節(jié)點(diǎn)的父節(jié)點(diǎn)是 black
6. 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑上不能有兩個(gè)連續(xù)的 red 節(jié)點(diǎn)
7. 從任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的 black 節(jié)點(diǎn)
1. 紅黑樹添加節(jié)點(diǎn)
紅黑樹添加節(jié)點(diǎn)，我們一般在葉子節(jié)點(diǎn)添加紅色，因?yàn)樘砑蛹t色節(jié)點(diǎn)能更快的符合上面幾條性質(zhì)，比如，如果添加一個(gè)黑色節(jié)點(diǎn)，很容易就打破規(guī)則7，本來紅黑樹從任意節(jié)點(diǎn)到子節(jié)點(diǎn)的路徑上都包含相同的 black 節(jié)點(diǎn)，但是如果這時(shí)候我們添加black 節(jié)點(diǎn)，那么這條規(guī)則就打破了，所以我們一般添加紅色節(jié)點(diǎn)
所以如果葉子節(jié)點(diǎn)為黑色節(jié)點(diǎn)，我們添加紅色節(jié)點(diǎn)沒有問題，但是葉子節(jié)點(diǎn)是紅色節(jié)點(diǎn)，那么久不滿足性質(zhì)6了，就需要做調(diào)整
黑
紅
紅（后添加的）
上面的情況就是 LL
黑
紅
紅（后添加）
這種情況就是RR
所有就需要染色，就需要將，父節(jié)點(diǎn)染成黑色，祖父節(jié)點(diǎn)染成紅色，然后進(jìn)行旋轉(zhuǎn)，進(jìn)行左旋和右旋
如果添加節(jié)點(diǎn)出現(xiàn)上溢的情況，那么將這個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和叔父節(jié)點(diǎn)染成黑色，然后把原來的父節(jié)點(diǎn)染成red，然后當(dāng)做新添加的節(jié)點(diǎn)來處理,遞歸向上，如果到了根節(jié)點(diǎn)還是上溢，只需要將根節(jié)點(diǎn)染成 black
2. 刪除節(jié)點(diǎn)
1.如果刪除的為 red 節(jié)點(diǎn)，那么直接刪除
如果刪除 black 節(jié)點(diǎn)：
2.如果這個(gè)black 有兩個(gè)red 節(jié)點(diǎn)，那么不用理會(huì)，因?yàn)閯h除這個(gè)black 節(jié)點(diǎn)之后，會(huì)有相應(yīng)的red節(jié)點(diǎn)來頂替
擁有一個(gè) red 節(jié)點(diǎn)的black 節(jié)點(diǎn)，和葉子black 節(jié)點(diǎn)，如下圖
3.刪除擁有一個(gè) red 節(jié)點(diǎn)的 black 節(jié)點(diǎn)：
判定條件：用以替代的子節(jié)點(diǎn)為 red
刪除這個(gè) black 節(jié)點(diǎn)之后，將替代的子節(jié)點(diǎn)染成黑色即可
- 刪除 black 葉子節(jié)點(diǎn)，兄弟節(jié)點(diǎn)為 black
如果兄弟節(jié)點(diǎn)至少有一個(gè) red 節(jié)點(diǎn)，那么就管兄弟借一個(gè)，此時(shí)可能會(huì)導(dǎo)致 B 樹下溢，
1. 進(jìn)行旋轉(zhuǎn)操作
2. 旋轉(zhuǎn)之后的中心節(jié)點(diǎn)，繼承原來 parent 的顏色
3. 旋轉(zhuǎn)之后的左右兩個(gè)節(jié)點(diǎn)都染為黑色
- 刪除葉子節(jié)點(diǎn)，兄弟節(jié)點(diǎn)為 black
如果兄弟節(jié)點(diǎn)沒有一個(gè) red 節(jié)點(diǎn)，那么就將 parent染成黑色，兄弟節(jié)點(diǎn)染成紅色
如果 parent 為黑色，那么會(huì)導(dǎo)致下溢，只需要把parent當(dāng)做被刪除的節(jié)點(diǎn)就可以
- 刪除 black 葉子節(jié)點(diǎn)，兄弟節(jié)點(diǎn)為紅色
1. 兄弟節(jié)點(diǎn)染成黑色，parent 染成紅色，然后進(jìn)行旋轉(zhuǎn)
2. 這時(shí)候又回到了5的情況，兄弟節(jié)點(diǎn)為 black
