RBT(红黑树)的相关操作及代码

发表于 | 分类于 | 阅读次数: |
字数统计: 3.1k | 阅读时长 ≈ 13

红黑树（RBT）

红黑树也是一种平衡二叉排序树。

五个条件(性质)

  1. 每个节点非黑即红；

  2. 根节点一定为黑；

  3. 叶节点(NIL，用来替代原有空指针的节点)一定为黑；

  4. 红色节点的左右两个子节点一定为黑；
  5. 从根节点出发到所有叶节点的路径上，每条路径的黑色节点数量相同。

    可由性质4和5得到：

    红黑树中从根节点出发到所有叶子节点最长路径和最短路径的长度关系是最长路径是最短路径的二倍

    简单证明：

    由红黑树性质可得知，最短的路径一定全由黑色节点组成，而最长的路径则是穿插着红色节点，在这两条路径中黑色节点数量相等，所以最长路径的长度是最短路径的二倍

AVL树是通过树高控制平衡，而红黑树的本质也是通过控制树高来控制平衡，不过红黑树的树高范围更松散一些(长边是短边的二倍)。

调整策略

  1. 插入调整站在祖父节点看，若站在祖父节点向下看两层失衡了，则进行调整(解决两个红色节点相连的情况，因为两个红色节点相连会打破第4个条件)
  2. 删除调整站在父节点看，若站在父节点向下看一层失衡了，则进行调整(类比二叉排序树的删除)
  3. 插入和删除的情况处理一共5种

插入调整

往一个红黑树中插入黑色节点对整体的影响大于插入红色节点对整体的影响，因为无论往哪一条路径插入黑色节点，都会导致这条路径上的黑色节点数目增加1，就可能打破条件5，即从根节点出发到所有的叶节点，黑色节点的数目相等。

所以在红黑树的插入操作中，为了防止打破条件5，我们选择新插入的节点颜色为红色，而不是黑色。

在新插入的节点为红色的情况下，只有一种情况可能会导致失衡：即插入节点的颜色为红色，其父节点也是红色(打破了条件4)。

当需要进行插入调整的时候，祖父节点一定是黑色，由第4条性质可知，产生冲突的x节点的父节点一定是红色，所以x节点的祖父节点一定不是红色，若祖父节点是红色，那么x的父节点一定是黑色，所以不会导致冲突，与之前产生冲突的x节点产生了矛盾。

红色下沉

RBT-红色下沉

红色上浮

RBT-红色上浮

在红黑树的第5个条件中，这两个条件是等价的。

情况一(uncle为红色)

如下图所示：

RBT-插入调整情况一

注：框住的节点为颜色确定的节点。

此时如何解决冲突？

解决方案：利用红色上浮解决此问题

将作为父节点的20号红色节点和作为uncle节点的1号红色节点改为黑色，将作为祖父节点的15号黑色节点改为红色即可解决冲突。

延伸情况(4种)

以此延伸出4种情况，如下图所示，均可统一用红色上浮解决此问题。

RBT-插入调整情况一延伸情况

即只要产生冲突的x节点的uncle节点为红色，不管x的位置如何，均可采用红色上浮来解决冲突。

情况二(uncle为黑色)

RBT-插入调整情况二

此时如何解决冲突？

解决方案：将其绕祖父节点进行大右旋

将情况二进行大右旋后：

插入调整情况二右旋后

解决方案：利用红色下沉将20号黑色节点改为红色节点，将15号红色节点改为黑色节点，或者利用红色上浮将10号节点改为黑色，这两种策略都可以使得两边的黑色节点数量相等。

延伸情况(4种)

插入调整情况二延伸情况

解决方案：

对于LL型将其绕着x节点的祖父节点进行大右旋，再对其利用红色下沉或者红色上浮即可解决冲突(即情况二所示)

对于RR型将其绕着x节点的祖父节点进行大左旋，在对其利用红色下沉或者红色上浮即可解决冲突(与LL型类似)

插入调整情况二延伸情况2

解决方案：

对于LR型，类比AVL树的LR型调整，将x的祖父节点的左子树进行小左旋，转换成LL型(即情况二所示)，再对其进行大右旋后，利用红色下沉或者红色上浮即可解决冲突

对于RL型，类比AVL树的RL型调整，将x的祖父节点的右子树进行小右旋，转换成RR型，再对其进行大左旋后，利用红色下沉或者红色上浮即可解决冲突

删除调整

类比于二叉排序树的删除：

若删除度为0、1、2的红色节点，对红黑树无影响，不会影响其平衡，因为第5个条件主要说的是黑色节点数量，而不是红色节点数量。

但若是删除黑色节点，无论度为几，则对红黑树有影响，主要影响了第5个条件。

双重黑

当产生双重黑时，就要进行调整操作，删除调整主要去掉双重黑。

情况一(brother为黑色)

RBT-删除调整情况一

情况描述：

x是双重黑，x的brother节点也是黑色，其两个孩子也同时为黑色

解决方案：

由于要处理掉双重黑，所以要使得x节点从双重黑变为单黑，就要使得43号节点的左子树黑色节点数目减少一，为了处理这种情况，使x变为单黑，43号节点加一重黑色，43号节点的左子树减少一重黑色，即9号兄弟节点由单黑变为红色节点，即可解决这个问题。由于43号节点颜色不确定，但是没关系，若43号节点本身为单黑，加一重黑色变为双黑，在之后回溯的过程中仍然会调整；若43号节点本身为红色，加一重黑色则变为单黑节点，仍然无冲突。

好处：

这样做的好处在于可以使得双重黑逐渐向上浮，浮到根节点时即可直接使双重黑消失。

情况二(brother为黑色，RL型)

删除调整情况二

情况描述：

此为RL型，x双重黑节点的兄弟节点在父节点右部，兄弟节点左部有一个红色节点

解决方案：

先将其绕着兄弟节点进行右旋，得到如下所示的图

删除调整情况二右旋后

解决方案：

将51节点改为黑色，将72节点变为红色，放大到全图看变回了RR型，即可转为情况三的RR型进行处理。

延伸情况(LR型)

解决方案类似于RL型，出现LR型情况时，将其绕着兄弟节点进行左旋，转换成情况三的LL型进行处理。

情况三(brother为黑色，RR型)

删除调整情况三

情况描述：

此为RR型，x双重黑节点的兄弟节点在x父节点右部，而兄弟节点的右部有一个红色节点

解决方案：

将其围绕着x节点的父节点进行右旋，得到如下所示的图

删除调整情况三左旋后

解决方案：

由于48号节点颜色不确定，为了防止两个红色的冲突，38号节点一定要改成黑色，这个时候将72改成黑色，51改成红色即可防止冲突。

但若38本身是黑色，则将51也改成黑色即可。

总结如下：

出现RR型情况时，将其绕着父节点进行左旋，将左旋后的根节点的两个子节点改为黑色，将左旋后的根节点颜色改为原有根节点的颜色即可。

延伸情况(LL型)

解决方案类似于RR型，出现LL型情况时，将其绕着父节点进行右旋，将右旋后的根节点的两个子节点改为黑色，将右旋后的根节点颜色改为原有根节点的颜色即可。

延伸情况(brother为红色，2种)

注：若brother节点在x节点左部则进行右旋，若在右部则进行左旋

删除调整延伸情况

情况描述：

此时作为双重黑的x节点的兄弟节点为红色

解决方案：

将其绕着父节点进行右旋，得到如下所示的图

删除调整延伸情况右旋后

解决方案：

将颜色更改为如下图所示，得到新的brother节点，此时brother节点为黑色

删除调整延伸情况颜色更改

解决方案：

最终转换成删除调整的情况一、二、三进行解决。

代码

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdlib>

#define RED 0
#define BLACK 1
#define DOUBLE_BLACK 2

using namespace std;

typedef struct Node {
    int key, color; // 0 red, 1 black, 2 double black
    struct Node *lchild, *rchild;
} Node;

Node _NIL, * const NIL = &_NIL;

__attribute__((constructor))
void init_NIL() {
    NIL->key = 0;
    NIL->lchild = NIL->rchild = NIL;
    NIL->color = BLACK;
    return ;
}

Node *getNewNode(int key) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->key = key;
    p->lchild = p->rchild = NIL;
    p->color = RED;
    return p;
}

int hasRedChild(Node *root) {
    return root->lchild->color == RED || root->rchild->color == RED;
}

Node *left_rotate(Node *root) {
    Node *temp = root->rchild;
    root->rchild = temp->lchild;
    temp->lchild = root;
    return temp;
}

Node *right_rotate(Node *root) {
    Node *temp = root->lchild;
    root->lchild = temp->rchild;
    temp->rchild = root;
    return temp;
} 


Node *insert_maintain(Node *root) {
    if (!hasRedChild(root)) return root;
    if (root->lchild->color == RED && root->rchild->color == RED) {
        if (!hasRedChild(root->lchild) && !hasRedChild(root->rchild)) return root;
        goto insert_end;
    }
    if (root->lchild->color == RED) {
        if (!hasRedChild(root->lchild)) return root;
        if (root->lchild->rchild->color == RED) {
            root->lchild = left_rotate(root->lchild);
        }
        root = right_rotate(root);
    } else {
        if (!hasRedChild(root->rchild)) return root;
        if (root->rchild->lchild->color == RED) {
            root->rchild = right_rotate(root->rchild);
        }
        root = left_rotate(root);
    }
insert_end:
    root->color = RED;
    root->lchild->color = root->rchild->color = BLACK;
    return root;
}

Node *__insert(Node *root, int key) {
    if (root == NIL) return getNewNode(key);
    if (root->key == key) return root;
    if (root->key > key) root->lchild = __insert(root->lchild, key);
    else root->rchild = __insert(root->rchild, key);
    return insert_maintain(root);
}

Node *insert(Node *root, int key) {
    root = __insert(root, key);
    root->color = BLACK;
    return root;
}

Node *predeccessor(Node *root) {
    Node *temp = root->lchild;
    while (temp->rchild != NIL) temp = temp->rchild;
    return temp;
}

Node *erase_maintain(Node *root) {
    if (root->lchild->color != DOUBLE_BLACK && root->rchild->color != DOUBLE_BLACK) return root;
    if (root->rchild->color == DOUBLE_BLACK) {
        if (root->lchild->color == RED) {
            root->color = RED;
            root->lchild->color = BLACK;
            root = right_rotate(root);
            root->rchild = erase_maintain(root->rchild);
            return root;
        }
        if (!hasRedChild(root->lchild)) {
            root->color += 1;
            root->lchild->color -= 1;
            root->rchild->color -= 1;
            return root;
        }
        if (root->lchild->lchild->color != RED) {
            root->lchild->rchild->color = BLACK;
            root->lchild->color = RED;
            root->lchild = left_rotate(root->lchild);
        }
        root->lchild->color = root->color;
        root->rchild->color -= 1;
        root = right_rotate(root);
        root->lchild->color = root->rchild->color = BLACK;
    } else {
        if (root->rchild->color == RED) {
            root->color = RED;
            root->rchild->color = BLACK;
            root = left_rotate(root);
            root->lchild = erase_maintain(root->lchild);
            return root;
        }
        if (!hasRedChild(root->rchild)) {
            root->color += 1;
            root->lchild->color -= 1;
            root->rchild->color -= 1;
            return root;
        }
        if (root->rchild->rchild->color != RED) {
            root->rchild->lchild->color = BLACK;
            root->rchild->color = RED;
            root->rchild = right_rotate(root->rchild);
        }
        root->rchild->color = root->color;
        root->lchild->color -= 1;
        root = left_rotate(root);
        root->lchild->color = root->rchild->color = BLACK;
    }
    return root; 
}

Node *__erase(Node *root, int key) {
    if (root == NIL) return root;
    if (root->key > key) {
        root->lchild = __erase(root->lchild, key);
    } else if (root->key < key) {
        root->rchild = __erase(root->rchild, key);
    } else {
        //处理度为0或1的黑色节点
        if (root->lchild == NIL || root->rchild == NIL) {
            Node *temp = root->lchild == NIL ? root->rchild : root->lchild;
            temp->color += root->color;
            free(root);
            return temp;
        } else {
            //处理度为2
            Node *temp = predeccessor(root);
            root->key = temp->key;
            root->lchild = __erase(root->lchild, temp->key);
        }
    }
    return erase_maintain(root);
}

Node *erase(Node *root, int key) {
    root = __erase(root, key);
    root->color = BLACK;
    return root;
}

void clear(Node *root) {
    if (root == NULL) return ;
    clear(root->lchild);
    clear(root->rchild);
    return ;
}

void output(Node *root) {
    if (root == NIL) return ; 
    printf("%d [%d, %d] %s\n", 
        root->key,
        root->lchild->key,
        root->rchild->key,
        root->color ? "BLACK" : "RED"
    );
    output(root->lchild);
    output(root->rchild);
    return ;
}

int main() {
    int op, val;
    Node *root = NIL;
    while (scanf("%d%d", &op, &val) != EOF) {
        switch (op) {
            case 1: root = insert(root, val); break;
            case 2: root = erase(root, val); break;
        }
        output(root);
    }
    return 0;
}