左斜红黑树

发表于 更新于 分类于 阅读次数：
本文字数： 6.9k 阅读时长 ≈ 6 分钟

1. 介绍

红黑树是 2-3 树的一种简易实现方式，它拥有两种链接，红链接和黑链接。

黑链接是普通的二叉查找树链接，红链接表示了一个 3-节点

Red Black Tree

在这里，我们使用的是左斜的红黑树，它满足以下条件：

  1. 红链接永远在左边（向左倾斜）
  2. 一个节点不能同时链接两个红链接
  3. 红黑树是完美黑链接平衡的

需要注意的是，如果红黑树满足以上条件，那么其和 2-3 树就是等价的。
事实上，如果把红链接画平，那么红黑树就是一个 2-3 树。

2. 新的节点定义

为了表示链接的颜色，我们需要定义一个新的节点，或者说向原有节点增加新的属性——颜色。

1
2
3
4
5
6
pravite class Node {
    Key key;
    Value val;
    int N;
    boolean color;
}

在这里，我们为原有的节点增加一个布尔值来表示指向它的链接的颜色，这样定义能省去一些麻烦，具体在下面的内容中会讨论到。

3. 变形

当我们往红黑树插入节点时，需要进行一些变形来让红黑树满足以上条件，就像我们对 2-3 树插入节点时做的处理一样。

3.1 旋转

第一个重要的变形是旋转变形。
当我们在插入节点的时候，不可避免的会破坏红黑树的条件，有时会出现红色的右链接，或者两个连续的红链接等。
对于这些情况，我们需要对红黑树做适当的旋转变换来让它重新满足红黑树的条件。

3.1.1 向左旋转

Rotate Left

由图可以注意到，所谓的旋转主要做了两件事：

  1. 交换根节点
  2. 将中间子树调换父亲

剩下就是转换颜色，修改子树节点数目等。
抓住这个根本操作，就不会出错。

1
2
3
4
5
6
7
8
9
10
11
12
13
Node rotateLeft(Node h) {
    Node x = h.right;
    h.right = x.left;   // Link the middle
    x.left = h;         // x ship to the root
    x.color = h.color;  // Change color
    h.color = RED;      // Change color
    x.N = h.N;          // Ship amount

    // Calculate the amount of left subtree
    h.N = 1 + size(h.left) + size(h.right);

    return x;           // Return new root
}

注意，我们采用了和二叉查找树一样的递归返回引用的方法，这样有利于重用原有代码和维护树的链接性。

3.1.2 向右旋转

这个方法和向左旋转大同小异，核心的思想就是转换根节点和中间子树。

关于必要性：有些时候遇到复杂的红链接情况，就首先要将连接向右旋转，随后在进行其他变形操作。

虽然红黑树条件中不允许红色右链接的存在使得此方法显得无意义，但是此方法的用意在于构建一个便于处理的中间状态。

Rotate Right

3.2 颜色转换

当我们在进行旋转的过程中，很可能会遇到两个子节点的链接都是红色的情况。

由于红链接代表了 3-节点，显然 2 个红链接就代表了一个 4-节点，在 2-3 树插入中，我们需要将临时的 4-节点 分裂，在红黑树中就是第二种变形——颜色转换。

步骤如下：

  1. 将两个红链接变成黑链接
  2. 将父节点的链接颜色变为红色

Flip Colors

1
2
3
4
5
void filpColors(Node h) {
    h.color = RED;
    h.left.color = BLACK;
    h.right.color = BLACK;
}

这很好地体现了 4-节点 的分裂过程。
首先，我们将红链接变为黑色，事实上增加了两个新节点，也就是将 4-节点 分裂了
其次，将父节点的链接变为红色，此时父节点就会变为上层 3-节点 的一部分，也满足了在分裂过程中，将中间节点向上传递的思想。

假如父节点是根节点时，由于没有任何链接指向根节点，所以根节点的颜色变得无关紧要了
这也是为什么我们在定义新节点的时候要将其颜色定义为指向其链接的颜色的原因

4. 插入

最后，我们终于进入了真正的插入环节，根据 2-3 树的插入思想，红黑树的插入步骤如下：

  1. 新节点的颜色是红色的

    由于 2-3 树在插入之后一定会形成至少一个 3-节点（有时还会有临时的 4-节点）

  2. 如果右子结点是红色，左子结点是黑色，那么向左旋转

    右子结点为红色，左子结点为黑色，说明红黑树中存在红色的右链接，将其向左旋转

  3. 如果左子结点和它的左子结点都是红色的，那么将当前节点向右旋转

    这种情况说明红黑树中存在两个连续的红色链接，说明存在一个内部的 4-节点，此时我们将其向右旋转，变为可以进行颜色转换的状态，随后通过颜色转换来将 4-节点 分裂

  4. 如果左子结点和右子结点都是红色的，那么进行颜色转换

    此时说明存在 4-节点，通过颜色转换将其分裂

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
public void put(Key key, Value val) {
    root = put(root, key, val);
    root.color = BLACK;
}

private Node put(Node h, Key key, Value val) {
    if (h == null)
        return new Node(key, val, 1, RED);

    // 插入位置的搜寻过程
    int cmp = key.compareTo(h.key);
    if (cmp < 0)
        h.left = put(h.left, key, val);
    else if (cmp > 0)
        h.right = put(h.right, key, val);
    else
        h.val = val;

    // 旋转和颜色转换
    // 注意以下顺序不可改变
    if (isRed(h.right) && !isRed(h.left))
        h = rotateLeft(h);

    if (isRed(h.left) && isRed(h.left.left))
        h = rotateRight(h);

    if (isRed(h.left) && isRed(h.right))
        flipColors(h);

    h.N = size(h.left) + size(h.right) + 1;

    return h;
}

需要注意的是，有可能存在需要多次变换的情况，所以上述检测需要依次进行一遍

比如折线式的红链接（红色的左链接 + 红色的右链接），此时就需要先将右链接向左旋转，变为连续的红链接，再将上面的链接进行右旋转，变为两个红色的子链接，随后进行颜色转换。

这样做的原因在于，我们可以按照图示那样， 逐步减少需要讨论的情况，从而节省代码

同时，为了能让父节点也能进行正确的变形，变形操作要放置在递归方法之后，也就是修改值之后再进行变形操作。

5. 删除

删除通常来说是符号表实现的一个比较难的部分。

对于红黑树来说， 我们不能直接删除一个黑节点，这样会导致黑节点出现不平衡。

一般的红黑树实现中，通常是对红黑树做一个 BST 的删除操作，随后再进行恢复，不过这样在实践中会导致代码过于冗长。

在左斜红黑树中，我们以 删除一个红节点 作为目标；

在删除完成后，我们通过递归向上对链接进行修复。

5.1 删除最大最小元素

为了能够让我们所删除的元素成为红节点，当出现连续两个子节点都是黑的时，我们就必须通过颜色变换将红链接向下传递；

否则红链接的特性就会断绝

但是，这样有可能导致两个连续的红链接，如下图所示；

b 节点并不在我们的递归路线中，我们无法对这种非法的 4-节点进行修复；

所以我们要对这种情况进行处理。

可以看到，我们首先将 a 节点进行颜色反转，从而将 c 染红；

但是此时，由于 b 也是红节点，所以造成了两个连续的红链接；

所以我们通过先将 c 向右旋转，再将 a 向左旋转，将其变为平衡态；

再通过颜色反转避免了连续的红链接出现。

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
private Node moveRedLeft(Node h) {
    //红链接向下传递
    colorFlip(h);

    // 出现红色后继
    if (isRed(h.right.left)) {
        h.right = rotateRight(h.right);
        h = rotateLeft(h);
        colorFlip(h);
    }

    return h;
}

完整的删除最小元素的代码如下：

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
public void deleteMin() {
    // 如果根节点的两个子节点都是黑色的，那么将根节点设为红
    // 以求能够有红链接属性向下传递
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;

    root = deleteMin(root);

    // 递归结束，将根节点恢复颜色
    if (!isEmpty())
        root.color = BLACK;
}

private Node deleteMin(Node h) {
    if (h.left == null)
        return null;

    // 如果连续两个子节点都是黑链接，那么将红链接性质传递
    if (!isRed(h.left) && !isRed(h.left.left))
        h = moveRedLeft(h);

    h.left = deleteMin(h.left);

    // 递归向上修复链接性质
    return balance(h);
}

// 实际上就是插入时使用的性质修复
private Node balance(Node h) {

    if (isRed(h.right))
        h = rotateLeft(h);
    if (isRed(h.left) && isRed(h.left.left))
        h = rotateRight(h);
    if (isRed(h.left) && isRed(h.right))
        flipColors(h);

    h.size = size(h.left) + size(h.right) + 1;
    return h;
}

同理，在删除最大元素和删除通常元素的时候，我们也会出现由于红链接向下传递引起的连续红链接问题，如图所示：

其中 d 不处在我们的递归路线上，所以就必须进行处理。

实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
private Node moveRedRight(Node h) {
    // 红链接向下传递
    flipColors(h);

    // 出现连续左斜红色
    if (isRed(h.left.left)) {
        h = rotateRight(h);
        flipColors(h);
    }

    return h;
}

完整实现如下：

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
public void deleteMax() {
    // 保证有红链接存在
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;

    root = deleteMax(root);

    // 恢复根节点的黑链接
    if (!isEmpty())
        root.color = BLACK;
}

private Node deleteMax(Node h) {
    // 由于是左斜红黑树，所以需要将左边的红链接右转
    // 以能够向下传递
    if (isRed(h.left))
        h = rotateRight(h);

    if (h.right == null)
        return null;

    // 如果没有连续的红链接，那么就将红链接向下传递
    if (!isRed(h.right) && !isRed(h.right.left))
        h = moveRedRight(h);

    h.right = deleteMax(h.right);

    return balance(h);
}

5.2 通常节点的删除

对于通常内部节点的删除，由于红黑树的特殊特性，我们直接使用 BST 的删除方法需要考虑的问题颇多；

但除此之外，我们可以使用一个巧妙的方法：

  1. 将节点设置为其后继节点
  2. 将其后继节点删除

这样既符合 BST 删除原理，同时我们可以重用现有的代码；

因为一个节点的后记节点，就是 其右子树的最小节点(min(h.right))；

因为我们已经实现了 deleteMin() 方法；

所以只需要简单的将节点交换，同时将后继删除即可。

完整的实现如下：

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
public void delete(Key key) {
    if (key == null)
        throw new  IllegalArgumentException("argument to delete() is null");
    if (!contains(key)) return;

    // 保证红链接向下传递
    if (!isRed(root.left) && !isRed(root.right))
        root.color = RED;

    root = delete(root, key);

    // 递归结束，将根节点恢复
    if (!isEmpty())
        root.color = BLACK;
}

private Node delete(Node h, Key key) {
    if (key.compareTo(h.key) < 0)  {    // 在左子树

        // 如果没有连续的红链接，则将红链接向下传递
        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);

        h.left = delete(h.left, key);
    }
    else {  // 在右子树或者命中

        // 左斜红黑树
        // 将左边的红链接向右转，以向下传递
        if (isRed(h.left))
            h = rotateRight(h);

        // 到达最大节点
        if (key.compareTo(h.key) == 0 && (h.right == null))
            return null;

        // 没有连续的红链接，将红链接向下传递
        if (!isRed(h.right) && !isRed(h.right.left))
            h = moveRedRight(h);

        // 内部节点
        if (key.compareTo(h.key) == 0) {

            // 后继
            Node x = min(h.right);

            // 将节点交换为后继
            h.key = x.key;
            h.val = x.val;

            // 删除后继节点
            h.right = deleteMin(h.right);
        }
        else
            h.right = delete(h.right, key);
    }
    return balance(h);
}
0%