7 红黑树

Wu Jun 2019-12-25 15:59:04
01 数据结构与算法 > 数据结构 > 01 数据结构

1、红黑树定义

红黑树是一种近似平衡的二叉查找树,它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一陪。可以在 O(logn) 时间内做查找,插入和删除。红黑树相对于AVL树来说,牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。

满足如下条件:

  1. 每个节点要么是红色,要么是黑色。
  2. 根节点是黑色的
  3. 每个叶子节点是黑色的
  4. 红色节点不能连续(红色节点的孩子和父亲都不能是红色)。
  5. 从任意一个节点到叶子节点,经过的黑色节点是一样的。

1、红黑树与2-3树的等价性

参考下图,再红黑树中使用两个节点来模拟 2-3 树中的 3-节点,使用红色来表示 b 与 c 是并列的关系,如果来表示这条红色的边呢,其实就是让 b 这个节点变为红色,而 b 只有一个父节点,所以其与父节点的连线也就是红色,本质上就是把并列关系存储在子节点中。

用红黑树来表示对等的 2-3 树:

再来回顾以下上面关于红黑树的 5 条定义:

红黑树是保持 黑平衡 的二叉树。严格定义来讲,不是平衡二叉树,最大高度为(最坏的情况) 2(logn)。

2、红黑树实现

在树的结构发生改变时(插入或者删除操作),往往会破坏上述条件3或条件4,需要通过调整使得查找树重新满足红黑树的约束条件。

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

 private class Node {

        Key key;
        Value value;
        Node left;
        Node right;
        boolean color;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            color = RED;
        }

    }

调整可以分为两类:

每次添加一个节点,都要保证根节点为黑色:

public void add(Key key, Value value) {
    root = addImproved(root, key, value);
    root.color = BLACK;//保持根节点为黑色
}

插入新节点过程:

颜色维护过程:

node.right = x.left;
x.left = node;
x.color = node.color;//旋转之前,node是根节点,旋转之后,x是根节点,所以x的颜色应该与node相同,保持根节点颜色一致。
node.color = RED;//旋转之后,node 和 x 组成 3-节点,所以 node 在左侧,需要改为红色。

最后,上面情况,node 是黑色的,如果当前树的没有这么简单,则在插入前 node 也可能是红色,情况就变成了在一个红色节点的右侧插入节点,则 x.color 也是红色了,左旋转导致了两个连续的红色节点,但在这种情况下,此时左旋转是一个子过程,会继续把 x 递归回去进行旋转。最终还是能满足红黑树的性质。

情况 2 和 3 就类似在2-3树中,向2-节点插入一个新的元素,形3-节点。

颜色翻转和右旋转

向红黑树中的 3-节点 中添加节点:

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

//旋转
node.left = x.right;
x.right = node;
//颜色维护
x.color = node.color;//旋转后新形成的根节点与原来的根节点颜色保持一致
node.color = RED;//本质上还是 12 42 37 三个节点组成的临时的 4-节点。所以 node 要变为红色。

变成情况2,再按情况2 的方式处理。即再右旋转+颜色翻转,整个过程如下:

维护红黑树的时机

先把节点按照 BST 的逻辑添加到树种,再回溯向上维护,与 AVL 一致。插入节点后,红黑树的性质维护是一个叠加的过程,而且有些情况属于另一些情况的子过程,参考下面箭头方向:

//递归插入节点后,三个过程不是互斥的,而是补充的。
private boolean isRed(Node node) {
    if (node == null) {
        return BLACK;
    }
    return node.color;
}

/*是否需要左旋转,右边的孩子是红色,左边的孩子不是红色*/
/*node 对应上图第二个情况,中间的红色节点*/
if (isRed(node.right) && !isRed(node.left)) {
    node = leftRotate(node);
}

/*是否需要右旋转,右边的孩子是红色,左边孩子的左孩子也是红色*/
/*node 对应上图第三个情况,顶部黑色节点*/
if (isRed(node.left) && isRed(node.left.left)) {
    node = rightRorate(node);
}

//是否需要进行颜色翻转
/*node 对应上图第四个情况,顶部黑色节点*/
if(isRed(node.right) && isRed(node.left)){
    flipColor(node);
}