AVL树和红黑树02：2-3树和红黑树

2-3树

2-3树满足二分搜索树的基本性质，中间节点的值大于左子树，小于右子树

但是，其节点可以存放1个元素或者2个元素，即每个节点有2个孩子或者3个孩子，分别称为2节点和3节点

2-3树是一种绝对平衡树，任何时候任何节点的子树高度都一样，即要么是叶子节点，要么同时有左（中）右孩子

2-3树如何维持绝对的平衡

2-3树在添加节点时，新节点永远不会去空的位置，因此从根节点开始判断，最后遇到的节点肯定是叶子节点，此时分以下两种情况：

1、如果该叶子节点是一个2节点，那么直接和新节点合并成3节点

2、如果该叶子节点是一个3节点，那么在进行上述操作后，该节点变成了“4节点”，此时分以下两种情况：

• 如果该“4节点”是根节点，那么让该节点中间的那个元素成为新的根节点，左右两个元素分别为左右孩子（树的高度增加1）
• 如果该“4节点”不是根节点，那么在进行上述操作后，其父节点的左右子树必然不平衡了，此时让该子树的根节点和父节点融合，此时分以下两种情况：
  • 如果父节点是2节点，那么该子树边缘的那个孩子不动，靠近中间的那个孩子成为中间孩子
  • 如果父节点是3节点，那么在进行上述操作以后，父节点变成了“4节点”，此时让父节点中间的那个元素成为新的父节点，左右两个元素分别作为左右子树的根节点（树的高度增加1）

红黑树和2-3树的等价性

2-3树的2节点对应于红黑树的普通节点，是黑色的

而3节点拥有两个元素，对应在红黑树中则是让较小的元素作为该节点的左孩子，用红色来表示，因此所有的红色节点都是左倾斜的，且和父节点的连线是红色的，表示其对应于2-3树的3节点

可以将每个红节点和父节点看成是两个平等的节点，这样整体看红黑树也是绝对平衡树

红黑树的性质

红黑树同样满足二分搜索树的基本性质，但为了维持平衡二叉树的性质，需同时满足以下5个条件：

• 每个节点有且仅能是红色或者黑色
• 根节点是黑色的（因为红节点必然有父节点）
• 每个叶子节点（最后的空节点）是黑色的
• 一个红色节点的孩子节点都是黑色的（因为红节点的父节点必然是黑节点）
• 从任意一个节点出发到叶子节点，经过的黑色节点都是一样的（等价于2-3树的绝对平衡性，在红黑树中称为“黑平衡性”）

红黑树添加元素

红黑树删除元素非常复杂，因此没有进行介绍

保持根节点为黑色和左旋转

红黑树在添加节点时，新节点永远是红节点，因此从根节点开始判断，最后遇到的节点要么没有孩子，要么有左红孩子，此时分以下两种情况：

1、如果当前节点没有孩子，此时分以下两种情况：

• 如果小于当前节点，那么直接作为其左孩子
• 如果大于当前节点，那么先作为右孩子，然后对其进行左旋转，同时颜色发生改变，新树的左孩子为红节点，父节点颜色和左旋转之前的父节点一样

/**
 * 左旋转，然后改变颜色，此时的父节点x和之前的父节点node颜色一样
 *      node                                 x
 *     /   \                               /  \
 *   T1     x         左旋转（node）       node T3
 *        /  \     ---------------->     /   \
 *       T2  T3                         T1   T2
 */
private Node leftRotate(Node node){

    Node x = node.right;
    node.right = x.left;
    x.left = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

public void add(K key, V value){

    /**
     * 添加元素后，保持根节点为黑色
     */
    root = add(root, key, value);
    root.color = BLACK;
}
......

颜色翻转和右旋转

2、如果当前节点有左红孩子，此时分以下两种情况：

• 如果大于当前节点，那么直接作为其右孩子，且左右孩子节点颜色全部翻转为黑色，父节点为红色
• 如果小于当前节点，此时分以下两种情况：
  • 如果小于左孩子，那么先作为左孩子的左孩子，然后对当前节点进行右旋转，同时颜色发生改变，新树的右孩子为红节点，父节点颜色和右旋转之前的父节点一样。最后为了维持红黑树的性质，再进行一次颜色翻转
  • 如果大于左孩子，那么先作为左孩子的右孩子，然后对该左孩子进行左旋转，然后对父亲节点进行右旋转，具体操作和上述一样

/**
 * 右旋转，然后改变颜色，此时的父节点x和之前的父节点node颜色一样
 *          node                               x
 *         /   \                             /  \
 *       x     T2       右旋转（node）       T2   node
 *     /  \          ---------------->         /   \
 *   T2   T1                                  T1   T2
 */
private Node rightRotate(Node node){

    Node x = node.left;
    node.left = x.right;
    x.right = node;

    x.color = node.color;
    node.color = RED;

    return x;
}

/**
 * 翻转颜色
 * 父亲节点为红色，左右孩子为黑色
 */
private void flipColors(Node node){

    node.color = RED;
    node.left.color = BLACK;
    node.right.color = BLACK;
}
......

添加元素完整代码

class redBlackTree, V>{

    /**
     * 红黑树的节点需要一个判断颜色的属性，为了避免被修改，定义两个静态常量RED和BLACK来记录颜色，红色代表true
     */
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    class Node{

        /**
         * 为什么默认添加节点定义为红色？
         * 等价于在2-3树中每个新节点都要和其他节点进行融合（不能添加在空的位置），形成3节点或者“4节点”，然后再进行维护操作
         */
        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;
            color = RED;
        }
    }

    private Node root;
    int size;

    public redBlackTree(){

        root = null;
        size = 0;
    }

    public int getSize(){

        return size;
    }

    public boolean isEmpty(){

        return size == 0;
    }

    private boolean isRed(Node node){

        /**
         * 空节点定义为黑
         */
        if (node == null){
            return BLACK;
        }

        return node.color;
    }

    /**
     * 左旋转，然后改变颜色，此时的父节点x和之前的父节点node颜色一样
     *      node                                 x
     *     /   \                               /  \
     *   T1     x         左旋转（node）       node T3
     *        /  \     ---------------->     /   \
     *       T2  T3                         T1   T2
     */
    private Node leftRotate(Node node){

        Node x = node.right;
        node.right = x.left;
        x.left = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

    /**
     * 右旋转，然后改变颜色，此时的父节点x和之前的父节点node颜色一样
     *          node                               x
     *         /   \                             /  \
     *       x     T2       右旋转（node）       T2   node
     *     /  \          ---------------->         /   \
     *   T2   T1                                  T1   T2
     */
    private Node rightRotate(Node node){

        Node x = node.left;
        node.left = x.right;
        x.right = node;

        x.color = node.color;
        node.color = RED;

        return x;
    }

    /**
     * 翻转颜色
     * 父亲节点为红色，左右孩子为黑色
     */
    private void flipColors(Node node){

        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    public void add(K key, V value){

        /**
         * 添加元素后，保持根节点为黑色
         */
        root = add(root, key, value);
        root.color = BLACK;
    }

    private Node add(Node root, K key, V value){

        if (root == null){

            size++;
            return new Node(key, value);
        }

        if (root.key.compareTo(key) > 0){
            root.left = add(root.left, key, value);
        }
        else if (root.key.compareTo(key) < 0){
            root.right = add(root.right, key, value);
        }
        else {
            root.value = value;
        }

        /**
         * 添加新节点后，根据下面三个判断条件来维护红黑树的性质
         * 1、如果当前节点没有孩子，且新节点大于当前节点（小于的话直接添加默认就是红色），那么先作为右孩子，然后对其进行左旋转
         */
        if (isRed(root.right) && !isRed(root.left)){
            root = leftRotate(root);
        }

        /**
         * 2、如果当前节点有左红孩子，且新节点小于左孩子，那么先作为左孩子的左孩子，然后对当前节点进行右旋转
         */
        if (isRed(root.left) && isRed(root.left.left)){
            root = rightRotate(root);
        }

        /**
         * 3、最后判断是否要进行颜色翻转，如果左右孩子都是红色就翻转
         */
        if (isRed(root.left) && isRed(root.right)){
            flipColors(root);
        }

        return root;
    }
}

红黑树的性能总结

拓展：另一种统计性能优秀的树结构Splay Treee（伸展树），其基于局部性原理，即刚被访问的内容下次高概率被再次访问