引入
首先其实平衡树就是BST，即二叉查找树，然后尽量使这棵BST保持平衡。 我们知道BST容易退化，所以就有人发明了AVL树和红黑树，虽然这两种树的运行速度很快=_=，但是代码很复杂， 插入删除旋转情况有很多种，才保证了它的平衡，所以后来又出现了Treap这种平衡树。 虽然Treap比较简单，但是时间上却要稍稍差一点，而且有极小到几乎没有的可能（但是还是有）会退化，但显然在平时也已经够用了， 所以这里先来看看Treap。
数据结构的储存
首先因为这是一棵二叉查找树，所以每个节点必然要存两个儿子和它本身的值，然后在这个基础上，加上一个值，作为它的优先级，那么优先级有什么用，待会儿再说。
实现原理
通过题目可以知道，Treap就是Tree(BST)+Heap Heap就是堆，所以一棵Treap肯定首先满足了BST的性质，然后怎么满足Heap的性质呢 那么对于BST有一个简单的优化，就是将原来的数列随机打乱后插入。那么其实Treap的思路也差不多，是在插入一个点的时候，然后给它一个随机的优先级，然后通过旋转使它保持堆性质。那么为什么旋转能在保持BST性质下，修改出Heap性质呢。先来看图。 很显然地，就是根节点在左旋的时候，根节点变成了右节点的左结点（有点绕），然后把原来右节点的左子树变成它的右子树，然后这样很显然是会保持BST性质的，右旋则反过来。 所以其实不必硬记，第一是打多了就熟悉了，第二是这是可以现场推导的，如果硬记反而麻烦←_← 那么有了旋转来看插入，只需要将一个点按照BST的插入方法插入为根节点，然后再往根节点往回递归的过程中，不停旋转，将不满足堆性质的子树变成满足的子树，最终会让整棵树依旧保持堆性质。 删除其实同理，只是将插入操作反过来运行，也就是将要删除的点通过旋转转成叶子结点，除了这个点以外使这棵BST依旧保持堆性质，然后直接删掉。 具体操作可以看代码。 最后写出来的代码应该是和set一样都具有一样功能的，但是Treap能实现的作用远远不止，还需要看后面的练习。
代码
#include <ctime>
#include <cstdio>
#include <cstdlib>
struct Treap {
struct Node {
Node *ch[2];
int r;
int v;
int cmp(int x) const {
if(x == v) return -1;
return x < v ? 0 : 1;
}
} *root;
void rotate(Node* &o, int d) {
Node* k = o -> ch[d ^ 1];
o -> ch[d ^ 1] = k -> ch[d];
k -> ch[d] = o;
o = k;
}
void insert(Node* &o, int x) {
if(o == NULL) {
o = new Node();
o -> ch[0] = o -> ch[1] = NULL;
o -> v = x;
o -> r = rand();
} else {
int d = o -> cmp(x);
if(o -> ch[d], x);
if(o -> ch[d] -> r > o -> r) {
rotate(o, d ^ 1);
}
}
}
void remove(Node* &o, int x) {
int d = o -> cmp(x);
if(d == -1) {
if(o -> ch[0] == NULL) {
o = o -> ch[1];
} else {
if(o -> ch[1] == NULL) {
o = o -> ch[0];
} else {
int d2 = (o -> ch[0] -> r > o -> ch[1] -> r ? 1 : 0);
rotate(o, d2);
remove(o -> ch[d2], x);
}
}
} else {
remove(o -> ch[d], x);
}
}
int find(Node* o, int x) {
while(o != NULL) {
int d = o -> cmp(x);
if(d == -1) return 1;
else o = o -> ch[d];
}
return 0;
}
} treap;
int main(void) {
srand(time(0));
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i) {
int x;
scanf("%d", &x);
treap.insert(treap.root, x);
}
for(int i = 0; i < m; ++i) {
int a;
scanf("%d", &a);
int b;
if(a == 0) {
scanf("%d", &b);
treap.remove(treap.root, b);
} else {
scanf("%d", &b);
printf("%s\n", treap.find(treap.root, b) ? "existent" : "nonexistent");
}
}
return 0;
}
