数据结构 -红黑树

593 阅读2分钟

一、红黑树定义

  1. 二分搜索树
  2. 平衡二叉树
  3. 每个节点是红色或者黑色
  4. 根节点是黑色
  5. 每一个叶子节点(最后空节点)是黑色的
  6. 如果一个节点是红色,那么孩子节点都是黑色
  7. 从任意一节点到叶子节点经过的黑色节点是一样的
1. 太过生硬
2. 和2-3树的等价性,理解2-3树和红黑树直接的关系

二、 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. 红黑树统计性能更优(综合增删改查操作)