简介

红黑树首先是二叉排序树，每个节点要么是红色要么是黑色，同时，红黑树满足下面四条性质：

  • 每个红色节点的儿子都一定是黑色节点
  • 每个黑色节点的儿子可以是红色也可以是黑色
  • 根节点是黑色节点
  • 从根节点出发到达每个叶子节点经过的黑色节点个数一样多

1

以上为一个红黑树的图例，你可以把空节点当作叶子节点，这样所有的叶子节点都是黑色节点

我们考虑从根到叶子节点的一条路径，黑色节点数是确定的，而红色节点数不会超过黑色节点数，所以从根到叶子节点的最长路径长度不会超过最短路径长度的两倍，所以红黑树是平衡的，现在考虑如何在插入和删除操作中维护以上性质

插入

设插入的节点为红色，如果是该节点为根节点，改为黑色即可，如果不是根节点，那么可能违背性质 $1$，要违背性质 $1$，该节点的父亲节点也一定是红色，设当前节点为 $u$，父亲节点为 $f$，祖父节点为 $ff$，父亲的兄弟节点为 $v$，那么 $ff$ 一定是黑色，$v$ 的颜色不确定，需要分类讨论

2

作图如上，$u$ 既可以是 $f$ 的左儿子也可以是 $f$ 的右儿子

一、$v$ 为红色

3

此时将 $ff$ 变为红色，$f$ 和 $v$ 变成黑色即可，但是此时 $ff$ 为红色，可能会与他的父亲节点冲突，所以需要递归向上检查更新

二、$v$ 为黑色

4

$u$ 为 $f$ 的右儿子时，将 $f$ 旋转到 $ff$ 的位置并交换颜色，结果为下图

5

$u$ 为 $f$ 的左儿子时，先将 $u$ 旋转到 $f$ 的位置，再将 $u$ 旋转到 $ff$ 的位置，最后交换 $u$ 和 $ff$ 的颜色，结果如下

6

删除

现在我们要删除 $val$ 为 $x$ 的节点，先找到 $val$ 为 $x$ 的节点，并找到他的后继节点 $next$，如果没有后继节点，就找他的前驱节点作为 $next$，然后交换当前节点和 $next$ 节点的 $val$，不交换颜色，然后在 $next$ 节点继续递归操作

假设现在递归到了最底层，即两个儿子都为空，如果当前节点是红色节点，直接删除即可，否则就要进行修正，修正的过程是从下往上的，假设当前的节点为 $u$ 并且以 $u$ 为根的子树已经满足红黑树的性质，而且当前节点为黑色节点，设 $f$ 为 $u$ 的父亲节点，$v$ 为 $u$ 的兄弟节点，$ls$ 和 $rs$ 分别为 $v$ 的左右儿子

一、$f$ 红，$v$ 黑，$ls$ 和 $rs$ 黑

7

设 $d[rt]$ 表示以 $rt$ 为根的子树中从 $rt$ 到叶子节点结果的黑色节点数目，显然，$d[u]+1=d[v]$，所以这里交换 $f$ 和 $v$ 节点的颜色即可

8

二、$f$ 黑，$v$ 黑，$ls$ 和 $rs$ 黑

11

此时，将 $v$ 染红即可，但是 $d[f]$ 相比于修改前会减少 $1$，所以要对 $f$ 进行修正

12

三、$f$ 黑，$v$ 红，$ls$ 和 $rs$ 黑

9

将 $v$ 旋转到 $f$ 的位置，交换 $v$ 和 $f$ 的颜色

10

此时 $u$ 变成了 $f$ 红色，兄弟节点黑色的情况，该情况放在后面进行讨论

四、$f$ 任意，$v$ 黑，$ls$ 任意，$rs$ 红

13

蓝色和紫色表示任意颜色，先将 $v$ 旋转到 $f$ 的位置

14

随后把 $v$ 置为 $f$ 的颜色，$f$ 和 $rs$ 置黑即可

15

五、$f$ 任意，$v$ 黑，$ls$ 红，$rs$ 黑

16

先将 $ls$ 置为 $f$ 的颜色，并将 $ls$ 旋转到 $v$ 的位置

17

最后将 $f$ 置黑，并且将 $ls$ 旋转到 $f$ 的位置

18

题目链接

「洛谷」P3369

完整代码

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
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
#include <bits/stdc++.h>
using namespace std;

const int INF = INT_MAX;
const int maxn = 1e5 + 5;

struct Tree {
    int cnt, root, col[maxn], val[maxn];
    int ch[maxn][2], size[maxn], fa[maxn];

    int node(int f, int x) {
        size[++cnt] = 1;
        val[cnt] = x;
        col[cnt] = 1;
        fa[cnt] = f;
        return cnt;
    }

    void pushup(int rt) { size[rt] = size[ch[rt][0]] + size[ch[rt][1]] + 1; }

    int dir(int u) { return ch[fa[u]][1] == u; }

    void connect(int u, int f, int d) {
        if (u) fa[u] = f;
        ch[f][d] = u;
    }

    void rotate(int u) {
        int f = fa[u], ff = fa[f], du = dir(u);
        if (!f) return;
        int df = dir(f);
        connect(u, ff, df), connect(ch[u][du ^ 1], f, du),
            connect(f, u, du ^ 1);
        pushup(f), pushup(u);
        if (f == root) root = u;
    }

    void check(int u) {
        if (!u || !col[u]) return;
        if (root == u) {
            col[u] ^= 1;
        } else if (col[fa[u]]) {
            int f = fa[u];
            int df = dir(f), ff = fa[f], du = dir(u), v = ch[ff][df ^ 1];
            if (col[v]) {
                col[f] = col[v] = 0;
                col[ff] = 1;
            } else {
                if (du == df) {
                    rotate(f);
                    col[ff] = 1, col[f] = 0;
                } else {
                    rotate(u);
                    rotate(u);
                    col[ff] = 1, col[u] = 0;
                }
            }
        }
    }

    int getred(int u, int d) {
        if (ch[u][d] && col[ch[u][d]])
            return d;
        else if (ch[u][d ^ 1] && col[ch[u][d ^ 1]])
            return d ^ 1;
        return -1;
    }

    void maintain(int u) {
        int f = fa[u];
        if (u == root) {
            root = 0;
            return;
        }
        int du = dir(u), v = ch[f][du ^ 1];
        ch[f][du] = 0;
        fa[u] = 0;
        while (true) {
            if (!v) return;
            if (!col[f] && col[v]) {
                swap(col[f], col[v]);
                rotate(v);
                v = ch[f][du ^ 1];
            } else if (!col[f] && !col[v] && getred(v, 0) == -1) {
                col[v] = 1;
                u = f;
                if (u == root) return;
                f = fa[u], du = dir(u), v = ch[f][du ^ 1];
            } else if (col[f] && !col[v] && getred(v, 0) == -1) {
                swap(col[f], col[v]);
                return;
            } else {
                int dv = dir(v);
                if (getred(v, dv) == dv) {
                    col[v] = col[f];
                    col[ch[v][dv]] = col[f] = 0;
                    rotate(v);
                } else {
                    col[ch[v][dv ^ 1]] = col[f];
                    col[f] = 0;
                    int son = ch[v][dv ^ 1];
                    rotate(son);
                    rotate(son);
                }
                return;
            }
        }
    }

    void insert(int &u, int f, int x) {
        if (!u) {
            u = node(f, x);
            check(u);
            return;
        }
        ++size[u];
        if (x >= val[u])
            insert(ch[u][1], u, x);
        else
            insert(ch[u][0], u, x);
        check(u);
    }

    int getnext(int u) {
        if (!ch[u][1]) {
            u = ch[u][0];
            if (!u) return 0;
            while (ch[u][1]) u = ch[u][1];
        } else {
            u = ch[u][1];
            while (ch[u][0]) u = ch[u][0];
        }
        return u;
    }

    void del(int &u, int x) {
        if (!u) return;
        size[u]--;
        if (val[u] == x) {
            int next = getnext(u);
            if (!next) {
                if (col[u]) {
                    ch[fa[u]][dir(u)] = 0;
                    fa[u] = 0;
                } else {
                    maintain(u);
                }
            } else {
                int v = next;
                while (fa[v] != u) {
                    v = fa[v];
                    size[v]--;
                }
                swap(val[u], val[next]);
                del(next, x);
            }
        } else if (x > val[u]) {
            del(ch[u][1], x);
        } else
            del(ch[u][0], x);
    }

    int rank(int x) {
        int u = root, ans = 0;
        while (u) {
            if (val[u] < x)
                ans += size[ch[u][0]] + 1, u = ch[u][1];
            else
                u = ch[u][0];
        }
        return ans + 1;
    }

    int find(int k) {
        int u = root;
        while (u) {
            if (size[ch[u][0]] + 1 >= k) {
                if (size[ch[u][0]] < k)
                    return val[u];
                else
                    u = ch[u][0];
            } else
                k -= size[ch[u][0]] + 1, u = ch[u][1];
        }
        return -1;
    }

    int pre(int x) {
        int u = root, ans = -INF;
        while (u) {
            if (val[u] < x && val[u] > ans) ans = val[u];
            if (val[u] < x)
                u = ch[u][1];
            else
                u = ch[u][0];
        }
        return ans;
    }

    int next(int x) {
        int u = root, ans = INF;
        while (u) {
            if (val[u] > x && val[u] < ans) ans = val[u];
            if (val[u] > x)
                u = ch[u][0];
            else
                u = ch[u][1];
        }
        return ans;
    }
} T;

void Main() {
    int n;
    cin >> n;
    for (int cas = 1; cas <= n; cas++) {
        int op, x;
        cin >> op >> x;
        if (op == 1) T.insert(T.root, 0, x);
        if (op == 2) T.del(T.root, x);
        if (op == 3) cout << T.rank(x) << '\n';
        if (op == 4) cout << T.find(x) << '\n';
        if (op == 5) cout << T.pre(x) << '\n';
        if (op == 6) cout << T.next(x) << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    Main();
    return 0;
}