ITP2_7_A Set: Search

問題
Set: Search | Aizu Online Judge

AOJに新しいコースが追加されていました。ITP2(Introduction to Programming 2)ということなのですが、
「Hello,World」から始まるITP1とは違って結構難しいです。なかなか解き終わりません。
多くはC++に標準実装されてる？ものが題材になっているのですが、手間をかけてCで頑張っています。
今回の問題もその一つで集合に関する問題です。

union-findでもやったように、集合は木構造で管理すると良さそうです。
実際、C++で標準実装されてるSet:searchも内部処理的には二分木だそうです。
というわけで、二分木を実装したのですが、入力に偏りがあると綺麗な二分木にならず、アクセス効率が悪くなりTLEとなってしまいます。
これを解決するために、平衡二分木を実装しました。具体的には、前回の記事にしたTreapを利用してみました。
今回、優先度は乱数を使って自分で与えることにしました。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct node{
	int key;
	int priority;
	struct node *left;
	struct node *right;
}node;


int find(node *p,int x){

	while(p!=NULL){
		if(p->key == x)return 1;
		else if(p->key > x)p=p->left;
		else p=p->right;
	}
	
	return 0;
	
}


node * makenode(int x,int y){
	node *new=malloc(sizeof(node));
	new->key=x;
	new->priority=y;
	new->left=NULL;
	new->right=NULL;
	return new;
}

node *rightRotate(node *p){
	node *q=p->left;
	p->left=q->right;
	q->right=p;
	return q;
}

node *leftRotate(node *p){
	node *q=p->right;
	p->right=q->left;
	q->left=p;
	return q;
}


node* insert(node **t,int key,int priority){
	node *new;
	
	if((*t)==NULL)
		return new=makenode(key,priority);
	if ((*t)->key==key)
		return *t;
	
	if(key < (*t)->key){
		(*t)->left=insert(&(*t)->left,key,priority);
		if((*t)->priority < (*t)->left->priority)
			(*t)=rightRotate((*t));
	}
	else {
		(*t)->right=insert(&(*t)->right,key,priority);
		if((*t)->priority < (*t)->right->priority)
			(*t)=leftRotate((*t));
	}
	
	return *t;
}


int main(){
	int q,x,com;
	int num=0;
	node *root=NULL;
	srand((unsigned)time(NULL));
	
	scanf("%d",&q);
	
	for(int i=0;i<q;i++){
		scanf("%d %d",&com,&x);
		
		if(com==0){
			if(!find(root,x)){
				root=insert(&root,x,rand()%200001);
				num++;
			}
			printf("%d\n",num);
		}
		else {
			if(find(root,x))printf("1\n");
			else printf("0\n");
		}
		
	}
		
	return 0;
	
}

他の平衡二分木（AVL木）なども、いつか実装してみたいです。