红黑树(下):红黑树的增删方法实现


1 插入节点

红黑树插入节点的过程与 二叉排序树一样,都是利用二分法查找空位并插入,只是插入后需要做自平衡操作。实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public void insert(K key, V value) {
    Node<K,V> t = root;
    // 如果空树,直接插入黑色根节点
    if (t == null) {
        root = new Node<>(key, value, null);
        count = 1;
        return;
    }
    // 递归查找插入位置,同二叉排序树
    Node<K, V> parent;
    int compare;
    do {
        parent = t;
        compare = key.compareTo(t.key);
        if (compare < 0) {
            t = t.left;
        } else if (compare > 0) {
            t = t.right;
        } else {
            // 如果 key 值相等,做更新操作
            t.setValue(value);
            return;
        }
    } while (t != null);
    // 找到了空位,开始插入
    Node<K, V> e = new Node<>(key, value, parent);
    if (compare < 0) {
        // 作为左子节点
        parent.left = e;
    } else {
        parent.right = e;
    }

    // 插入节点后,进行自平衡
    fixAfterInsertion(e);
    ++count;
}

2 插入节点后的自平衡操作

fixAfterInsertion 自平衡方法实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
private void fixAfterInsertion(Node<K,V> x) {
    // 新插入节点默认为红色
    x.color = RED;

    while (x != null && x != root && x.parent.color == RED) {
        // 如果父节点是祖父节点的左子节点
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            Node<K, V> uncleNode = rightOf(parentOf(parentOf(x)));
            if (colorOf(uncleNode) == RED) {
                // 如果存在红色叔叔节点,变色即可
                setColor(parentOf(x), BLACK);
                setColor(uncleNode, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                // 祖父节点染红后,作为新节点向上递归
                x = parentOf(parentOf(x));
            } else { // 如果不存在红色叔节点,则需要旋转 + 染色
                // 如果新节点是父节点的右节点,则构成 LR 型场景
                if (x == rightOf(parentOf(x))) {
                    // 需要先对 x 和 x.p 左旋
                    x = parentOf(x);// 旋转后,x 与 x.p 会颠倒,所以记录下来旋转后的子节点
                    rotateLeft(parentOf(x));
                }
                // 无论是 LR 还是 RR,都需要对旋上来的新节点和祖父节点右旋,此时 x 始终为新插入节点处的节点
                rotateRight(parentOf(parentOf(x)));
                // 旋转完成后,需要将新插入的节点染黑,同时将 x 祖父节点染红
                setColor(parentOf(x), BLACK);// x 与 x.p 颠倒了,所以 parOfx 实际上是新插入的节点
                setColor(rightOf(parentOf(x)), RED);// 原祖父节点,此时是新插入节点的右节点
            }
        } else { // 如果祖父节点是父节点的右子节点
            Node<K, V> uncleNode = leftOf(parentOf(parentOf(x)));
            if (colorOf(uncleNode) == RED) {
                // 如果存在红色叔叔节点,变色即可
                setColor(parentOf(x), BLACK);
                setColor(uncleNode, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                // 祖父节点染红后,作为新节点向上递归
                x = parentOf(parentOf(x));
            } else {
                // 如果新节点是父节点的左子节点,构成 RL 型场景
                if (x == leftOf(parentOf(x))) {
                    // 对称:需要先将 x 和 x.p 右旋
                    x = parentOf(x); //缓存将来在新插入位置的节点,也就是现在的父节点
                    rotateRight(parentOf(x));
                }
                // 对称:对旋上来的新节点和原祖父节点左旋
                rotateLeft(parentOf(parentOf(x)));
                // 旋转完成后,需要将新插入的节点染黑,同时将 x 祖父节点染红
                setColor(parentOf(x), BLACK);
                setColor(leftOf(parentOf(x)), RED);
            }
        }
    }

    // 处理完后,将根节点染黑
    root.color = BLACK;
}

3 删除节点

红黑树删除节点的过程与 二叉排序树一样,都是利用二分法查找目标节点并删除,只是删除后需要做自平衡操作。实现如下:

1
2
3
4
5
6
7
8
9
public void remove(K key) {
    // 查询节点
    Node<K, V> p = search(key);
    if (p == null) {
        return;
    }
    // 执行删除操作
    deleteNode(p);
}

其中的 search 方法实现原理与 二叉排序树相同,这里不再赘述。我们重点关注其 deleteNode 方法:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
private void deleteNode(Node<K,V> s) {
    --count;

    // 如果被删除节点的左右子节点均不为空,则使用左子树中的最大节点(前驱)代替被删除的节点
    // (参数 s 节点处的颜色不变)
    if (s.left != null && s.right != null) {
        Node<K, V> p = predecessor(s);
        s.key = p.key;
        s.value = p.value;
        // 并将 s 引用指向前驱节点
        s = p;
    }

    /*
        如果参数 s 的左右子节点都存在,则 replacement 指向 s 的前驱节点(p)的左子节点:
            s
           / \
          l   r
           \
           lr
             \
              p
             /
           sl <- replacement
        否则,replacement 指向 s 的唯一子节点
            s                         s
             \          or           /
              r <- replacement ---> l
    */
    Node<K, V> replacement = s.left != null ? s.left : s.right;

    if (replacement != null) {
        /*
        如果参数 s 的左右子节点都在,那么用前驱节点覆盖 s 后,需要删除前驱节点,并处理前驱节点的左子节点 replacement
        如果参数 s 只存在一个子节点,也需要用这个子节点短接 s
        所以用 replacement 指向 前驱节点的左子节点 或者参数 s 的唯一子节点
            */
        // 用 replacement 短接 s
        replacement.parent = s.parent;
        if (s.parent == null)
            root = replacement;
        else if (s.parent.left == s)
            s.parent.left = replacement;
        else
            s.parent.right = replacement;
        // 将 s(参数 s,或参数 s 的前驱节点 s)摘下
        s.left = s.right = s.parent = null;
        // 如果刚被短接 s 是红色的,不需要再平衡
        // 否则,需要对它的子节点 replacement 执行再平衡
        if (s.color == BLACK)
            fixAfterDeletion(replacement);
    } else if (s.parent == null) {
        // 如果 s(必为参数 s)的子节点为空,且父节点也为空
        // 说明被删节点就是树中唯一的 root,直接删除即可
        root = null;
    } else {
        // 如果要删除的 s 是个叶子节点,
        //  如果是红色节点,直接删除
        //  否则,使用 s 自己做自己的 “幻影子节点”,进行再平衡
        if (s.color == BLACK)
            fixAfterDeletion(s);
        // 先平衡幻影子节点,再删除
        if (s.parent != null) {
            if (s == s.parent.left)
                s.parent.left = null;
            else if (s == s.parent.right)
                s.parent.right = null;
            s.parent = null;
        }
    }
}

4 删除节点后的自平衡操作

删除节点后的自平衡方法 fixAfterDeletion 实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
 * 当直接删除了黑色节点,或者被拿来替换的前驱节点是黑节点时,需要对其子节点执行再平衡
 * @param x 被删节点 s 的唯一子节点 或 被用来替换的前驱节点 p 的子节点
 *          如果没有子节点,则传入自身
 */
private void fixAfterDeletion(Node<K,V> x) {
    while (x != root && colorOf(x) == BLACK) {
        // 如果当前节点是其父节点的左子节点
        if (x == leftOf(parentOf(x))) {
            // 拿到 x 的兄弟节点
            Node<K,V> sib = rightOf(parentOf(x));
            // 如果兄弟节点是红色
            if (colorOf(sib) == RED) {
                /*
                  将兄弟节点染黑,父节点染红,最后左旋兄弟节点和父节点
                */
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateLeft(parentOf(x));
                sib = rightOf(parentOf(x));
            }

            if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(rightOf(sib)) == BLACK) {
                    setColor(leftOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateRight(sib);
                    sib = rightOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(rightOf(sib), BLACK);
                rotateLeft(parentOf(x));
                x = root;
            }
        } else { // 如果当前节点是其父节点的右子节点
            Node<K,V> sib = leftOf(parentOf(x));

            if (colorOf(sib) == RED) {
                setColor(sib, BLACK);
                setColor(parentOf(x), RED);
                rotateRight(parentOf(x));
                sib = leftOf(parentOf(x));
            }

            if (colorOf(rightOf(sib)) == BLACK &&
                    colorOf(leftOf(sib)) == BLACK) {
                setColor(sib, RED);
                x = parentOf(x);
            } else {
                if (colorOf(leftOf(sib)) == BLACK) {
                    setColor(rightOf(sib), BLACK);
                    setColor(sib, RED);
                    rotateLeft(sib);
                    sib = leftOf(parentOf(x));
                }
                setColor(sib, colorOf(parentOf(x)));
                setColor(parentOf(x), BLACK);
                setColor(leftOf(sib), BLACK);
                rotateRight(parentOf(x));
                x = root;
            }
        }
    }

    setColor(x, BLACK);
}

至此,红黑树的特性就介绍完了。