main.cpp

treap的c++实现。有良好的可读性。并且多次验证了可行性

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
int a[100],right[100],left[100],pri[100];
int root,length;

void newnode(int x,int &p,int r);
void insert(int x,int &p);
void remove(int x,int &p);
void rotateleft(int &p);
void rotateright(int &p);
void deletenode(int &p);

int  main()
{
	pri[0]=20;
	srand(unsigned(time(NULL)));
	insert(2,root);
	insert(12,root);
	remove(12,root);
	remove(2,root);
	return 0;
}


void insert(int x,int &p)
{
	if (!p) newnode(x,p,rand()%20);
	else if (x<a[p])
	{
		insert(x,left[p]);
		if (pri[left[p]]<pri[p]) rotateleft(p);
	}
	else if (x>a[p])
	{
		insert(x,right[p]);
		if (pri[right[p]]<pri[p]) rotateright(p);
	}
}
void newnode(int x,int &p,int r)
{
	length++;
	p=length;
	a[p]=x;
	pri[p]=r;
}
void rotateleft(int &p)
{
	int q=left[p];
	left[p]=right[q];
	right[q]=p;
	p=q;
}
void rotateright(int &p)
{
	int q=right[p];
	right[p]=left[q];
	left[q]=p;
	p=q;
}
void remove(int x,int &p)
{
	if (p)
	{
		if (x<a[p]) remove(x,left[p]);
		else if (x>a[p]) remove(x,right[p]);
		else
		{
			if (!left[p]&&!right[p]) deletenode(p);
			if (pri[left[p]]<pri[right[p]])
			{
				rotateleft(p);
				remove(x,right[p]);
			}
			else {
				rotateright(p);
				remove(x,left[p]);
			}
		}
	}
}
void deletenode(int &p)
{
	a[p]=0;left[p]=0;right[p]=0;pri[p]=0;p=0;
}