[数据结构与算法]平衡树（Treap）的基本操作

数组实现平衡树（支持插入，查询是否存在与删除操作）

#include<bits/stdc++.h>
using namespace std;
const int maxn=3*1e5+5;
struct edge{
	int ls,rs,fix,num;
};
struct node{
	edge tree[maxn];
	int root,len=0;
	node(){
		root=0;
	} 
	bool check(int now,int v)
	{
		if(now==0)return false; 
		if(tree[now].num==v)return true;
		if(tree[now].num<v)return check(tree[now].rs,v);
		if(tree[now].num>v)return check(tree[now].ls,v);
	}
	void turn_R(int &now)
	{
		int tmp=tree[now].ls;
		tree[now].ls=tree[tmp].rs;
		tree[tmp].rs=now;
		now=tmp;
	}
	void turn_L(int &now)
	{
		int tmp=tree[now].rs;
		tree[now].rs=tree[tmp].ls;
		tree[tmp].ls=now;
		now=tmp;
	}
	void insert(int &now,int v)
	{
		if(now==0){
			tree[++len]={0,0,rand(),v};
			now=len;
			return ;
		}
		else if(tree[now].num>=v){
			insert(tree[now].ls,v);
			if(tree[tree[now].ls].fix<tree[now].fix)
				turn_R(now);
		}
		else if(tree[now].num<v){
			insert(tree[now].rs,v);
			if(tree[tree[now].rs].fix<tree[now].fix)
				turn_L(now);
		}
	}
	void remove(int &now,int v)
	{
		if(now==0)return ;
		if(tree[now].num==v){
			if(tree[now].ls==0||tree[now].rs==0)
			{
				if(tree[now].rs)
					now=tree[now].rs;
				else now=tree[now].ls;
			}
			else if(tree[tree[now].ls].fix<tree[tree[now].rs].fix){
				turn_R(now);
				remove(tree[now].rs,v);
			}
			else {
				turn_L(now);
				remove(tree[now].ls,v);
			}
		}
		else if(tree[now].num<v){
			remove(tree[now].rs,v);
		}
		else if(tree[now].num>v){
			remove(tree[now].ls,v);
		}
	}
}T;
int n,x,y;
int main()
{
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&x,&y);
		if(x==1)T.insert(T.root,y);
		if(x==2)T.remove(T.root,y);
		if(x==3)printf("%d\n",T.check(T.root,y));
	}
	return 0;
}

（注意now与&now的区别）

指针实现（from ywq）

#include <cstdlib>
#include <cstdio>

int n;

struct NODE {
	int value, fix;
	NODE *left, *right;

	NODE(const int v){
		value = v;
		fix = rand();
		left = NULL;
		right = NULL;
	}
};

void rightRotate(NODE *&p) {
	NODE *tmp = p->left;
	p->left = tmp->right;
	tmp->right = p;

	p = tmp;
}

void leftRotate(NODE *&p) {
	NODE *tmp = p->right;
	p->right = tmp->left;
	tmp->left = p;

	p = tmp;
}

void insert(NODE *&p, const int value) {
	if (p == NULL) {
		p = new NODE(value);
	}
	else if (value <= p->value) {
		insert(p->left, value);
		if (p->left->fix < p->fix)
			rightRotate(p);
	}
	else {
		insert(p->right, value);
		if (p->right->fix < p->fix)
			leftRotate(p);
	}
}

int count(const NODE *p, const int value) {
	if (!p) return 0;
	if (p->value == value) return 1;

	if (value <= p->value)
		return count(p->left, value);
	else
		return count(p->right, value);
}

void remove(NODE *&p, const int value) {
	if (!p) return;
	if (p->value == value) {
		if (p->left == NULL || p->right == NULL) {
			NODE *tmp = p;
			if (p->right) p = p->right;
			else p = p->left;
			delete tmp;
		}
		else if (p->left->fix < p->right->fix) {
			rightRotate(p);
			remove(p->right, value);
		}
		else {
			leftRotate(p);
			remove(p->left, value);
		}
	}
	else if (value < p->value)
		remove(p->left, value);
	else
		remove(p->right, value);
}

NODE *root;

int main() {
	// srand(...);

	scanf("%d", &n);
	while (n --) {
		int opt, x;
		scanf("%d %d", &opt, &x);

		if (opt == 1) {
			insert(root, x);
		}
		else if (opt == 2) {
			remove(root, x);
		}
		else {
			printf("%d\n", count(root, x));
		}
	}

	return 0;
}