算法-红黑树
标签:算法

红黑树

1. 2-3树

2-3树是一棵绝对平衡的树

对于三节点存放的值就是在上面的两个元素之间

2-3树添加一个节点不会把他添加一个空节点上去,而是找到它最后添加的叶子节点,和叶子节点做融合。

1.1 2-3树添加过程

1.2 2-3树添加示例

1.3 2-3树和红黑树

红黑树的2节点与3节点与红黑树的红黑节点

将2-3树转换为红黑树

2. 红黑树的五个性质

  1. 每个节点要么是红色的,要么是黑色的
  2. 根节点是黑色的(等价于2-3树,2-3树对应的在红黑树中的节点的根节点都是黑色的)
  3. 每一个叶子节点(最后的空节点)是黑色的 (相当于在定义红黑树中空这个节点是黑色的,对于一棵空树也是红黑树,这个空即是叶子节点也是根节点)
  4. 如果一个节点是红色的,那么它的孩子节点都是黑色的,对于黑节点,它的右孩子一定是一个黑色节点
  5. 从任意一个节点到叶子节点,经过的黑色节点是一样的(因为2-3树是一棵绝对平衡的树,在2-3树中从任意节点到叶子节点走过路程是一样的,对应到红黑树就是经过的黑色节点)

红黑树是保持黑平衡的二叉树,从根节点到叶子节点,走过的黑色节点的个数是一样多的,严格意义上讲,不是一棵平衡二叉树,故最大的高度为 2logn ,故增删改查的时间复杂度都为仍为 O(logn)

对于数据结构要经常添加,删除的话红黑树的效率比AVL树效率要高,但如果我们创建的树之后不常修改的话,AVL的效率会更好一些。

3. 红黑树添加新元素

3.1 向红黑树的2节点添加元素

向2节点添加元素,如果要添加的元素比它最后要融合的叶子节点要大的话,那么就会发生异常左旋转。

3.2 向红黑树的3节点添加元素

上面也存在两种情况,当添加的元素比现在的根要大时,相当于把元素添加到三节点的右边,最后需要进行一次颜色翻转

    /**
     * 颜色翻转
     *
     * @param node
     */
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

下面这种情况是,要添加的元素在3节点的最左侧,需要进行一次右旋转,再进行一次颜色翻转,对应的右旋转代码为:

    //     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;
    }

如果要添加的元素在3节点的两个元素之间的话,那么


把上面的三种情况综合一下就有下面这个图:

3.3 最后的添加代码

    // 向以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;
    }

4. 小结

  • 5 min read

CONTRIBUTORS


  • 5 min read