splaytree.c

数据结构基础（ C）： splay 树； BS 树； AVL 树

/*SplayTree*/
#include<stdio.h>
#include <time.h>
clock_t  start, stop; /* clock_t is a built-in type for processor time (ticks) */
double  duration;  /* records the run time (seconds) of a function */
struct SPTreeNode { int Num;
					struct SPTreeNode* Left;
					struct SPTreeNode* Right;
					};
typedef struct SPTreeNode* SPTree;
SPTree Head;			/*an external tree root;Head Num is negative ;thus the tree is head's right child  */
int Path[10001];		/*an array to remember the visiting  path*/
int Pos=1;				/*the position on the visiting path*/
void  SPTree_Initial()
{ 
	Head=(SPTree)malloc(sizeof(struct SPTreeNode));
	Head->Num=-1;
	Head->Left=Head->Right=NULL;/*make the empty tree right child of Head*/
	Path[0]=-1;			/* Head's Num is -1*/
}
int SPTree_Isempty( SPTree root)
{	
	return (root==NULL);/*test emptyness */
}
SPTree SPTree_Finmax( SPTree root)/*find max*/
{
	if(!SPTree_Isempty(root))
	{ 
	while(root->Right!=NULL)
		root=root->Right;
	return root;
	}
	else
	{
		printf("NO MAX IN NULL\n");
		return(NULL);
	}
}
SPTree SPTree_ZigZigwithLeft( SPTree root)/*zigzig left*/
{
	if(!SPTree_Isempty(root))
	{
		SPTree temp1,temp2;
		temp1=root->Left;
		temp2=temp1->Left;
		temp1->Left=temp2->Right;
		root->Left=temp1->Right;
		temp2->Right=temp1;
		temp1->Right=root;
		return(temp2);/*return the new tree*/
	}
	else
	{
		printf("CAN'T ZIZL NULL");
		return(root);
	}
}
SPTree SPTree_ZigZigwithRight( SPTree root)/*ZigZig Right*/
{	
	if(!SPTree_Isempty(root))
	{
		SPTree temp1,temp2;
		temp1=root->Right;
		temp2=temp1->Right;
		temp1->Right=temp2->Left;
		root->Right=temp1->Left;
		temp2->Left=temp1;
		temp1->Left=root;
		return(temp2);
	}
	else
	{
		printf("CAN'T ZIZR NULL");
		return(root);
	}
}

SPTree SPTree_ZigZagwithLeft( SPTree root)/*ZigZag Left*/
{	
	if(!SPTree_Isempty(root))		
	{
		SPTree temp1=root->Left;          /*mark the parent*/
		SPTree temp2=temp1->Right;        /*mark the tall son*/
		root->Left=temp2->Right;
		temp1->Right=temp2->Left;
		temp2->Left=temp1;                 /*change the subtree in SearchTree Sequence*/
		temp2->Right=root;                 /*tall son is new root*/
		return temp2;
	}
	else
	{
		printf("CAN'T ZAZL NULL");
		return(root);
	}
}
SPTree SPTree_ZigZagwithRight( SPTree root)/*ZigZag Right*/
{
	if(!SPTree_Isempty(root))
	{	
		SPTree temp1=root->Right;        /*mark the parent*/
		SPTree temp2=temp1->Left;        /*mark the tall son*/
		root->Right=temp2->Left;
		temp1->Left=temp2->Right;
		temp2->Right=temp1;               /*change the subtree in SearchTree Sequence*/
		temp2->Left=root;                 /*tall son is new root*/
		return temp2;
	}
	else
	{
		printf("CAN'T ZAZR NULL");
		return(root);
	}
}
SPTree SPTree_ChangeLeft(SPTree root)/*exChange with Left ; used for two left*/
{	
	if(!SPTree_Isempty(root))
	{
		SPTree temp=root->Left;
		root->Left=temp->Right;
		temp->Right=root;
		return temp;
	}
	else
	{
		printf("CAN'T CL NULL");
		return(root);
	}
}
SPTree SPTree_ChangeRight(SPTree root)/*exChange with Right ; used for two left*/
{	
	if(!SPTree_Isempty(root))
	{
		SPTree temp=root->Right;
		root->Right=temp->Left;
		temp->Left=root;
		return temp;
	}
	else
	{
		printf("CAN'T CR NULL");
		return(root);
	}
}
SPTree SPTree_Pos(int key, SPTree root)/*return the position of element in the tree*/
{
	if(!SPTree_Isempty(root))
	{
		if(root->Num==key)
			return(root);
		else
			if(root->Num<key)
				return(SPTree_Pos(key,root->Right));/*recurse right*/
			else
				return(SPTree_Pos(key,root->Left));/*recurse left*/
		
	}
	else
	{
		printf("CAN'T FIND %d\n",key);
		return(NULL);
	}
}

void SPTree_Up()
{
	SPTree temp,head;
	for(;Pos>=3;Pos-=2)/*more than or equal three left on the path*/
	{ 	
		if(Pos==3)
			head=Head;/*three left */
		else
			head=SPTree_Pos(Path[Pos-3],Head->Right);/*more than three*/
		
		temp=SPTree_Pos(Path[Pos-2],Head->Right);/*the grandfather */
		if(head->Num<Path[Pos-2])/*the grandfather is on right of grandgrandfather*/
			{
			if(Path[Pos-2]<Path[Pos-1] && Path[Pos-1]<Path[Pos])/*Zig Zig with Right*/
				head->Right=SPTree_ZigZigwithRight(temp);
			else if(Path[Pos-2]<Path[Pos-1] && Path[Pos-1]>Path[Pos])/*Zig Zag with Right*/
				head->Right=SPTree_ZigZagwithRight(temp);
			else if(Path[Pos-2]>Path[Pos-1] && Path[Pos-1]>Path[Pos])/*Zig Zig withLeft*/
				head->Right=SPTree_ZigZigwithLeft(temp);
			else if(Path[Pos-2]>Path[Pos-1] && Path[Pos-1]<Path[Pos])/*Zig Zag with Left*/
				head->Right=SPTree_ZigZagwithLeft(temp);
			}
		else if(head->Num>Path[Pos-2])/*the grandfather is on left of grandgrandfather*/
			{
			if(Path[Pos-2]<Path[Pos-1] && Path[Pos-1]<Path[Pos])/*symmetry with above*/
				head->Left=SPTree_ZigZigwithRight(temp);
			else if(Path[Pos-2]<Path[Pos-1] && Path[Pos-1]>Path[Pos])
				head->Left=SPTree_ZigZagwithRight(temp);
			else if(Path[Pos-2]>Path[Pos-1] && Path[Pos-1]>Path[Pos])
				head->Left=SPTree_ZigZigwithLeft(temp);
			else if(Path[Pos-2]>Path[Pos-1] && Path[Pos-1]<Path[Pos])
				head->Left=SPTree_ZigZagwithLeft(temp);
			}
		
	}
	if(Pos==2)/*two left;exchange with root*/
	{
	
	if(Head->Num<Path[1])
		{
		if(Path[2]>Path[1])
			Head->Right=SPTree_ChangeRight(Head->Right);
		else if(Path[2]<Path[1])
			Head->Right=SPTree_ChangeLeft(Head->Right);
		}
	}
	Pos=1;/*start over*/
}

	
	
	
SPTree SPTree_Visit(int key, SPTree root)/*remember the visiting path on the array*/
{
	if(!SPTree_Isempty(root))
	{
		if(root->Num==key)
		{
			Path[Pos]=key;/*destination of visiting*/
		}
		else
		{
			Path[Pos++]=root->Num;/*remember the element passed*/
			if(root->Num<key)
			return(SPTree_Visit(key,root->Right));/*recurse in right*/
			else 
			return(SPTree_Visit(key,root->Left));/*recurse in left*/
		}
	}
	else
		printf("CAN'T VISIT %d\n",key);/*not in the tree*/
	
	return(root);	
}

SPTree SPTree_Insertnum(int key, SPTree root)/* inser the element as BS tree*/
{	
	if(SPTree_Isempty(root))
	{ 
		root=(SPTree)malloc(sizeof(struct SPTreeNode));
		root->Num=key;
		root->Left=root->Right=NULL;
	}
	else
	{	
		if(key<root->Num)
			root->Left =SPTree_Insertnum( key , root->Left );
		else if(key>root->Num)
			root->Right=SPTree_Insertnum( key , root->Right);
		
	}
	return(root);
}
SPTree SPTree_Insert(int key)
{ 
	Head->Right=SPTree_Insertnum(key,Head->Right);/*insert element */
	SPTree_Visit(key,Head->Right);/*visit element*/
	SPTree_Up();/*up it to root*/
	return(Head->Right);/*finishing insert*/
}
SPTree SPTree_Delete( int key )
{
	if(!SPTree_Isempty(Head->Right))
	{
	SPTree temp,temp1,temp2,temp3;
		if(SPTree_Visit(key,Head->Right)!=NULL)
		{
			SPTree_Up();/*the element is in the tree,up it to the root */
			temp=Head->Right;
			temp1=temp->Left;
			temp2=temp->Right;
			if((temp3=SPTree_Finmax(temp->Left))!=NULL)/*left subtree has a max*/
			{
				free(temp);/*delete the element*/
				Head->Right=temp1;/*connect left subtree */
				SPTree_Visit(temp3->Num,Head->Right);
				SPTree_Up();/*use the max to be the root */
				Head->Right->Right=temp2;/*connet the right subtree*/
			}
			else
			{	
				free(temp);
				return(temp2);/*left subtree has no max;thus empty,directly connect right subtree*/
			}
		}
		else 
			printf("%d IS NOT IN\n",key);/*element is not in*/
		
	}	
	else
		printf("CAN'T Delete %d IN NULL\n",key);/*empty tree*/
	
	return(Head->Right);/*new tree*/
}


void input()
{
	int i,key;
	int n=1;
	while(n>=0)/*negative command number;end test*/
	{
		scanf("%d", &n);
		if(n>0 && n<=10001)/*negative or too large,quit test*/
		{	
			for(i=1;i<=n;i++)
			{
				scanf("%d",&key);
				Head->Right=SPTree_Insert (key);/*read in element to insert*/
			}
			for(i=1;i<=n;i++)
			{
				scanf("%d",&key);
				Head->Right=SPTree_Delete (key);/*read in element to delete*/
			}
		}
		else continue;

	}
}
void output(SPTree root)/*inorder travesal*/
{
	if(root!=NULL)
	{	
		output(root->Left);
		printf("%d\n",root->Num);
		output(root->Right);
	}
}

 int main ( )
{	
	int i;
	/* clock() returns the amount of processor time (ticks) that has elapsed
		since the program began running */
	start = clock(); 	/* records the ticks at the beginning of the function call */
	for(i=0;i<=100;i++)/*run 100 times */
	{
	freopen("Input.txt","r",stdin);
    freopen("Output.txt","w",stdout);
	SPTree_Initial();
	input();
 	output(Head->Right); 	
	}
	stop = clock();	/* records the ticks at the end of the function call */
	duration = ((double)(stop - start))/CLK_TCK; 
											/* CLK_TCK is a built-in constant = ticks per second */
	printf("%lf",duration);/*the time used*/
	return 1;
}