BST很容易退化，例如在BST中一次插入一个有序序列，将会得到一条链，平均操作复杂度将为 $O(N)$。

树堆的概念

树堆（英语：Treap, Treap = Tree+Heap），是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。其基本操作的期望时间复杂度为O(\log{n})。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。（树堆-维基百科）

在实践过程中发现，以随机的顺序插入节点来构建一颗二叉查找树（普通的BST树）往往是趋紧平衡的。利用随机来创造平衡条件就是Treap的核心思想。在向Treap插入一个新节点的同时，都会为该节点生成一个随机的附加值。插入节点后的树堆通过旋转，不仅要满足二叉查找树的性质，也要满足大根堆的性质。

树堆的基本操作

插入

给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。

删除

因为Treap满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。

查找

查找过程和普通的二叉搜索树相同，可以分为通过值val查找其通过排序之后的位置rank，以及通过排序之后的位置rank查找值val。这时就需要在每个节点上维护一个表示以其为根的子树大小的变量size。

前驱

前驱和后继的查找同样与普通二叉树相同。在查找val的前驱时，前驱定义为在二叉树中小于val，且最大的数。下面分几种情况来讨论一下一个数val的前驱子在树的什么位置。为了简化边界情况，在构建二叉搜索树时，插入一个极大值（INF）和极小值（-INF）使得在算法实现的过程中，不用针对没有前驱后继的情况做特殊处理。

  1. 在二叉搜索树中，找到了值为val的节点，且该节点有左子树时。Val的前驱为该节点的左子树上最大的那个值。

  2. 在二叉搜索树中，找到了值为val的节点，但该节点没有左子树时。这个时候要考虑该节点是否是其父节点的右孩子。若是，则Val的前驱为该节点的父节点。否则，要递归的判断其父节点是否是其父节点的父节点的右孩子，直到找到该节点最近的一个是其父节点的右孩子的祖先。由于，我们在查找到值为val的节点时，会遍历过该节点的所有祖先。因此，该情况可以简化为Val的前驱是Val的所有值小于Val的祖先中值最大的那一个。

  3. 在二叉搜索树中，没有找到值为val的节点。假设我们要在该二叉搜索树中插入值为val的节点node。那么在这种情况下的搜索过程中。将会经过节点node的所有祖先。该情况下，查找Val的前驱方法与上一种情况相同。

后继

与查找前驱相同，现在只做简要概括。

  1. 在二叉搜索树中，找到了值为val的节点，且该节点有右子树时。Val的前驱为该节点的左子树上最小的那个节点。
  2. 否则，Val的前驱是Val的所有值大于Val的祖先中值最小的那一个。

代码与实践

现在通过题目普通平衡树来进行实践，以掌握Treap。

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

  1. 插入x数
  2. 删除x数(若有多个相同的数，因只删除一个)
  3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x，且最大的数)
  6. 求x的后继(后继定义为大于x，且最小的数)

输入描述:

1
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1 <= opt <= 6).

输出描述:

1
对于操作3,4,5,6每行输出一个数，表示对应答案

示例

输入

1
2
3
4
5
6
7
8
9
10
11
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

输出

1
2
3
106465
84185
492737

备注

  1. n 的数据范围: n <= 100000
  2. 每个数的数据范围: [-2e9, 2e9]

代码

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
236
237
238
239
240
241
242
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <tuple>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <cstring>
#include <cctype>
#include <iomanip>
#include <numeric>
#include <sstream>  // update
#include <bitset>   // update

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> int2;        //update
typedef tuple<int, int, int> int3;  //update

#define lg2(x) (log(x)/log(2))   // update

#define SIZE (100010)

struct Treap {
    int l, r;
    int val, dat;
    int cnt, size;
} a[SIZE];

int tot, root, INF = 0x7FFFFFFF;

int newNode(int val) {
    a[++tot].val = val;
    a[tot].dat = rand();
    a[tot].l   = a[tot].r    = 0;
    a[tot].cnt = a[tot].size = 1;
    return tot;
}

inline void updateNode(int p) {
    a[p].size = a[a[p].r].size + a[a[p].l].size + a[p].cnt;
}

void buildTreap() {
    tot = 0;
    srand((unsigned)time(NULL));
    newNode(-INF);  // 1
    newNode(INF);  // 2
    root = 1;
    a[1].r = 2;  // 有判断是否符合大根堆？
    updateNode(root);
}

// 右旋
void zip(int &p) {
    int q = a[p].l;
    a[p].l = a[q].r;
    a[q].r = p;
    p = q;
    updateNode(a[p].r);
    updateNode(p);
}

// 左旋
void zap(int &p) {
    int q = a[p].r;
    a[p].r = a[q].l;
    a[q].l = p;
    p = q;
    updateNode(a[p].l);
    updateNode(p);
}

void insert(int &p, int val) {
    if (p == 0) {
        p = newNode(val);
        return;
    }
    if (val == a[p].val) {
        a[p].cnt++;
        updateNode(p);
        return;
    }

    if (val < a[p].val) {
        insert(a[p].l, val);
        if (a[p].dat < a[a[p].l].dat)
            zip(p);  // 右旋
    } else {  // val > a[p].val
        insert(a[p].r, val);
        if (a[p].dat < a[a[p].r].dat)
            zap(p);  // 左旋
    }
    updateNode(p);
}

void remove(int &p, int val) {
    if (p == 0) return;
    if (val == a[p].val) {
        if (a[p].cnt > 1) {
            a[p].cnt--;
            updateNode(p);
            return;
        }

        if (a[p].r == 0 && a[p].l == 0) {
            p = 0;
        } else {  // 不是叶子节点
            if (a[p].r == 0 || a[a[p].r].dat < a[a[p].l].dat) {
                zip(p);
                remove(a[p].r, val);
            } else {
                zap(p);
                remove(a[p].l, val);
            }
        }
    } else {  // val != a[p].val
        if (val < a[p].val)
            remove(a[p].l, val);
        else
            remove(a[p].r, val);
    }
    updateNode(p);
}

int findRankOfVal(int p, int val) {
    if (p == 0) return 0;
    if (val < a[p].val) {
        return findRankOfVal(a[p].l, val);
    } else if (val > a[p].val) {
        return findRankOfVal(a[p].r, val) + a[p].cnt + a[a[p].l].size;
    }
    return a[a[p].l].size + 1;  // cnt == 1
}

int findValOfRank(int p, int rank) {
    if (p == 0) return 0;  // not found
    if (rank <= a[a[p].l].size)
        return findValOfRank(a[p].l, rank);
    else if (a[a[p].l].size + a[p].cnt < rank)
        return findValOfRank(a[p].r, rank - (a[a[p].l].size + a[p].cnt));
    return a[p].val;
}

int getPredecessor(int val) {
    int ans = 1;  // a[1].val = -INF
    int p = root;
    while (p) {
        if (val == a[p].val) {
            if (a[p].l > 0) {
                p = a[p].l;
                while (a[p].r > 0)
                    p = a[p].r;
                ans = p;
            }
            break;
        }
        if (a[p].val < val && a[p].val > a[ans].val)
            ans = p;

        p = (val < a[p].val? a[p].l: a[p].r);
    }
    return a[ans].val;
}

int getSuccessor(int val) {
    int ans = 2;  // a[2].val = INF
    int p = root;
    while (p) {
        if (val == a[p].val) {
            if (a[p].r > 0) {
                p = a[p].r;
                while (a[p].l > 0)
                    p = a[p].l;
                ans = p;
            }
            break;
        }
        if (a[p].val > val && a[p].val < a[ans].val)
            ans = p;
        p = (val < a[p].val? a[p].l: a[p].r);
    }
    return a[ans].val;
}

void inorderTraversal(int p) {
    if (p == 0) return;
    inorderTraversal(a[p].l);
    printf("%d ", a[p].val);
    inorderTraversal(a[p].r);
}

int main(int argc, const char * argv[]) {
    freopen("input.txt", "r", stdin);
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);

    int n, opt, x;
    scanf("%d", &n);
    buildTreap();

    while (n--) {
        scanf("%d%d", &opt, &x);
        switch (opt) {
        case 1:  // insert
            insert(root, x);
            break;
        case 2:  // delete
            remove(root, x);
            break;
        case 3:  // findRankOfVal
            printf("%d\n", findRankOfVal(root, x)-1);
            break;
        case 4:  // findValOfRank
            printf("%d\n", findValOfRank(root, x+1));
            break;
        case 5:  // getPredecessor
            printf("%d\n", getPredecessor(x));
            break;
        case 6:  // getSuccessor
            printf("%d\n", getSuccessor(x));
            break;

        default:
            break;
        }
    }

    return 0;
}