Data Structure Note(V) —— RB Tree

Posted on | In | Visitors:
Words count in article: 4.5k

prologue

　　这是数据结构大杂烩系列的第五篇文章(有生之年系列)。在前几篇文章中，我们学习了几种树结构，以及treap和splay两种平衡树。今天，我们将介绍一种应用十分广泛，且性能也十分优秀的平衡树——红黑树。不过由于网上资料较多，且笔者能力有限，这篇文章只是对算法导论中关于红黑树的知识的一些简单整理而已。

what is RB-Tree

　　首先，需要回答这样一个问题:为什么使用红黑树呢？答案其实是很简单的。因为红黑树的表现十分优秀！红黑树能够保证树不会退化成链表，导致效率的急剧下降。简单来说，红黑树是一颗特殊的二叉搜索树，它在每个节点上增加了一个存储位来表示节点的颜色(红或黑)。并且，由于这一个特性，红黑树中到叶子节点的简单路径中，不会有一条路径长度是其他路径的两倍。
　　红黑树满足以下性质:

  1. 每个结点是黑色或者红色
  2. 根节点是黑色
  3. 每个叶子结点是黑色的(NIL)
  4. 如果一个结点是红色的，那么它的两个子结点都是黑色的
  5. 对每个结点，该结点到所有后代叶结点的简单路径上均包含相同数目的黑色结点

　　一颗合法的红黑树:
red-black tree
　　同时，红黑树中有一种特殊的节点是NIL，起到相当与空结点的作用，但可以减少一些边界判断(其实就是哨兵)。另外，由于红黑树的性质5，我们可以定义红黑树的黑高bh，定义为该结点到所有叶结点的路径上黑色结点的数量。
　　此时，我们可以证明，一颗有n个内部结点(即不含NIL)的红黑树高度至多为\(\,2log(n+1)\)
　　证明: 先证任一结点为根的子树中至少包含\(\,2^{bh(x)}-1\)个内部结点。可以用数学归纳法证明。又由于根到任意叶子结点的任何一条路径上都至少有一半的结点为黑色(性质4)，因此有\(n >= 2^{h/2}-1\)，整理得，\(h<=2log(n+1)\)
　　我们接下来可以知道，红黑树上的插入，删除等操作的运行时间均为O(h)，因此我们可以得到这些操作的时间都是O(logn)
　　这篇文章接下来将以洛谷P3369为例子，讲讲如何简单地实现红黑树。我们将实现以下操作:

  1. 插入数字x
  2. 删除数字x
  3. 查询数字x的排名
  4. 查询排名为x的数字
  5. 求x的前驱(比x小的数字中最大的那个)
  6. 求x的后继(比x大的数字中最小的那个)

　　以下是红黑树的结点的定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define RED 0
#define BLACK 1
#define T Node*
struct Node {
    T fa;
    T lson;
    T rson;
    // 需要维护的数据: 键值v，子树大小siz，该结点的次数cnt，颜色color
    int v, siz, cnt;
    bool color;
    // 构造函数
    Node(int v, int siz = 1, int cnt = 1, int color = RED):
        v(v),siz(siz),cnt(cnt),color(color){}
    // up操作
    void up() {
        // 注意我们需要保证空结点NIL的size为0，否则会出问题
        if (cnt == 0) return;
        siz = lson->siz + rson->siz + cnt;
    }
};

how to implement Red-black Tree

rotation

　　我们知道，插入，删除等操作有可能会违背红黑树的红黑特性，因此我们需要一种操作来维持红黑树的特性不被改变，这就是旋转操作。和treap类似却又不太一样:红黑树的旋转同样分为左旋和右旋，但左旋是将当前节点旋转到左儿子的位置，右旋同理。具体操作如下:

rotation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 这里展示左旋的写法，右旋和左旋写法对称
void rotL(T x) {
    // partI 连接x和y的左儿子
    T y = x->rson;
    x->rson = y->lson;
    if (y->lson != nil) {
        y->lson->fa = x;
    }
    // partII y和x的父亲
    y->fa = x->fa;
    if (x->fa == nil) {
        rt = y;
    } else if (x->fa->lson == x) {
        x->fa->lson = y;
    } else {
        x->fa->rson = y;
    }
    // partIII 连接x和y
    x->fa = y;
    y->lson = x;
    // 最后别忘了up操作。注意x和y的先后顺序
    x->up();y->up();
}

insert

　　我们先考虑普通的BST的情况。这种情形下，我们只需要找到一个可以插入数字v的节点即可。如果找到了，我们就直接将该结点的次数+1即可。如果找不到，我们就重新new一个结点。考虑到我们需要维护子树的大小，我们可以在查找的时候顺便更新一下查找路径上所有结点的siz。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(int v) {
    T cur = root;
    while (cur != NIL) {
        cur->siz++;
        if (v < cur->v) {
            cur = cur->lson;
        } else if (v > cur->v) {
            cur = cur->rson;
        } else {
            // 找到了，直接次数+1后返回
            cur->cnt++;
            return;
        }
    }
    // 找不到时，重新new一个结点
    cur = new Node(v);
    // 这里需要连接结点cur和父结点，并将左右儿子指向NIL
    ...
}

　　写到这里，又会有一个问题，新结点的颜色呢？为了满足红黑树的性质，新的节点只能是红色或者黑色。如果我们将新的结点设置为黑色的话，会发生什么情况？性质5会被破坏，如果我们想修复性质5，处理起来是很麻烦的。因此我们选择将新的结点设置为红色。这个时候，性质2，性质4有可能被破坏。修复性质2的话其实很简单，我们只需要将根节点设置为黑色就可以了(根节点的颜色不影响黑高bh)。修复性质4的话，我们需要分类讨论。我们在insert方法的最后，调用insert-fixed方法，维护红黑树的特性。
　　当插入节点的父结点为红色时，违背了性质4，这个时候我们需要通过旋转和重新染色来进行修复。首先，如果当前结点的父亲是黑色的话，那么不违背红黑树的性质，直接退出即可。否则，假设当前结点的父亲是祖先的左儿子，这时分三种情况讨论。(注意到父亲结点为红色时，祖先结点必然存在，因为根节点是黑色的)
insert
　　情况1中，当前结点的叔叔结点为红色，这个时候我们可以将当前结点的父亲和叔叔染成黑色，将祖先染成红色，这个时候各个叶子结点的黑高并没有发生改变，故解决了问题。但是将祖先结点染成红色有可能会导致破坏了性质4，因此将x赋值为祖先结点，继续循环。
　　情况2中，叔叔结点为黑色，当前结点是父亲的右儿子。这个时候我们将x赋值为其父亲结点，同时对父亲结点进行左旋操作，就进入了情况3。
　　情况3中，叔叔节点为黑色，当前结点是父亲的左儿子，这个时候将父亲结点染成黑色，祖先结点染成红色，并对祖先结点进行一次右旋，然后我们就发现，红黑树的性质得到了维护，循环可以退出了。注意到右旋时，由于父亲结点是红色，因此兄弟结点一定是黑色，对祖先结点右旋后两个儿子都是黑色的，因此没有破坏性质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
void insert_fixed(T x) {
    while (x->fa->color == RED) {
        if (x->fa == x->fa->fa->lson) {
            T y = x->fa->fa->rson;
            // 情况1: 叔叔结点为红色
            if (y->color == RED) {
                y->color = x->fa->color = BLACK;
                x->fa->fa->color = RED;
                x = x->fa->fa;
            }
            // 情况2: 叔叔结点为黑色，且当前结点是父亲的右儿子
            else if (x == x->fa->rson) {
                x = x->fa;
                rotL(x);
            }
            // 情况3: 叔叔结点为黑色，且当前节点是父亲的左儿子
            else {
                x->fa->color = BLACK;
                x->fa->fa->color = RED;
                rotR(x->fa->fa);
            }
        }
        else {
            // 这里的写法和之前是对称的
            ...
        }
    }
    // 别忘了把根节点设置为黑色
    rt->color = BLACK;
}

remove

　　删除操作应该是最繁琐的一项了。同样的，我们先考虑普通的BST的情况。这种情形下，我们只需要找到需要删除的点的位置即可，并将该结点的次数-1，如果次数大于0，我们则可以直接返回，次数等于0时，则说明当前结点需要被移除。同样的，由于我们需要维护子树的大小，我们可以在查找的时候顺便更新一下查找路径上所有结点的siz。
　　那么该如何移除呢？在BST中，我们的做法是找出结点v的后继y，用y来替换结点v的位置(y的颜色也变成v的颜色)，同时，我们把y的右儿子提到y的位置(注意到y没有左儿子，因为它是v的后继，即v的右子树中最小的值)，这样我们就成功地将原先结点移除了。但是，由于y结点被x结点替换了，有可能会导致红黑树的特性被破坏，这里我们需要记录y原来的颜色，以便于我们的恢复操作。操作过后，对于整棵树来说，相当于少了一个y结点。如果y是红色，那么红黑树的性质并没有被破坏，直接返回即可。如果y是黑色，y节点(即当前x的位置)的所有子结点的黑高小了1，违背了性质5，同时也有可能违背了性质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
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
// 连接v结点和u结点的父亲
void transplant(T u, T v) {
    if (u->fa == nil) rt = v;
    else if (u == u->fa->lson) {
        u->fa->lson = v;
    } else {
        u->fa->rson = v;
    }
    v->fa = u->fa;
}

void remove(int v) {
    T cur = rt;
    // 获取值v对应的结点的指针
    while (cur != nil) {
        cur->siz--;
        if (v < cur->v) cur = cur->lson;
        else if (v > cur->v) cur = cur->rson;
        else {
            cur->cnt--;
            break;
        }
    }
    // 大于0直接返回
    if (cur->cnt > 0) return;
    T y = cur;
    T x;
    bool originColor = y->color;
    // 左儿子或右儿子是空的，直接替换即可
    if (cur->lson == nil) {
        x = cur->rson;
        transplant(cur, x);
    } else if (cur->rson == nil) {
        x = cur->lson;
        transplant(cur, x);
    }
    // 左右儿子都非空，我们需要用y的后继来替换当前结点
    else {
        // 获得当前结点cur的后继及其颜色
        y = cur->rson;
        while (y->lson != nil) y = y->lson;
        originColor = y->color;
        // y的右结点替换y
        x = y->rson;
        // y如果是cur的子结点，那么x父亲应该指向y，注意到x也可以是NIL
        // 否则应该用x替换y，y替换cur
        if (y->fa == cur) {
            x->fa = y;
        } else {
            transplant(y, x);
            y->rson = cur->rson;
            cur->rson->fa = y;
        }
        transplant(cur, y);
        y->lson = cur->lson;
        y->lson->fa = y;
        y->color = cur->color;
        // 从初始的y的位置到cur的位置上的所有结点的siz需要更新
        T c = x;
        while (c != y) {
            c = c->fa;
            c->up();
        }
    }
    delete cur;
    if (originColor == BLACK) remove_fixed(x);
}

　　假设结点y的初始颜色是黑色，那么我们应该如何修复呢？我们可以这样考虑:结点y删除后，y的黑色由x来继承，这样x就相当于是一个具有双重颜色的结点”红黑或者黑黑”，这样，性质5就没有被破坏，但有可能破坏了性质1，2，和4。我们需要做的其实就是把其中的一重颜色去掉。
　　首先，如果x是红黑结点时，那么我们可以把它直接变成黑色结点。这种情况下所有性质都得到了维护。另外，如果x是根结点时，无论x是红黑结点或者是黑黑结点，我们都只需要直接把它变成黑色即可。因此，我们需要考虑的就是x是双黑结点且不是根节点的情况。类似的，我们假设当前结点是父亲的左儿子。这时，分四种情况讨论。
remove
　　对于情况1，其兄弟结点是红色，这个时候我们可以将兄弟结点变成黑色，并把父亲结点变成红色，再对父亲结点进行左旋，这个时候，我们发现得到的新的树中，x的兄弟结点就变成了黑色，转化为情况2～4
　　对于情况2，其兄弟结点和兄弟结点的左右儿子都是黑色，那么我们可以把兄弟结点变成红色，并把x的父亲赋值给x，这样，我们就相当与将x的其中一重黑色移动到了它的父亲结点上。
　　对于情况3，兄弟结点是黑色，兄弟节点的右儿子是黑色，左儿子是红色。这个时候我们将兄弟结点变成红色，兄弟结点的左儿子变成黑色，并对兄弟结点进行右旋操作，转化为情况4
　　对于情况4，兄弟节点是黑色，且兄弟结点右儿子是红色，交换父亲结点和兄弟结点的颜色，并把兄弟节点的右儿子染成黑色，再将父亲结点进行左旋，这个时候我们就相当于把黑色转移到了父亲结点上，可以直接退出循环。
　　在这4中情况下，由于情况1会转为2~4，情况3会转为情况4，并且情况4可以直接完成旋转和染色，情况2每次迭代高度都会减少1，因此最后的复杂度为O(logn)。这样，我们就完成了修复函数的一半
　　类似的，当前结点是父亲的右儿子时，操作完全一样，只要左儿子变成右儿子，左旋变成右旋对称地处理即可。代码见下方:

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
void remove_fixed(T x) {
    // 到达根节点或者当前结点是红色时，退出循环
    while (x != rt && x->color == BLACK) {
        if (x == x->fa->lson) {
            T w = x->fa->rson;
            // 情况1
            if (w->color == RED) {
                w->color = BLACK;
                x->fa->color = RED;
                rotL(x->fa);
                w = x->fa->rson;
            }
            // 情况2
            if (w->lson->color == BLACK && w->rson->color == BLACK) {
                w->color = RED;
                x = x->fa;
            }
            // 情况3
            else if (w->rson->color == BLACK) {
                w->lson->color = BLACK;
                w->color = RED;
                rotR(w);
                w = x->fa->rson;
            }
            // 情况4
            else {
                w->color = x->fa->color;
                x->fa->color = BLACK;
                w->rson->color = BLACK;
                rotL(x->fa);
                // 把x赋值为根节点，就可以直接退出循环
                x = rt;
            }
        } else {
            // 这里对称地处理即可
            ...
        }
    }
    // 别忘了把根节点变成黑色
    x->color = BLACK;
}

other operation

　　为了完成题目，我们还需要实现rank,search,pre,next等函数，这里写法其实和普通的平衡树没有任何区别，不过这里还是简单提一下吧。具体的代码就不贴了。

  1. rank函数，查找某一个数字的排名。我们沿着树遍历，若当前节点的值大于我们要找的数字，说明这个数字在左边，往左子树走。若当前结点的值等于我们要找的数字，说明左子树上所有节点都小于我们要找的数字，因此返回累计值加上左子树的大小再+1。若当前结点的值小于我们要找的数字，则累计值应该加上当前结点的次数和左子树的大小，并且往右子树方向找。
  2. search函数，查找排名为x的数字的值。如果左子树的大小大于当前要找的排名，往左找。如果左子树加上当前的结点的次数小于要找的排名，往右找，同时排名减去左子树和当前结点次数。否则说明排名为x的数字刚好就是当前结点对应的值
  3. pre函数，查找前驱。我们知道，前驱比当前结点小，故应该在结点的左子树当中，且是左子树中最大的那个。因此，我们只要找左子树中最大的值即可。找最大值的话就只需要不断地试着往右儿子移动，当右儿子为空时，当前结点就是最大值
  4. next函数，查找后继。同样的，我们只需要查找右子树中最小的值即可。只需要在右子树中不断往左儿子方向走，左儿子为空时即为后继。

epilogue

　　红黑树这一期到这里应该就结束了，这一期主要还是作为笔记，以加深自己的印象。红黑树整体来说应该不能算是很难的一种数据结构，但它的分类很多，很繁琐而且并不好记，因此给人一种望而生畏的感觉。红黑树最大的难点应该还是在插入和删除时对红黑树特性的维护那个部分，这个可能只能强行背一下了，似乎也没有什么更好的记忆办法。作为一名喜欢算法与数据结构的程序员，红黑树是不得不掌握的。

------------- The artical is over Thanks for your reading -------------