#include"iostream"
#include"cstring"

using namespace std;

struct NOD
{
	char *data;
	int priority;		
	NOD *left,*right;
	NOD()
	{
		data=0;
		priority=0;
		left=0;
		right=0;
	}
	NOD(char *data,int priority)
	{
		this->data=new char[strlen(data)+1];
		strcpy(this->data,data);
		this->priority=priority;
		left=0;
		right=0;
	}
};

bool cmp(NOD *r,NOD *l)
{
	if(l==0)
		return r==0;
	else
		return r==0 || r->priority>l->priority;
}

class Treap
{
public:
	NOD *root;
	Treap(){root=0;};
	void Insert(NOD* &nod,NOD *ins);
	void Delete(NOD* &nod,char* del);
	void LL(NOD* &nod);
	void RR(NOD* &nod);
	NOD * Find(NOD* &root,char* x);
};

void Treap::Insert(NOD* &nod,NOD *ins)
{
	if(nod==0)
		nod=ins;
	else
	{
		if(strcmp(nod->data,ins->data)<0)
		{
			Insert(nod->right,ins);
			if(cmp(nod->right,nod))
				this->LL(nod);
		}
		else
			if(strcmp(nod->data,ins->data)>0)
			{
				Insert(nod->left,ins);
				if(cmp(nod->left,nod))
					this->RR(nod);
			}
	}
}

void Treap::Delete(NOD* &nod,char* del)
{
	if(nod==0)
		return;
	if(strcmp(nod->data,del)>0)
	{
		this->Delete(nod->left,del);
	}
	else
		if(strcmp(nod->data,del)<0)
		{
			this->Delete(nod->right,del);
		}
		else
		{
			if(nod->left==0 && nod->right==0)
			{
				delete nod;
				nod=0;
			}
			else
				if(cmp(nod->left,nod->right))
				{
					this->RR(nod);
					this->Delete(nod->right,del);
				}
				else
				{
					this->LL(nod);
					this->Delete(nod->left,del);
				}
		}
}

void Treap::LL(NOD* &nod)
{
	NOD *temp=nod->right;
	nod->right=temp->left;
	temp->left=nod;
	nod=temp;
}

void Treap::RR(NOD* &nod)
{
	NOD *temp=nod->left;
	nod->left=temp->right;
	temp->right=nod;
	nod=temp;
}

NOD* Treap::Find(NOD* &root,char* x)
{
	if(root==0)
		return 0;
	if(strcmp(root->data,x)==0)
		return root;
	else
		if(strcmp(root->data,x)>0)
			return Find(root->left,x);
		else
			return Find(root->right,x);
}

void print(NOD * nod)
{
	if(nod==0)
		return;
	printf("(");
	print(nod->left);
	printf("%s/%d",nod->data,nod->priority);
	print(nod->right);
	printf(")");
}

int main()
{
	int n;
	while(EOF!=scanf("%d",&n) && n)
	{
		Treap treap;
		char data[1000];
		char ch;
		int p,priority;
		int i;
		for(i=0;i<n;i++)
		{
			p=0;
			getchar();
			while((ch=getchar())!='/')
			{
				data[p++]=ch;
			}
			data[p]=0;
			scanf("%d",&priority);
			NOD* nod=new NOD(data,priority);
			treap.Insert(treap.root,nod);
		}
		print(treap.root);
		putchar(10);
	}
	return 0;
}

• 别用new和指针操作，保存一个下标就可以了，treap用cartesian建立或者用insert+旋转 (0) 407811696 2010-11-19 08:46:16
  • Re:别用new和指针操作，保存一个下标就可以了，treap用cartesian建立或者用insert+旋转 (24) ahululu2010 2014-07-22 14:15:43