1、概念

紅黑樹也是一種自平衡的二叉搜索樹摘盆，以前也叫做平衡二叉B樹
紅黑樹必須滿足以下5條性質(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
RED節(jié)點(diǎn)的parent都是BLACK肋殴，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑上不能有兩個(gè)連續(xù)的RED節(jié)點(diǎn)囤锉。
5、從任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的BLACK節(jié)點(diǎn)

2护锤、添加

已知
B樹中官地，新元素必定添加到葉子節(jié)點(diǎn)
4階B樹所有節(jié)點(diǎn)的元素個(gè)數(shù)x都符合1x3

2.1、添加所有情況

有4種情況滿足紅黑樹的性質(zhì)4：parent為BLACK
同樣也滿足4階B樹的性質(zhì)烙懦，因此不用做任何額外處理

無需調(diào)整

有8種情況不滿足紅黑樹的性質(zhì)4：parent為RED（DOUBLE RED）
其中前4種屬于B樹節(jié)點(diǎn)上溢的情況

需要調(diào)整

2.2驱入、LL\RR修復(fù)

判定條件 uncle不是RED
1、parent染成BLACK氯析，grand染成RED
2突照、grand進(jìn)行單旋操作

LL\RR

2.3、LR\RL修復(fù)

判定條件 uncle不是RED
1讯壶、自己染成BLACK鼠渺，grand染成RED
2、進(jìn)行雙旋操作

LR\RL

2.4你辣、上溢-LL

判定條件：uncle是RED
1巡通、parent尘执、uncle染成BLACK
2、grand向上合并
染成RED宴凉，當(dāng)做是新節(jié)點(diǎn)進(jìn)行處理
grand向上合并時(shí)誊锭，可能繼續(xù)發(fā)生上溢，若上溢持續(xù)到根節(jié)點(diǎn)弥锄，只需將根節(jié)點(diǎn)染成BLACK

上溢-LL

2.5炉旷、上溢-RR

判定條件：uncle是RED
1、parent叉讥、uncle染成BLACK
2窘行、grand向上合并
染成RED，當(dāng)做是新節(jié)點(diǎn)進(jìn)行處理

上溢-RR

以此類推图仓，下面同樣處理

2.6罐盔、上溢-LR

2.7、上溢-RL

關(guān)鍵代碼

protected void afterAdd(Node < E > node)
 {
     Node < E > parent = node.parent;
     // 添加的是根基節(jié)點(diǎn)
     if(parent == null)
     {
         black(node);
         return;
     }
     // 如果父節(jié)點(diǎn)是黑色救崔，直接返回
     if(isBlack(parent)) return;
     // uncle節(jié)點(diǎn)
     Node < E > uncle = parent.sibling();
     // 祖父節(jié)點(diǎn)
     Node < E > grand = parent.parent;
     if(isRed(uncle))
     {
         black(parent);
         black(uncle);
         // 祖父節(jié)點(diǎn)當(dāng)成是新添加的節(jié)點(diǎn)
         red(grand);
         afterAdd(grand);
         return;
     }
     // 叔父節(jié)點(diǎn)不是紅色
     if(parent.isLeftChild())
     { // L
         if(node.isLeftChild())
         { // LL
             black(parent);
             red(grand);
             rotateRight(grand);
         }
         else
         { // LR
             black(node);
             red(grand);
             rotateLeft(parent);
             rotateRight(grand);
         }
     }
     else
     {
         if(node.isLeftChild())
         { // RL
             black(node);
             red(grand);
             rotateLeft(grand);
             rotateRight(parent);
         }
         else
         { // RR
             black(parent);
             red(grand);
             rotateLeft(grand);
         }
     }
 }

3惶看、刪除

B樹中，最后真正被刪除的元素都在葉子節(jié)點(diǎn)中

3.1六孵、刪除的是RED節(jié)點(diǎn)

直接刪除纬黎，不用做調(diào)整，如下刪除劫窒，17,33,50,72

刪除RED節(jié)點(diǎn)

3.2本今、刪除的是BLACK節(jié)點(diǎn)

刪除BLACK節(jié)點(diǎn)

分3種情況
1、擁有2個(gè)RED子節(jié)點(diǎn)的BLACK節(jié)點(diǎn)
不可能被直接刪除主巍，因?yàn)闀?huì)找它的子節(jié)點(diǎn)替代刪除
因此不需要考慮這種情況
2冠息、擁有1個(gè)RED子節(jié)點(diǎn)的BLACK節(jié)點(diǎn)
條件：用以替代的子節(jié)點(diǎn)是RED
將替代的子節(jié)點(diǎn)染成BLACK即可保持紅黑樹的性質(zhì)
3、BLACK葉子節(jié)點(diǎn)-sibling為BLACK
BLACK葉子節(jié)點(diǎn)被刪除后孕索，會(huì)導(dǎo)致B樹節(jié)點(diǎn)下溢（比如下圖刪除88）
如果sibling至少有1個(gè)RED子節(jié)點(diǎn)
1）逛艰、進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)后中心節(jié)點(diǎn)繼承parent的顏色
2）搞旭、旋轉(zhuǎn)后左右節(jié)點(diǎn)染成BLACK

刪除88