trees.cpp

对三种数据结构的分析.avl tree,splaytree和binary search tree的插入和删除的算法复杂度分析.

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

typedef struct TreeNode *searchtree;
typedef struct AvlNode *avltree;
typedef struct TreeNode *splaytree;

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 */

/* functions about binary search tree */
searchtree S_Insert(int element,searchtree T); /*insert the integers in the binary search tree*/
searchtree S_Delete(int element,searchtree T); /* delete the integers from the binary search tree*/
searchtree S_FindMin(searchtree T); /* find the minimum in the binary search tree */
searchtree MakeEmpty(searchtree T); /* make the tree empty */
/* functions about avl tree */
int Height(avltree T); /* calculate the avltree's height */
int Max(int a,int b); /* find the larger one */
avltree A_FindMin(avltree T);  /* find the minimum in the AVL tree */
avltree A_Insert(int element,avltree T);  /*insert the integers in the AVL tree*/
avltree A_Delete(int element,avltree T);  /* delete the integers from the AVL tree*/
avltree A_SingleRotateWithLeft(avltree T); /* LL rotate */
avltree A_SingleRotateWithRight(avltree T); /* RR rotate */
avltree A_DoubleRotateWithLeft(avltree T); /* LR rotate */
avltree A_DoubleRotateWithRight(avltree T); /* RL rotate */
avltree Makeempty(avltree T);
/* functions about splay tree */
splaytree splay(int element,splaytree T); /* splay at the node element */
splaytree FindMax(splaytree T); /* find the maxmum in the splay tree */
splaytree Sp_Insert(int element,splaytree T); /* insert the integers in the splay tree */
splaytree Sp_Delete(int element,splaytree T); /* delete the integers from the splay tree*/
splaytree Sp_SingleRotateWithLeft(splaytree T); /* lefe rotate */
splaytree Sp_SingleRotateWithRight(splaytree T); /* right rotate */
splaytree Sp_DoubleRotateWithLeft(splaytree T); /* LR rotate */
splaytree Sp_DoubleRotateWithRight(splaytree T); /* RL rotate */


struct TreeNode  /* binary search tree's node T1 & splay tree's node T3 */
{
	int Element;
	searchtree Left;
	searchtree Right;
}*T1,*T3;
struct AvlNode  /* AVL tree's node T2*/
{
	int Element;
	avltree Left;
	avltree Right;
	int height;
}*T2;

/**************************************************************************************************
************************************** end of declaration ******************************************
***************************************************************************************************/

int main ( )
{


	int N1,N2; /* N1 is the total integers to insert and N2 is the total integers to delete*/
	int num; /* num is the number from input */
	int i;
	FILE *ins,*del,*out;

	if((out=fopen("output.txt","w"))==NULL) /* open the output.txt to show the insert&delete time */
	{
		printf("Can't open the input.txt");
		exit(0);
	}

/*************************************************************************************************
*********************************** BINATY SEARCH TREE *******************************************
**************************************************************************************************/

	if((ins=fopen("ins.txt","r"))==NULL)  /* read ins.txt including n integers to insert */
	{
		printf("Can't open the ins.txt");
		exit(0);
	}
       	
		if((del=fopen("del.txt","r"))==NULL)  /* read del.txt including n integers to delete */
	{
		printf("Can't open the del.txt");
		exit(0);
	}

	fscanf(ins,"%d",&N1); /*read the total number to insert */
	fscanf(del,"%d",&N2); /*read the total number to delete */

	if(N1==0 || N2 ==0)
	{
		printf("illegal input");
		exit(0);
	}

	T1=MakeEmpty(T1);
	start = clock(); 	/* INSERTION*/
	for(i=0;i<N1;i++)
	{
		fscanf(ins,"%d",&num);/*read esch number*/
		T1=S_Insert(num,T1); /*insert the integers*/
    }
	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 */
	fprintf(out,"Inserting time of Binary Search Tree is %le\n",duration);

	start = clock(); 	/* DELETION */
	for(i=0;i<N2;i++)
	{
		fscanf(del,"%d",&num); /* read esch number */
		T1=S_Delete(num,T1); /* delete the integers */
	}
	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 */
	fprintf(out,"Deleting time of Binary Search Tree is %le\n",duration);

	free(T1);

	fclose(ins); /* close the ins.txt */
	fclose(del); /* close the del.txt */

/**************************************************************************************************
******************************************* AVL TREE **********************************************
***************************************************************************************************/

	if((ins=fopen("ins.txt","r"))==NULL)  /* read ins.txt including n integers to insert */
	{
		printf("Can't open the ins.txt");
		exit(0);
	}
       if((del=fopen("del.txt","r"))==NULL)  /* read del.txt including n integers to delete */
	{
		printf("Can't open the del.txt");
		exit(0);
	}

	fscanf(ins,"%d",&N1); /*read the total number to insert */
	fscanf(del,"%d",&N2); /*read the total number to delete */
    T2=Makeempty(T2);
	start = clock(); 	/* INSERTION*/
	for(i=0;i<N1;i++)
	{
		fscanf(ins,"%d",&num);/*read esch number*/
		T2=A_Insert(num,T2); /*insert the integers*/
	}
	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 */
	fprintf(out,"Inserting time of AVL Tree is %le\n",duration);

	start = clock(); 	/* DELETION */
	for(i=0;i<N2;i++)
	{
		fscanf(del,"%d",&num);/* read esch number */
		T2=A_Delete(num,T2); /* delete the integers */
	}
	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 */
	fprintf(out,"Deleting time of AVL Tree is %le\n",duration);

	free(T2);

	fclose(ins); /* close the ins.txt */
	fclose(del); /* close the del.txt */

/**************************************************************************************************
******************************************* splay TREE ********************************************
**************************************************************************************************/

	if((ins=fopen("ins.txt","r"))==NULL)  /* read ins.txt including n integers to insert */
	{
		printf("Can't open the ins.txt");
		exit(0);
	}
       if((del=fopen("del.txt","r"))==NULL)  /* read del.txt including n integers to delete */
	{
		printf("Can't open the del.txt");
		exit(0);
	}

	fscanf(ins,"%d",&N1); /*read the total number to insert */
	fscanf(del,"%d",&N2); /*read the total number to delete */

	T3=MakeEmpty(T3);
    start = clock(); 	/* INSERTION*/
	for(i=0;i<N1;i++)
	{
		fscanf(ins,"%d",&num);/*read esch number*/
		T3=Sp_Insert(num,T3); /*insert the integers*/
	}
	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 */
	fprintf(out,"Inserting time of Splay Tree is %le\n",duration);

	start = clock(); 	/* DELETION */
	for(i=0;i<N2;i++)
	{
		fscanf(del,"%d",&num);/* read esch number */
		T3=Sp_Delete(num,T3); /* delete the integers */
	}
	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 */
	fprintf(out,"Deleting time of Splay Tree is %le\n",duration);

	free(T3);

	fclose(ins); /* close the ins.txt */
	fclose(del); /* close the del.txt */

return 1;
}

/**************************************************************************************************
*********************************** functions about binary searchtree *****************************/

searchtree MakeEmpty(searchtree T)  /* make the tree empty */
{
	if(T!=NULL)
	{
		MakeEmpty(T->Left);
		MakeEmpty(T->Right);
		free(T);
	}
	return NULL;
}

searchtree S_Insert(int element,searchtree T) /*insert the integers*/
{
	if(T==NULL) /*create and return a one-node tree*/
	{
		T=(searchtree)malloc(sizeof(struct TreeNode));
		if(T==NULL)  /*fatal error*/
		{
			printf("out of space");
			exit(0);
		}
		else /* create the new node */
		{
			T->Element=element;
			T->Left=T->Right=NULL;
		}
	}
	else if(element < T->Element) /*element is smaller than the T->Element */
		T->Left=S_Insert(element,T->Left); /*go to the left subtree*/
	else if(element > T->Element) /*element is larger than the T->Element */
		T->Right=S_Insert(element,T->Right); /*go to the right subtree*/

	return T;
}

searchtree S_Delete(int element,searchtree T) /* delete the integers */
{
	searchtree TmpCell;

	if(T==NULL) /* empty tree */
		printf("Not found\n");
	else if(element < T->Element) /* go to the left subtree */
		T->Left=S_Delete(element,T->Left);
	else if(element > T->Element)  /* go to the right subtree */
		T->Right=S_Delete(element,T->Right);
	else /* find the element to be deleted */
		if(T->Left && T->Right) /*two children */
		{
			/* replace with the smallest in the right subtree */
			TmpCell=S_FindMin(T->Right);
			T->Element=TmpCell->Element;
			T->Right=S_Delete(T->Element,T->Right);
		}
		else /* one or zero child */
		{
			TmpCell=T;
			if(T->Left==NULL) /* has right child or zero child */
				T=T->Right;
			else if(T->Right==NULL) /* zero child */
				T=T->Left;
			free(TmpCell); /* free the space of TmpCell */
		}

	return T;
}

searchtree S_FindMin(searchtree T) /* find the minimum in the tree*/
{
	if(T!=NULL)
		while(T->Left!=NULL)
			T=T->Left;

	return T;
}

/************************************ functions about Avltree **************************************/

 avltree Makeempty(avltree T)  /* make the tree empty */
{
	if(T!=NULL)
	{
		Makeempty(T->Left);
		Makeempty(T->Right);
		T->height=-1;
		free(T);
	}
	return NULL;
}
avltree A_Insert(int element,avltree T)  /*insert the integers*/
{
	if(T==NULL) /*create and return a one-node tree*/
	{
		T=(avltree)malloc(sizeof(struct AvlNode));
		if(T==NULL) /*fatal error*/
		{
			printf("out of space");
			exit(0);
		}
		else /* create the new node */
		{
			T->Element=element;
			T->height=0;
			T->Left=T->Right=NULL;
		}
	}