伸展树基本操作.txt

ACM资料大集合

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

#define NMAX 200
typedef struct record
{
	int father,lchild,rchild;
//	record *father,*lchild,*rchild;
	int data;
}record;

record temp;
//record *ans;
//record *T;//=&temp;;
record T[NMAX];
int root;
int height;

void RRT(int x)
{
	int y=T[x].father;

	T[y].lchild=T[x].rchild;
	if(T[x].rchild!=0) T[T[x].rchild].father=y;

	T[x].father=T[y].father;
	if(T[y].father!=0)
	{
		if(y==T[T[y].father].lchild) T[T[y].father].lchild=x;
		else T[T[y].father].rchild=x;
	}

	T[y].father=x;
	T[x].rchild=y;
}

void LRT(int x)
{
	int y=T[x].father;

	T[y].rchild=T[x].lchild;
	if(T[x].lchild!=0) T[T[x].lchild].father=y;

	T[x].father=T[y].father;
	if(T[y].father!=0)
	{
		if(y==T[T[y].father].lchild) T[T[y].father].lchild=x;
		else T[T[y].father].rchild=x;
	}

	T[y].father=x;
	T[x].lchild=y;
}

void splay(int now)
{
	int t;
	while(T[now].father!=0)
	{
//		printf("splay now=%d\n",now);
		t=T[now].father;
		if(T[t].father==0)
		{
			if(now==T[t].lchild) 
			{RRT(now);printf("ZIG\n");}
			else {LRT(now);printf("ZAG\n");}
			break;
		}

		if(now==T[t].lchild)
		{
			if(t==T[T[t].father].lchild) {RRT(t);RRT(now);printf("ZIG-ZIG\n");}
			else {RRT(now);LRT(now);printf("ZIG-ZAG\n");}
		}
		else
		{
			if(t==T[T[t].father].rchild) {LRT(t);LRT(now);printf("ZAG-ZAG\n");}
			else {LRT(now);RRT(now);printf("ZAG-ZIG\n");}
		}
//		printf("splay now=%d\n",now);
	}
	root=now;
}
bool bst_search(int key,int tt,int fa,int &ans)
{
	ans=tt;
	if(key<T[tt].data)
	{
		if(T[tt].lchild!=0)	return bst_search(key,T[tt].lchild,tt,ans);
		else return false;
	}
	else if(key>T[tt].data)
	{
		if(T[tt].rchild!=0) return bst_search(key,T[tt].rchild,tt,ans);
		else return false;
	}
	else return true;
}

bool bst_insert(int x,int tt,int p)
{
	int ans=0;
	if(bst_search(x,tt,0,ans)==false)
	{
		T[p].data=x;
		T[p].lchild=T[p].rchild=0;
		T[p].father=ans;;
		if(x<T[ans].data) T[ans].lchild=p;
		else T[ans].rchild=p;
		return true;
	}
	return false;
}

void visit(int tt,int th)
{
	if(height<th) height=th;
	if(T[tt].lchild!=0) visit(T[tt].lchild,th+1);
	printf("%d ",T[tt].data);
	if(T[tt].rchild!=0) visit(T[tt].rchild,th+1);
}

void insert(int x,int p)
{
	int trr=root,j;
	if(bst_insert(x,trr,p)==true)	splay(p);
}

void init(int x)
{
	int i;
	for(i=1;i<NMAX;i++)
	{
		T[i].data=T[i].father=T[i].lchild=T[i].rchild=0;
	}
	T[1].data=x;
	root=height=1;
}

int main()
{
	int i,num,a,j;
	scanf("%d",&num);
	scanf("%d",&a);
	init(a);
	visit(1,height);
	printf("\nheight=%d\n\n",height);
	for(i=2;i<=num;i++)
	{
		scanf("%d",&a);
		height=1;
		insert(a,i);
		visit(root,1);
		printf("\nheight=%d\n\n",height);
	}
}
/*
bool bst_search(int key,record *tt,record *fa)
{//要查找的元素是key,tt是当前节点，fa是父节点，ans是最后返回的节点
	if(tt==NULL) {ans=fa;return false;}
	else if(key<(tt->data)) return bst_search(key,tt->lchild,tt);
	else if(key>(tt->data)) return bst_search(key,tt->rchild,tt);
	else {ans=tt;return true;}
	return true;
}

void bst_insert(int x,record *tt)
{
	record *s;
	ans=NULL;
	if(bst_search(x,tt,NULL)==false) 
	{
		s=(record *)malloc(sizeof(record));
		s->data=x;
		s->lchild=s->rchild=s->father=NULL;
		if(ans==NULL) T=s;
		else if(x<ans->data) {ans->lchild=s;s->father=ans;}
		else {ans->rchild=s;s->father=ans;}
	}	
}

void insert(int x,record *tt)
{
//	printf("insert\n");
	bst_insert(x,tt);
}

void visit(record *tt)
{
	if(tt->lchild!=NULL) visit(tt->lchild);
	printf("%d ",tt->data);
	if(tt->rchild!=NULL) visit(tt->rchild);
}


int main()
{
	int i,num,a;
	scanf("%d",&num);
	for(i=1;i<=num;i++)
	{
		scanf("%d",&a);
		insert(a,T);
		visit(T);
		printf("\n");
	}
}
*/