BST (Binary Search Tree)

定义不必多说.

支持的操作

  1. 插入
  2. 删除
  3. 找 前驱/后继
  4. 找 最大/最小
  5. 求 某个值的排名
  6. 求 某个排名对应的值
  7. 比 某个数小的最大值
  8. 比 某个数大的最小值

其中 1 ~ 4 点在 STL set 中已经给出了实现, 5 ~ 8 点需要自己实现.

Treap (Tree + Heap)

目的: 使 BST 尽量随机, 从而保证平均复杂度为 .

做法: 给每个节点赋一个随机的val值, 使其同时满足 BST 和 大根堆的性质.

模板题: 253. 普通平衡树

代码实现

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
// Author: CodeBoy
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 100010, INF = 1e8;
int root, idx;
int n;
struct Node
{
    int l, r;
    int key, val;
    int cnt, size;
} tr[N];

// 更新该节点
void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

// 新建节点
int get_node(int key)
{
    tr[++idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

/*
旋转操作的含义：
    在不影响搜索树性质的前提下，把和旋转方向相反的子树变成根节点
    （如左旋，就是把右子树变成根节点）
    不影响性质，并且在旋转过后，跟旋转方向相同的子节点变成了原来的根节点
    （如左旋，旋转完之后的左子节点是旋转前的根节点）
*/

// 右旋
void zig(int &p)
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

// 左旋
void zag(int &p)
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}

// 建树
void build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);
    if (tr[1].val < tr[2].val)
        zag(root);
}

// 插入节点
void insert(int &p, int key)
{
    if (!p)
        p = get_node(key);
    else if (tr[p].key == key)
        tr[p].cnt++;
    else if (tr[p].key > key)
    {
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val)
            zig(p);
    }
    else
    {
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val)
            zag(p);
    }
    pushup(p);
}

// 删除节点
void remove(int &p, int key)
{
    if (!p)
        return;
    if (tr[p].key == key)
    {
        if (tr[p].cnt > 1)
            tr[p].cnt--;
        else if (tr[p].l || tr[p].r) // 有子树, 不能直接删除
        {
            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
            {
                zig(p);
                remove(tr[p].r, key);
            }
            else
            {
                zag(p);
                remove(tr[p].l, key);
            }
        }
        else
            p = 0;
    }
    else if (tr[p].key > key)
        remove(tr[p].l, key);
    else
        remove(tr[p].r, key);

    pushup(p);
}

int grbk(int p, int key)
{
    if (!p)
        return 0;
    if (tr[p].key == key)
        return tr[tr[p].l].size + 1;
    if (tr[p].key > key)
        return grbk(tr[p].l, key);
    return tr[tr[p].l].size + tr[p].cnt + grbk(tr[p].r, key);
}

int gkbr(int p, int rank)
{
    if (!p)
        return INF;
    if (tr[tr[p].l].size >= rank)
        return gkbr(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank)
        return tr[p].key;
    return gkbr(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key)
{
    if (!p)
        return -INF;
    if (tr[p].key >= key)
        return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key)
{
    if (!p)
        return INF;
    if (tr[p].key <= key)
        return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1)
            insert(root, x);
        else if (op == 2)
            remove(root, x);
        else if (op == 3)
            printf("%d\n", grbk(root, x) - 1);
        else if (op == 4)
            printf("%d\n", gkbr(root, x + 1));
        else if (op == 5)
            printf("%d\n", get_prev(root, x));
        else
            printf("%d\n", get_next(root, x));
    }
    return 0;
}