ALDS1_8_D Treap

問題
| アルゴリズムとデータ構造 | Aizu Online Judge

AOJのALDSに新しい問題が追加されていました。Treapを実装する問題です。
TreapとはTree+Heapということで、二分木とヒープの組み合わせです。考えた人すごいっすね。

自分で考えてもよく分からなかったので、問題の所に書いてあるアルゴリズムをそのまま実装しました。
今まで木の回転がよく分からなかったのですが、回転という言葉に惑わされず、「二分木の性質を保ちつつ親と子を交換する操作」と考えたらすんなり理解できました。

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

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


node * Delete(node **,int);
node * _delete(node **,int);

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;
	
}

void inorder(node *p){

	if(p->left!=NULL)inorder(p->left);
	
	printf(" %d",p->key);
	
	if(p->right!=NULL)inorder(p->right);
	
	return;
	
}

void preorder(node *p){
	
	printf(" %d",p->key);
	
	if(p->left!=NULL)preorder(p->left);
	
	if(p->right!=NULL)preorder(p->right);
	
	return;
	
}

void print(node *p){

	inorder(p);
	printf("\n");
	
	preorder(p);
	printf("\n");
	
	return;
	
}

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;
}


node * Delete(node **t,int key){
	if((*t)==NULL)
		return NULL;
		
	if(key < (*t)->key)
		(*t)->left=Delete(&((*t)->left),key);
		
	else if(key > (*t)->key)
		(*t)->right=Delete(&((*t)->right),key);
		
	else return _delete(t,key);
	
	return *t;
}

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


int main(){
	int n,x,y;
	char com[8];
	node *root=NULL;
	
	scanf("%d",&n);
	
	for(int i=0;i<n;i++){
		scanf("%s",com);
		
		switch(com[0]){
		
			case 'i':scanf("%d %d",&x,&y);
					 root=insert(&root,x,y);
					 break;
			
			case 'd':scanf("%d",&x);
					 root=Delete(&root,x);
					 break;
			
			
			case 'f':scanf("%d",&x);
					 if(find(root,x))printf("yes\n");
					 else printf("no\n");
					 break;

			case 'p':print(root);
					 break;
					 
		}
		
	}
	
	return 0;
	
}

これは自分で考え付くのは無理だなぁと思いました。