p1.c

主要是avl,splay和binary树的insert,delete程序,主要是avl,splay.binary树的

/**
 * Filename: Project 1
 * Description: Insertion and deletion of Binary search tree, AVL tree and splay tree
 * Author:
 **/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include<malloc.h>
#define Max(a, b) (a > b? a : b)

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

typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
struct TreeNode				/* BinarysearchTree's Struct */
{
	int Num;
	SearchTree Left;
	SearchTree Right;
};

typedef struct AvlNode *AvlPosition;
typedef struct AvlNode *AvlTree;
struct AvlNode				/* AVLTree's Struct */
{
	AvlTree Left;
	AvlTree Right;
	int Height;
	int Num;
};

typedef struct SplayNode *SplayPosition;
typedef struct SplayNode *SplayTree;
struct SplayNode			/*SplayTree's Struct*/
{
	int Num;
	SplayTree Left;
	SplayTree Right;
	
};

Position FindMin(SearchTree T)   /* Find The Minimal number in Binary Search Tree */
{
	if(T == NULL)
		return NULL;
	else if(T->Left == NULL)
		return T;
	else 
		return FindMin(T->Left);
}

AvlPosition Find(AvlTree T)		/* Find The Minimum in AVL Tree */
{
	if(T == NULL)
		return NULL;
	else if(T->Left == NULL)
		return T;
	else 
		return Find(T->Left);
}

AvlPosition FindMax(AvlTree T)	/* Find The Maximum  in AVL Tree */
{

	if(T == NULL)
		return NULL;
	else if(T->Right == NULL)
		return T;
	else 
		return FindMax(T->Right);
}

SearchTree Insert(int number, SearchTree T)
{
	if(T == NULL)
	{
		T = malloc(sizeof(struct TreeNode));
		if(T == NULL)
		{
			printf("Out of space\n");
		}
		else
		{
			T->Num = number;
			T->Left = T->Right = NULL;
			
		}
	}
	else if(number < T->Num)		/*Go Left*/
		T->Left = Insert(number, T->Left);
	else if(number > T->Num)		/*Go Right*/
		T->Right = Insert(number, T->Right);
	
	return T;
}

SearchTree Delete(int number, SearchTree T)
{
	Position Tmp;

	if(T == NULL)
	{
		printf("Element not found\n");
	}
	else if(number < T->Num)	/*Go Left*/
		T->Left = Delete(number, T->Left);
	else if(number > T->Num)	/*Go Right*/
		T->Right = Delete(number, T->Right);
	else if(T->Left && T->Right)/*two children*/
	{
		Tmp = FindMin(T->Right);
		T->Num = Tmp->Num;
		T->Right = Delete(T->Num, T->Right);
	}
	else						/*one child or none*/
	{
		Tmp = T;
		if(T->Left == NULL)
			T = T->Right;
		else if(T->Right == NULL)
			T = T->Left;
		free(Tmp);
	}

	return T;
}
static
int Height(AvlPosition P)			/* To make the height of the Node in AVLTree */
{
	if(P == NULL)
		return -1;
	else
		return P->Height;
}

static AvlPosition SingleRotateWithLeft(AvlPosition K2)		/*make LL single rotation*/
{
	AvlPosition K1;

	K1 = K2->Left;
	K2->Left = K1->Right;
	K1->Right = K2;

	K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;	/*to change the height after ratation*/
	K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;

	return K1;
}

static AvlPosition SingleRotateWithRight(AvlPosition K1)	/*make RR single rotation*/
{
	AvlPosition K2;

	K2 = K1->Right;
	K1->Right = K2->Left;
	K2->Left = K1;

	K2->Height = Max(Height(K2->Left), Height(K2->Right)) + 1;
	K1->Height = Max(Height(K1->Left), Height(K1->Right)) + 1;

	return K2;
}

static AvlPosition DoubleRotateWithLeft(AvlPosition K3)		/*make LR double rotation*/
{

	K3->Left=SingleRotateWithRight(K3->Left);
	return SingleRotateWithLeft(K3);
}

static AvlPosition DoubleRotateWithRight(AvlPosition K1)		/*make RL double rotation*/
{
	
	K1->Right=SingleRotateWithLeft(K1->Right);
	return SingleRotateWithRight(K1);
}

AvlTree AvlInsert(int number, AvlTree T)
{
	if(T == NULL)				 /* T is NULL */
	{
		T = malloc(sizeof(struct AvlNode));
		if(T == NULL)
		{
			printf("Out of space \n");
		}
		else
		{
		T->Num = number;
		T->Left = T->Right = NULL;
		T->Height = 0;
		}
		
	}
	else if(number < T->Num)	 /* Go left */ 
	{
		T->Left = AvlInsert(number, T->Left);
		if(Height(T->Left) - Height(T->Right) == 2) /* not balanced */
		{
			if(number < T->Left->Num)	/* LL Rotation */
				T = SingleRotateWithLeft(T);
			else						/* LR Rotation */
				T = DoubleRotateWithLeft(T);
		}
	}
	else if(number > T->Num)			/* Go right */ 
	{
		T->Right = AvlInsert(number, T->Right);
		if(Height(T->Right) - Height(T->Left) == 2)
		{
			if(number >T->Right->Num)	/* RR Rotation */	
				T = SingleRotateWithRight(T);
			else						/* RL Rotation */
				T = DoubleRotateWithRight(T);
		}
	}

	T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
	return T;
}

AvlTree AvlDelete( int number, AvlTree T ) 
{    
	AvlPosition TmpTree;
    
	if ( T == NULL )   /* T is NULL */
	{
		printf( "Element not found\n" ); 
	}
	else  if ( number < T->Num )  /* Go left */ 
	{
		T->Left = AvlDelete( number, T->Left ); 
		if ( Height( T->Right ) - Height( T->Left ) == 2 ) /* not balanced */
		if (T->Right->Right == NULL)/* RL Rotation */
			T = DoubleRotateWithRight( T );
		else  /* RR Rotation */
			T = SingleRotateWithRight( T ); 
	}
	else  if ( number > T->Num )  /* Go right */ 
	{    
		T->Right = AvlDelete( number, T->Right );
		if ( Height( T->Left ) - Height( T->Right ) == 2 ) /* not balanced */
	        if ( T->Left->Left == NULL)  /* LR Rotation */
				T = DoubleRotateWithLeft( T ); 
	        else  /* LL Rotation */
				T = SingleRotateWithLeft( T );
	}	 
	else /* Found element to be deleted */ 
	{		
		if ( T->Left && T->Right )  /* Two children */ 
	               /* Replace with smallest in right subtree */ 
		{
			if(Height(T->Left) > Height(T->Right))		/* the judge make the tree balance easily*/
			{
				
				TmpTree = FindMax(T->Left);
				T->Num = TmpTree->Num;
			    T->Left = AvlDelete(T->Num, T->Left);
			}
			else
			
			{
				TmpTree = Find(T->Right);
				T->Num = TmpTree->Num;
			    T->Right = AvlDelete(T->Num, T->Right);
			}
			
		
		} /* End if */
		else  /* One or zero child */ 
		{
			TmpTree = T; 
			if ( T->Left == NULL ) /* Also handles 0 child */ 
				T = T->Right; 
			else  if ( T->Right == NULL )  
				T = T->Left; 
			free( TmpTree );  
		
		}  /* End else 1 or 0 child */
	}
	if(T != NULL)
		T->Height = Max( Height( T->Left ), Height( T->Right ) ) + 1;
	
	return  T; 
}

static SplayPosition ZigZigLeft(SplayPosition K2)  /* When the left sub-tree is zig-zig, do single rotation with left */
{
	SplayPosition K1;

	K1 = K2->Left;  /* K1 is the left child of the root */
	K2->Left = K1->Right; 
	K1->Right = K2;  /* make K2 the right child of K1 */

	return K1; 
}

static SplayPosition ZigZigRight(SplayPosition K1) /* when the right sub-tree is zig-zig, do single rotation with right */
{
	SplayPosition K2;

	K2 = K1->Right; /* K2 is the right child of the root */
	K1->Right = K2->Left;
	K2->Left = K1; /* make K1 the left child of K2 */

	return K2;
}

SplayTree
Splay(int Item, SplayTree T)
{
	static struct SplayNode Header;
	SplayPosition LeftTreeMax,RightTreeMin;  

	Header.Left=Header.Right=NULL;
	LeftTreeMax=RightTreeMin=&Header;  /* Header is the head of the left-tree and right-tree */
	
	while(Item !=T->Num) 
	{
		if(Item<T->Num)  /* move the elements larger than Item to a right-tree */
		{
			if(T->Left == NULL)