红黑树简介

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二分搜索树。红黑树的每个节点上都有存储为表示节点的颜色，可以是红(Red)或黑(Black)。

1、红黑树的特性

红黑树特性

2、2-3树

说到红黑树，不得不说与它等价的一种树——2-3树。一种节点可以存放最多2个元素的树。

2-3树

2-3树是一个绝对平衡的树：对于任意一个节点来说，左右子树高度一定是相等的。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树节点关系
红黑树和2-3树的等价关系，如下图：
红黑树和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的旋转操作次数会更多，从而影响了性能。所以对于统计性能（综合增删改查的所有操作）来说，红黑树是更优的。

红黑树的性能总结