红黑树也是一种自平衡的二叉搜索树
红黑树必须满足一下5条性质
节点是RED或者BLACK
根节点是BLACK
叶子节点（外部节点，空节点）都是BLACK
RED节点的子节点都是BLACK
RED节点的parent都是BLACK
从根节点到叶子节点的所有路径上不能有2个连续的RED节点
从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点
以下即为一颗红黑树：
如上图所示：
? 上面的是红黑树，下面是与之等价的2-3-4树
// 染色
private Node<E> color(Node<E> node, boolean color) {
if (node == null) return node;
((RBNode<E>)node).color = color;
return node;
}
// 将该节点染为红色
private Node<E> red(Node<E> node) {
return color(node, RED);
}
// 将该节点染为黑色
private Node<E> black(Node<E> node) {
return color(node, BLACK);
}
// 返回该节点的颜色
private boolean colorOf(Node<E> node) {
return node == null ? BLACK : ((RBNode<E>)node).color;
}
// 该节点是否为黑色
private boolean isBlack(Node<E> node) {
return colorOf(node) == BLACK;
}
// 该节点是否为红色
private boolean isRed(Node<E> node) {
return colorOf(node) == RED;
}
public Node<E> sibling(){
if(isLeftChild()){
return parent.right;
}
if(isRightChild()){
return parent.left;
}
return null;
}
已知
建议新添加的节点默认为RED，这样能让红黑树的性质尽快满足
如果添加的是根节点，染成BLACK即可
有4中情况满足红黑树的性质4：parent为BLACK
同样也满足4阶B树的性质
因此不用做任何处理
如下图所示，如果我们要添加的是红色节点的话，又因为任何添加其实都是在叶子节点处添加，所以我们不需要对这种情况进行任何的处理，如图中的40,78,82,90都是这种情况
有 8 种情况不满足红黑树的性质 4 ：parent 为 RED（ Double Red ）
接下来我们对其进行一一解析
? 我们先来看这种情况，我们要在节点50的左边添加一个新的节点，或者我们要在72的右边添加一个新的节点。那么我们要做的事情很简单。我们知道新添加的这俩个节点，他们的父节点都是红色，这样的话，就会有连续的俩个节点都为红色了，那么就违背了红黑树的性质，所以我们要进行一定的调整。
判定条件：uncle（叔父节点）不是RED
? 其实调整的过程非常的简单：
? 也就是：
parent染成BLACK，grand染成RED
grand进行单选操作
LL：右旋转
RR：左旋转
旋转后如图所示：
? 我们再看这种情况，这种情况下，新添加的节点处于grand.right.left或者是grand.left.right，也就是我们下图所要添加的节点48或者节点74。对于这种情况，其实处理的方法也很简单，那就是我们要将新添加的节点染黑，然后将它的祖父节点染成红色，并且我们要进行旋转操作。对于下图添加节点48的情况，我们要将它的父节点进行右旋，然后将祖父节点进行左旋；对于下图中添加节点74的情况，我们只需要将它的父节点左旋，然后将它的祖父节点进行右旋就可以了。
判定条件：uncle不是RED
旋转之后的样子：
? 对于这种情况，我们添加元素的时候，肯定会发出上溢的情况，这个时候我们就要将节点进行向上合并的操作。如下图我们要添加新的节点10的时候，我们就需要进行一系列的操作。
? 首先，我们要将取出中间位置的节点向上合并，我们这里取节点25向上合并，做完这个操作之后，我们将25这个节点染成红色，作为是新添加的节点一样进行处理。然后因为25已经向上合并了，所以原先25节点的左子树和右子树分裂，所以我们要将新添加的节点的父节点，也就是下图的17节点染成黑色，然后我们将下图的33节点也染成黑色，因为现在的33节点也是一个叶子节点，我们知道红黑树里的叶子节点都是黑色的。
判定条件：uncle是RED
parent、uncle染成BLACK
grand向上合并
grand向上合并时，可能继续发生上溢
若上溢持续到根节点，只需将根节点染成BLACK
添加节点处理后如图所示：
? 对于这种情况，其实是和我们上面说的是相似的。对于我们要添加的新节点36来说，如果我们要添加新节点，那么必然会发生上溢的现象。所以我们同样的要选取中间位置的节点进行向上合并，这里我们取节点25进行向上合并，同样的，我们将节点25染成红色，当成新添加的节点进行处理。然后原来25节点的左右子树进行分裂。这个时候，我们应该将parent、uncle染成黑色。
判定条件：uncle是RED
? 在这里我就不一一进行赘述了，下面的情况大家可以自己进行理解
判定条件：uncle是RED
判定条件：uncle是RED
有3种情况
我们来说一说，为什么拥有2个RED子节点的BLACK节点的这种情况。如下图，假如我们要删除的是节点55，我们要处理的情况就是找到节点55的前驱结点或者后继节点进行替换节点55，然后将它的前驱结点或者后继节点删除。也就是说，如果我们要删除的节点是55的话，其实我们删除的就是它的前驱结点或者后继节点。
我们来简单的叙述一下这种操作，如下图，我们要删除节点46和节点76，因为要替代他们俩位置的都是红色的子节点50和72，所以进行删除的时候我们只需要将俩个节点删除，然后将节点50和72染成黑色就好了
操作之后的样子为：
原文：https://www.cnblogs.com/coderD/p/14612349.html