1、红黑树定义
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。可以在 O(logn) 时间内做查找，插入和删除。红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。
满足如下条件：
- 每个节点要么是红色，要么是黑色。
- 根节点是黑色的
- 每个叶子节点是黑色的
- 红色节点不能连续（红色节点的孩子和父亲都不能是红色）。
- 从任意一个节点到叶子节点，经过的黑色节点是一样的。
1、红黑树与2-3树的等价性
参考下图，再红黑树中使用两个节点来模拟 2-3 树中的 3-节点，使用红色来表示 b 与 c 是并列的关系，如果来表示这条红色的边呢，其实就是让 b 这个节点变为红色，而 b 只有一个父节点，所以其与父节点的连线也就是红色，本质上就是把并列关系存储在子节点中。
- 黑色节点，对应 2-3树中的 2-节点。
- 红色节点和它的父节点一起表示 2-3 树中的 3-节点。
- 红黑树中所有的红色节点都是左倾斜的。
用红黑树来表示对等的 2-3 树：
再来回顾以下上面关于红黑树的 5 条定义：
- 每个节点要么是红色的，要么是黑色的：这是显然的。
- 根节点是黑色的：在 2-3 树中，根节点要么是 2-节点、要么是 3-节点，参考上图，转换成红黑树的的表示形式，根节点确实是黑色的。
- 每个叶子节点（最后的空节点）是黑色的：与其说这是性质，不如说是定义。红黑树中空节点是黑色的。
- 如果一个节点是红色的，那么它的两个孩子都是黑色的：红色节点对应 2-3 树中的 3-节点的左侧，而 3-节点的孩子要么是 2-节点，要么是 3-节点，它们确实都是黑色的。
- 从任意一个节点到叶子节点，经过的黑色节点是一样的：2-3 树是绝对平衡的，绝对平衡的树同层的节点到底叶子节点所经历的节点数必然是一致的，而2-3 树中的节点要么是 2-节点、要么是 3-节点，不管是 2-节点还是是 3-节点，用红黑树中的节点与转换后，都对应一个黑色节点，所以这条也是成立的。
红黑树是保持 黑平衡 的二叉树。严格定义来讲，不是平衡二叉树，最大高度为（最坏的情况） 2(logn)。
- 查找来讲：虽然 AVL 和红黑树都是 O(logn)级别的，但是 AVL 要快。
- 添加和删除来讲，红黑树要比 AVL 快。
2、红黑树实现
在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的约束条件。
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
Key key;
Value value;
Node left;
Node right;
boolean color;
public Node(Key key, Value value) {
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;
}
}
调整可以分为两类：
- 颜色调整：改变某个节点的颜色
- 结构调整：改变检索树的结构关系
结构调整过程包含两个基本操作：左旋，右旋。
每次添加一个节点，都要保证根节点为黑色：
public void add(Key key, Value value) {
root = addImproved(root, key, value);
root.color = BLACK;//保持根节点为黑色
}
插入新节点过程：
- 情况1：当插入第一个节点时，设置其颜色为黑色。
- 情况2：当插入第二个节点 37 时，需要插入到根节点的左侧，则直接插入即可，形式等同于 2-3树 的 3-节点，保持了红黑树的性质。
- 情况3：当根节点是 37，需要插入第二个节点 42 时，需要插入到根节点的右侧，红色节点就出现在黑节点的右侧了，需要进行 左旋转 以维护红黑树的性质，除此之外，我们还需要对节点的颜色进行维护：
颜色维护过程：
node.right = x.left;
x.left = node;
x.color = node.color;//旋转之前，node是根节点，旋转之后，x是根节点，所以x的颜色应该与node相同，保持根节点颜色一致。
node.color = RED;//旋转之后，node 和 x 组成 3-节点，所以 node 在左侧，需要改为红色。
最后，上面情况，node 是黑色的，如果当前树的没有这么简单，则在插入前 node 也可能是红色，情况就变成了在一个红色节点的右侧插入节点，则 x.color 也是红色了，左旋转导致了两个连续的红色节点，但在这种情况下，此时左旋转是一个子过程，会继续把 x 递归回去进行旋转。最终还是能满足红黑树的性质。
情况 2 和 3 就类似在2-3树中，向2-节点插入一个新的元素，形3-节点。
颜色翻转和右旋转
向红黑树中的 3-节点 中添加节点：
- 情况1：在黑色节点的右侧插入节点，相当于在 2-3树中的 3-节点的右侧插入节点，会形成临时的 4-节点，之后需要节点进行拆分，拆分成两个独立的 2-节点，这相当于要把红黑树中两个红色节点改为黑色，最后，拆分形成的根节点需要继续向上与它的父亲节点融合，红黑树中只有红色节点才表示它要与它的父节点进行融合，这意味着新形成的根节点需要变为红色。这个过程看似三个节点的颜色都变了，称为颜色翻转。
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
- 情况2：在一个红色节点和黑色节点组成的 3-节点 的左侧插入元素，这就形成了黑节点的左孩子和其左孩子的左孩子都是红色的，可以看成是临时的4-节点，此时需要对其进行右旋转，之后在对其进行颜色翻转，以维持红黑树的性质，具体过程如下：
//旋转
node.left = x.right;
x.right = node;
//颜色维护
x.color = node.color;//旋转后新形成的根节点与原来的根节点颜色保持一致
node.color = RED;//本质上还是 12 42 37 三个节点组成的临时的 4-节点。所以 node 要变为红色。
- 情况3：在一个红色节点和黑色节点组成的 3-节点 的中间插入元素，即在黑色节点的左侧孩子的右侧插入节点，这个过程的需要进行的变换过程是：先基于 37 几点进行左旋转：
变成情况2，再按情况2 的方式处理。即再右旋转+颜色翻转，整个过程如下：
维护红黑树的时机
先把节点按照 BST 的逻辑添加到树种，再回溯向上维护，与 AVL 一致。插入节点后，红黑树的性质维护是一个叠加的过程，而且有些情况属于另一些情况的子过程，参考下面箭头方向：
- 最复杂的是在红色节点的右侧插入红色节点，需要进行三次变换。
- 第一个箭头表示，在红色节点的左侧插入就等价于第一种情况进行左旋转之后的情况。
//递归插入节点后，三个过程不是互斥的，而是补充的。
private boolean isRed(Node node) {
if (node == null) {
return BLACK;
}
return node.color;
}
/*是否需要左旋转，右边的孩子是红色，左边的孩子不是红色*/
/*node 对应上图第二个情况，中间的红色节点*/
if (isRed(node.right) && !isRed(node.left)) {
node = leftRotate(node);
}
/*是否需要右旋转，右边的孩子是红色，左边孩子的左孩子也是红色*/
/*node 对应上图第三个情况，顶部黑色节点*/
if (isRed(node.left) && isRed(node.left.left)) {
node = rightRorate(node);
}
//是否需要进行颜色翻转
/*node 对应上图第四个情况，顶部黑色节点*/
if(isRed(node.right) && isRed(node.left)){
flipColor(node);
}