avltree.c

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

/*AVL-Tree*/
#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 Node { int Num;
			  int Height;
			  struct Node* Left;
			  struct Node* Right;
			};                     
typedef struct Node* AvlTree; 
AvlTree Root=NULL;                
                                  /*Declaration*/
int Max(int a, int b )
{
	return (a>b)?(a):(b);  
}                                    /*find the bigger */
int AvlTree_Isempty ( AvlTree root )
{
	return (root==NULL);                       /* test empty */
}
AvlTree AvlTree_FinMax ( AvlTree root )
{
	if(!AvlTree_Isempty(root))
	{ 
	while(root->Right!=NULL)
		root=root->Right;
	return root;
	}
	else
	{
	printf("NO MAX IN NULL\n");   /*find the max*/
	return(NULL);
	}
}
int AvlTree_Height( AvlTree root ) /* a height of a node*/
{
	if(!AvlTree_Isempty(root))
		return(root->Height);
	else
		return(-1);
}
AvlTree AvlTree_DubRotationwithRight ( AvlTree root )
{	
	if(!AvlTree_Isempty(root))
	{	
		AvlTree temp1=root->Right;        /*mark the parent*/
		AvlTree 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*/
		root->Height=1+Max( AvlTree_Height(root->Left), AvlTree_Height(root->Right));
		temp1->Height=1+Max( AvlTree_Height(temp1->Left), AvlTree_Height(temp1->Right));
		temp2->Height=1+Max( AvlTree_Height(temp2->Left), AvlTree_Height(temp2->Right));
		/*new height*/		
		return temp2;
	}
	else
	{
		printf("CAN'T DRR NULL");
		return(NULL);
	}

}
AvlTree AvlTree_DubRotationwithLeft ( AvlTree root )
{	
	if(!AvlTree_Isempty(root))		
	{
		AvlTree temp1=root->Left;          /*mark the parent*/
		AvlTree 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*/
		root->Height=1+Max( AvlTree_Height(root->Left), AvlTree_Height(root->Right));
		temp1->Height=1+Max( AvlTree_Height(temp1->Left), AvlTree_Height(temp1->Right));
		temp2->Height=1+Max( AvlTree_Height(temp2->Left), AvlTree_Height(temp2->Right));
		/*new height*/	
		return temp2;
	}
	else
	{
		printf("CAN'T DRL NULL");
		return(NULL);
	}
}

AvlTree AvlTree_SingleRotwithLeft ( AvlTree root )
{  
	if(!AvlTree_Isempty(root))
	{
		AvlTree temp;
		temp=root->Left;
		root->Left=temp->Right;
		temp->Right=root;         /*change the subtree in SearchTree Sequence*/
		root->Height=1+Max( AvlTree_Height(root->Left), AvlTree_Height(root->Right));
		temp->Height=1+Max( AvlTree_Height(temp->Left), AvlTree_Height(temp->Right));
		return(temp);										/*new height*/
	}
	else
	{
		printf("CAN'T SRL NULL");
		return(NULL);
	}
}
AvlTree AvlTree_SingleRotwithRight ( AvlTree root )
{
	if(!AvlTree_Isempty(root))
	{ 
		AvlTree temp;
		temp=root->Right;
		root->Right=temp->Left;
		temp->Left=root;                    /*change the subtree in SearchTree Sequence*/
		root->Height=1+Max( AvlTree_Height(root->Left), AvlTree_Height(root->Right));
		temp->Height=1+Max( AvlTree_Height(temp->Left), AvlTree_Height(temp->Right));
		return(temp);        /*new height*/
	}
	else
	{
		printf("CAN'T SRR NULL");
		return(NULL);
	}
}
AvlTree AvlTree_Insert ( int key,AvlTree root )
{
	if(AvlTree_Isempty(root))
	{
		root=(AvlTree)malloc(sizeof(struct Node));
		root->Num=key;
		root->Left=root->Right=NULL;
		root->Height=0;                    /* for an empty tree*/
	}
	else
	{
		if(key<root->Num)
		{
			root->Left=AvlTree_Insert ( key,root->Left );  /*recurse as BS tree */
			if( AvlTree_Height(root->Left)-AvlTree_Height(root->Right)==2 )
			{							/* left tall need rotate*/
				if(key<root->Left->Num)
					root=AvlTree_SingleRotwithLeft ( root );/*Single Rot with Left*/
				else if(key>root->Left->Num)
					root=AvlTree_DubRotationwithLeft ( root );/*Dub Rotation with Left*/
			}

		}
		if(key>root->Num)
		{
			root->Right=AvlTree_Insert ( key,root->Right );/*recurse as BS tree */
			if( AvlTree_Height(root->Right)-AvlTree_Height(root->Left)==2 )
			{				/* left tall need rotate*/
				if(key>root->Right->Num)
					root=AvlTree_SingleRotwithRight ( root );/*Single Rot with Left*/
				else if(key<root->Right->Num)
					root=AvlTree_DubRotationwithRight ( root );/*Dub Rotation with Left*/
			}

		}
		root->Height=1+Max( AvlTree_Height(root->Right), AvlTree_Height(root->Left) );
		/*new height*/
	}
	return(root);
}
AvlTree AvlTree_Delete ( int key,AvlTree root )
{
	if(!AvlTree_Isempty(root))		/*non-empty*/
	{
		if(key<root->Num)
			{
			root->Left=AvlTree_Delete ( key,root->Left );/*delete from left */
			if( AvlTree_Height(root->Right) - AvlTree_Height(root->Left)==2 )/*right may 2 taller than left;like insert to right */
				if( AvlTree_Height(root->Right->Right)>=AvlTree_Height(root->Right->Left) )
                    root=AvlTree_SingleRotwithRight ( root ); /* if right right taller Single Rot with Right*/
				else
					root=AvlTree_DubRotationwithRight ( root );/* if right left taller Single Rot with Right*/
			}
		else if(key>root->Num)
			{
			root->Right=AvlTree_Delete ( key,root->Right );/*delete from right */
			if( AvlTree_Height(root->Left) - AvlTree_Height(root->Right)==2 )/*right may 2 taller than right;like insert to left */
				if( AvlTree_Height(root->Left->Left)>=AvlTree_Height(root->Left->Right) )
                    root=AvlTree_SingleRotwithLeft ( root );/* if left  left taller; Single Rot with left*/
				else
					root=AvlTree_DubRotationwithLeft ( root );/* if left right taller; Single Rot with left*/
			}
		else
			{
				AvlTree temp;
			if(root->Left!=NULL&&root->Right!=NULL)
				{
				temp=AvlTree_FinMax (root->Left);
				root->Num=temp->Num;
				root->Left=AvlTree_Delete( temp->Num, root->Left);/*replace the deleted with max in left sub*/
				}
			else
				{
				if(root->Left==NULL)
				{
					temp=root;
					root=temp->Right;/*for has one or less subtree ; don't worry about rotation*/
				}
				else if(root->Right==NULL)
				{
					temp=root;
					root=temp->Left;
				}
				 free(temp);
				}
			}

		if(!AvlTree_Isempty(root))		
			root->Height=1+Max( AvlTree_Height(root->Right), AvlTree_Height(root->Left) );
		return(root);				/*new height*/
	}
	else/*empty tree */
	{
		printf("CAN'T DELETE %d\n",key);
		return(root);
	}

}	

		
void input()
{
	int i,key;
	int n=1;
	while(n>=0)/*if n is negative stop */
	{
		scanf("%d", &n);
		if(n>0 &&n<=10001) /*if n is negative stop ; more than 10000 ineffect test*/
		{	
			for(i=1;i<=n;i++)            /*read in n  integer to insert */
			{
				scanf("%d",&key);
				Root=AvlTree_Insert(key,Root);
			}
		   	for(i=1;i<=n;i++)
			{
				scanf("%d",&key);			 /*read in n  integer to delete */
				Root=AvlTree_Delete(key,Root);
			}
		}
		else continue;

	}
}
void output(AvlTree 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++)
	{
	freopen("Input.txt","r",stdin);
    freopen("Output.txt","w",stdout);
	input();
	output(Root); 		
	}
	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 whole time*/
	return 1;
}