1、概念
红黑树也是一种自平衡的二叉搜索树，以前也叫做平衡二叉B树
红黑树必须满足以下5条性质：
1、节点是RED或者BLACK
2、根节点是BLACK
3、叶子节点（外部节点，空节点）都是BLACK
4、RED节点的子节点都是BLACK
RED节点的parent都是BLACK，从根节点到叶子节点的所有路径上不能有两个连续的RED节点。
5、从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点
2、添加
已知
B树中，新元素必定添加到叶子节点
4阶B树所有节点的元素个数x都符合1x
3
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进行单旋操作
2.3、LR\RL修复
判定条件 uncle不是RED
1、自己染成BLACK，grand染成RED
2、进行双旋操作
2.4、上溢-LL
判定条件：uncle是RED
1、parent、uncle染成BLACK
2、grand向上合并
染成RED，当做是新节点进行处理
grand向上合并时，可能继续发生上溢，若上溢持续到根节点，只需将根节点染成BLACK
2.5、上溢-RR
判定条件：uncle是RED
1、parent、uncle染成BLACK
2、grand向上合并
染成RED，当做是新节点进行处理
以此类推，下面同样处理
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
3.2、删除的是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
