1、概念

红黑树也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树
红黑树必须满足以下5条性质：
1、节点是RED或者BLACK
2、根节点是BLACK
3、叶子节点（外部节点，空节点）都是BLACK
4、RED节点的子节点都是BLACK
RED节点的parent都是BLACK，从根节点到叶子节点的所有路径上不能有两个连续的RED节点。
5、从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

2、添加

已知
B树中，新元素必定添加到叶子节点
4阶B树所有节点的元素个数x都符合1x3

2.1、添加所有情况

有4种情况满足红黑树的性质4：parent为BLACK
同样也满足4阶B树的性质，因此不用做任何额外处理

无需调整

有8种情况不满足红黑树的性质4：parent为RED（DOUBLE RED）
其中前4种属于B树节点上溢的情况

需要调整

2.2、LL\RR修复

判定条件 uncle不是RED
1、parent染成BLACK，grand染成RED
2、grand进行单旋操作

LL\RR

2.3、LR\RL修复

判定条件 uncle不是RED
1、自己染成BLACK，grand染成RED
2、进行双旋操作

LR\RL

2.4、上溢-LL

判定条件：uncle是RED
1、parent、uncle染成BLACK
2、grand向上合并
染成RED，当做是新节点进行处理
grand向上合并时，可能继续发生上溢，若上溢持续到根节点，只需将根节点染成BLACK

上溢-LL

2.5、上溢-RR

判定条件：uncle是RED
1、parent、uncle染成BLACK
2、grand向上合并
染成RED，当做是新节点进行处理

上溢-RR

以此类推，下面同样处理

2.6、上溢-LR

2.7、上溢-RL

关键代码

protected void afterAdd(Node < E > node)
 {
     Node < E > parent = node.parent;
     // 添加的是根基节点
     if(parent == null)
     {
         black(node);
         return;
     }
     // 如果父节点是黑色，直接返回
     if(isBlack(parent)) return;
     // uncle节点
     Node < E > uncle = parent.sibling();
     // 祖父节点
     Node < E > grand = parent.parent;
     if(isRed(uncle))
     {
         black(parent);
         black(uncle);
         // 祖父节点当成是新添加的节点
         red(grand);
         afterAdd(grand);
         return;
     }
     // 叔父节点不是红色
     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树中，最后真正被删除的元素都在叶子节点中

3.1、删除的是RED节点

直接删除，不用做调整，如下删除，17,33,50,72

删除RED节点

3.2、删除的是BLACK节点

删除BLACK节点

分3种情况
1、拥有2个RED子节点的BLACK节点
不可能被直接删除，因为会找它的子节点替代删除
因此不需要考虑这种情况
2、拥有1个RED子节点的BLACK节点
条件：用以替代的子节点是RED
将替代的子节点染成BLACK即可保持红黑树的性质
3、BLACK叶子节点-sibling为BLACK
BLACK叶子节点被删除后，会导致B树节点下溢（比如下图删除88）
如果sibling至少有1个RED子节点
1）、进行旋转，旋转后中心节点继承parent的颜色
2）、旋转后左右节点染成BLACK

删除88