数据结构 -红黑树

1. 二分搜索树
2. 平衡二叉树
3. 每个节点是红色或者黑色
4. 根节点是黑色
5. 每一个叶子节点（最后空节点）是黑色的
6. 如果一个节点是红色，那么孩子节点都是黑色
7. 从任意一节点到叶子节点经过的黑色节点是一样的

二、 2-3树介绍

1. 满足二分搜索树
2. 节点可以存放一个元素或者两个元素
3. 每一个节点或者有2个孩子或者有3个孩子（2节点、3节点）
4. 2-3 树是一只绝对的平衡的树（任意一节点左右子树高度相等））

三、2-3树通过什么机制维持它的绝对平衡

插入不是根节点 插入3节点 父亲为2节点， 直接让父亲节点变成3节点 插入3节点 父亲为3节点，向上融合父节点变成临时4节点，然后4节点拆成两个2节点

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

Red 等价于 3节点

五、红黑树的实现

public static final boolean RED = true;
    public static final boolean BLACK = false;

    private class Node {
        public K key;
        public V value;
        public Node left, right;
        public boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            color = RED;
        }
    }
复制代码

红黑树更多考察你的原理，旋转之类的不会白板编程红黑树的实现操作

五、维持根节点是黑色

// 向红黑树中添加新的元素(key, value)
    public void add(K key, V value){
        root = add(root, key, value);
        root.color = BLACK; // 最终根节点为黑色节点
    }

复制代码

六、左旋转

//   node                     x
    //  /   \     左旋转         /  \
    // T1   x   --------->   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;
    }
复制代码

// 颜色翻转
    private void flipColors(Node node){

        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
复制代码

七、右旋转

//     node                   x
    //    /   \     右旋转       /  \
    //   x    T2   ------->   y   node
    //  / \                       /  \
    // y  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;
    }
复制代码

八、红黑树添加新节点

// 向以node为根的红黑树中插入元素(key, value)，递归算法
    // 返回插入新节点后红黑树的根
    private Node add(Node node, K key, V value){

        if(node == 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 // key.compareTo(node.key) == 0
            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;
        return node;
    }
复制代码

九、红黑树的性能总结

1. 对于完全随机的数据，普通的二分搜索树很好用。缺点：极端情况下会退化成链表
2. 对于查询较多的，AVL树很好用
3. 红黑树牺牲了平衡性，最高的高度达到2logn 比AVL 树高
4. 红黑树统计性能更优（综合增删改查操作）