红黑树简介
R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二分搜索树。红黑树的每个节点上都有存储为表示节点的颜色，可以是红(Red)或黑(Black)。
1、红黑树的特性
2、2-3树
说到红黑树，不得不说与它等价的一种树——2-3树。一种节点可以存放最多2个元素的树。
2-3树是一个绝对平衡的树：对于任意一个节点来说，左右子树高度一定是相等的。2-3树也满足二分搜索树的特性。
-
2-3树插入元素的演变过程
当插入元素 4 时，根据二分搜索树的特性，是在根节点6的左侧，然后与3节点2-5融合成为4节点2-4-5，又由于2-3树最多只能允许3节点，于是需要拆分，即将4节点2-4-5根据二分搜索树特性拆分成一个子的二分搜索树，然后该子二分搜索树的根节点4继续与其父亲节点融合。假如融合之后不是2节点或者3节点，则需要继续拆分。
2-3树插入元素的演变过程
3、红黑树与二分搜索树
其实，红黑树和2-3树是等价的，只是红黑树的节点只能存放一个元素，并且颜色只能红或黑。我们可以将红色节点视为2-3树中3节点较小的那个元素，并且约定：红黑树中，所以红色节点都是左倾斜的。注意：这里这样的约定，是为了后续操作简单，但是这并不是红黑树的特性，红黑树的特性只有上面介绍的5个。
红黑树和2-3树的等价关系，如下图：
红黑树是保持“黑平衡”的二叉树，黑平衡：从任意一个节点出发到叶子结点，所经过的黑色节点数量是一样的。严格意义上，红黑树不是平衡二叉树。因为最坏情况下，每个黑色节点都有一个红色的左孩子，使树的高度接近2h。
4、红黑树的源码结构
由于红黑树也是二分搜索树，于是我们直接使用之前的二分搜索树的结构，只是Node节点新增了颜色标识的变量color，并且新增的节点颜色为红色。因为红色节点是表示2-3树中的3节点的一个元素，即在红黑树中，是和其父亲节点融合的元素。并且不会违背"特性5"！少违背一条特性，就意味着我们需要处理的情况越少。
/**
* 红黑树
*/
public class RBTree<K extends Comparable<K>, V> implements Map<K, V> {
private final static boolean RED = true;
private final static boolean BLACK = false;
private class Node{
//当前节点的值
public K key;
public V value;
//左节点
public Node left;
//右节点
public Node right;
// 颜色
public boolean color;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
/**
* 新增的节点都是需要和2-3树中其父亲节点进行融合的，
* 而在2-3树中的2节点（只有一个元素的节点）在红黑树中是用黑节点表示的，
* 所以新增节点采用红色。
*/
color = RED;
}
}
private Node root;
private int size;
红黑树的左旋转
和AVL一样，新增或者删除元素，都会破坏二分搜索树的特性，也会破坏红黑树自身的特性。所以需要通过旋转和颜色翻转来使其重新回到红黑树的特性上，我们先讲左旋转。
如下图：当我们新增节点 x 时，破坏了我们之前的约定（红色节点只能在左侧），于是需要左旋转（和AVL左旋转类似，就是多了着色操作）。
对node节点进行左旋转，让node节点的右子树指向x节点的左子树，即node.right = x.left；然后让x节点的左子树指向node节点，即x.left = node；然后让x节点的颜色变成node节点的颜色，即x.color = node.color；最后将旋转之后的根节点置为红节点，继续与其父亲节点进行融合操作。
左旋转代码实现：
// 红黑树左旋转:由于我们约定红色节点只能在左侧，
// 于是需要对红色节点在右侧的情况进行左旋转
// node x
// / \ 左旋转 / \
// T1 x ---------> node T3
// / \ / \
// T2 T3 T1 T2
private Node leftRotate(Node node){
if (node == null) {
return node;
}
Node x = node.right;
node.right = x.left;
x.left = node;
x.color = node.color;
// 这里必须变为红色，表示要和父亲节点x融合的
node.color = RED;
return x;
}
红黑树的右旋转
右旋转和左旋转是相反的，我就不累赘了，直接给视图。
这里需要注意的是，右旋转完成之后，x的右孩子成了红色节点，这个与我们约定的违背了，于是需要颜色翻转，下面介绍颜色翻转。
右旋转代码实现：
// 红黑树右旋转：当左侧连续有两个红色节点时，则需要右旋转
// node x
// / \ 右旋转 / \
// x T2 -------> y node
// / \ / \
// y T1 T1 T2
private Node rightRotate(Node node){
if (node == null) {
return node;
}
Node x = node.left;
node.left = x.right;
x.right = node;
x.color = node.color;
// 这里必须变为红色，表示要和父亲节点x融合的
node.color = RED;
return x;
}
红黑树的颜色翻转
当左右孩子的节点都为红色时，这时候违背了我们约定的红色节点只能在左侧的特性。其实，这种情况，在2-3树中就是一个4节点，是需要拆分成二分搜索树的。在红黑树中，我们把当前3个节点的颜色翻转一下就OK了。
如下图：
向2-3树中的3节点添加一个元素，会进行融合拆分的过程。对于红黑树来说，此时左右孩子都是红色节点，满足颜色翻转的条件。
颜色翻转之后，如下图：
颜色翻转代码实现：
// 颜色翻转：当向2-3树中的3节点添加元素时，需要进行融合再分散；
// 当新增元素之后，形成的红黑树是根节点为黑色，左右孩子为红色时，
// 此时节点位置不用变化，直接翻转下节点颜色，即根节点为红色，左右孩子为黑色。
// 注意：这里把根节点置为红色是为了后面和其父亲节点进行融合，因为融合节点是红色。
private void flipColors(Node node){
if (node == null) {
return;
}
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
红黑树的添加元素
讲完红黑树的左右旋转和颜色翻转，就可以进行添加操作了。
当新增元素的父亲节点（所需融合的节点）为2节点，这个简单，假如比此2节点的值小，则放入左孩子；比此2节点的值大，先放入右孩子，然后进行左旋转，旋转之后的根节点当成当前节点，继续与其父亲节点进行融合。
当新增节点的父亲节点是3节点，当新增的元素的值在3节点的两个元素值之间，则需要依次进行左旋转，右旋转，颜色翻转操作；当新增的元素的值比3节点的两个元素的最小值还小，需要依次执行右旋转，颜色翻转；当新增的元素的值比3节点的两个元素值的最大值还大，则直接颜色翻转。
我们可以发现，红黑树的添加元素操作，操作顺序都是 左旋转——> 右旋转 ——> 颜色翻转，3个操作步骤可以跳过，但是顺序不变。
红黑树的添加元素操作我们是在二分搜索树的添加操作之上进行的。
添加元素的代码实现：
@Override
public void add(K key, V value) {
root = add(root, key, value);
// 最终根节点为黑色节点
root.color = BLACK;
}
// 向 node 为根的红黑树中添加新的元素（key, value）
// 返回插入新节点后的红黑树的根
private Node add(Node node, K key, V value) {
//递归终止条件
if (node == null) {
//表示到达最后一个根节点null，则将新节点放入该位置
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0){
//将插入新节点后的红黑树的根挂在当前树上
node.left = add(node.left, key, value);
}else if(key.compareTo(node.key) > 0){
node.right = add(node.right, key, value);
}else {
node.value = value;
}
/**
* 红黑树添加元素的动作：左旋转—> 右旋转—> 颜色翻转
* 注意：可跳过，但是顺序不变
*/
// 判断是否需要左旋转
if (isRed(node.right) && !isRed(node.left)){
node = leftRotate(node);
}
// 判断是否需要右旋转
if (isRed(node.left) && isRed(node.left.left)){
node = rightRotate(node);
}
// 判断是否需要颜色翻转
if (isRed(node.left) && isRed(node.right)){
flipColors(node);
}
return node;
}
最终，我们需要对根节点的颜色置为黑色。所以在递归之后，需要执行root.color = BLACK；递归添加元素还是二分搜索树的逻辑，我们需要做的就是在添加完成之后，对破坏了红黑树特性的情况使其重新恢复红黑树的特性。根据上面的分析，添加的动作执行的操作顺序是，左旋转——> 右旋转 ——> 颜色翻转。于是我们依次根据条件进行各个操作，如果符合左旋转条件：右孩子为红色节点并且左孩子为黑色节点，则执行左旋转操作，并且把旋转之后的根节点赋值给node，因为需要继续执行后续操作；如果符合右旋转条件：左孩子和左孩子的左孩子都为红色节点，则进行右旋转操作，并且旋转之后的根节点赋值给node；如果符合颜色翻转条件：左右孩子都为红色节点，则执行颜色翻转操作。
红黑树的性能总结
对于完全随机的数据，普通的二分搜索树很好用，因为没有旋转的操作从而没有性能的损耗，缺点是：极端情况退化成链表或者高度不平衡。对于查询较多的情况，AVL树很好用，因为红黑树牺牲了平衡性，树的高度可以达到近2h（h 为相同节点数量下的AVL树的高度）。但是添加或者删除元素，红黑树性能则优于AVL树，因为AVL是平衡的二叉树，对于平衡性的依赖极高，添加或者删除元素，极可能的破坏其平衡性，所以相对于红黑树，AVL的旋转操作次数会更多，从而影响了性能。所以对于统计性能（综合增删改查的所有操作）来说，红黑树是更优的。
