#include <stdlib.h>
#include <stdio.h>
/* bst.h */


typedef struct STnode* BST;
struct STnode {
        int nData;
         BST Left;
	     BST Right;
		 int size;
};
static BST T;



/* operations on the bst data type.  This is a very simple
        type, since its entries only store integers. bst
 identified with its root*/

/* bst.c */


BST STinit()
{
 BST T= (BST) malloc(sizeof *T);
 T->size=0;
 T->nData=-1;
 T->Left=NULL;
 T->Right=NULL;
 return T;
}

int STempty (BST T)
{
	return (T->size==0);
}



int STinsert (BST T, int nNewData)
{int steps=0;
	if (T->size==0) 
	{
		T->nData=nNewData;
		T->Left=STinit();
		T->Right=STinit();
	}
	else if (nNewData <= T->nData) 
	{
		steps=STinsert(T->Left, nNewData);
	}
	else
	{	
		steps=STinsert(T->Right, nNewData);
	};
T->size++;
steps++;
/*printf("number inserted is %d, steps taken is %d steps.\n",nNewData,steps);*/
return steps;
	}

void STshow(BST T)
{
	if (T->size==0) return;
	 STshow(T->Left);
	 /*printf("The node %d has size %d.\n",T->nData,T->size);*/
	 STshow(T->Right);
}

int STwhatToDel(BST T,int *small,int *big,int newDel)
{
	int steps=0;
	if (T->size==0) 
	{
		printf("Empty tree: we cannot delete from it");
		return 0;
	}
	/*printf("We are at %d, big is %d, small is %d\n",T->nData,*big,*small)*/;
	if (T->nData==newDel)
	{
		*small=T->nData;
		*big=T->nData;
		return 1;
		/*printf("We are at %d,the number to be found is %d big is %d, small is %d\n",T->nData,newDel,*big,*small);*/
	}
	else if (T->nData>newDel) 
	{
		*big=T->nData;
		/*printf("We are at %d,the number to be found is %d, big is %d, small is %d\n",T->nData,newDel,*big,*small);*/
		if (T->Left->size>0) steps=STwhatToDel(T->Left,small,big,newDel);
	}
	else 
	{
		*small=T->nData;
		/*printf("We are at %d, big is %d, small is %d\n",T->nData,*big,*small);*/
		if (T->Right->size>0) steps=STwhatToDel(T->Right,small,big,newDel);
	}
	steps++;
	return steps;
}

int STrotateUpMax(BST T)
{
	int steps=0, data;
	BST temp;
	/*printf("Now we are at %d,the  right is %d, the left is %d. \n",T->nData, T->Right->nData, T->Left->nData);*/
	if (T->Right->size>0)

	{
		steps=STrotateUpMax(T->Right);
		data=T->nData;
		T->nData=T->Right->nData;
		T->Right->nData=data;
		temp=T->Right;
		T->Right=temp->Right;
		temp->Right=temp->Left;
		temp->Left=T->Left;
		T->Left=temp;
		temp->size=1 + temp->Left->size + temp->Right->size;
	}
return steps;
}

int STdelete(BST T, int key)
/*key must be in the tree*/
{
	int steps=0;
	BST temp;
	if (T->nData>key) steps=STdelete(T->Left,key);
	else if (T->nData<key) steps=STdelete(T->Right,key);
	/*t->nData=key*/
	else if (T->Left->size==0)
	{
		temp=T->Right;
		T->nData=temp->nData;
		T->Left=temp->Left;
		T->Right=temp->Right;
		free(temp);
	}
	else 
	{
		steps=STrotateUpMax(T->Left);
		temp=T->Left;
		T->nData=temp->nData;
		T->Left=temp->Left;
		free(temp);
	}
T->size--;
return steps;
}


void main ()
{
  int nSeed;
  int N,M, Range, ave;
  int i,j,RandomNum, max=0, steps,steps2;
  int sum=0,big=-1,small=-1;

  BST T=STinit();
  printf ("seed?");
  scanf ("%d",&nSeed);
  printf ("N? ");
  scanf ("%d",&N);
  printf ("Range? ");
  scanf ("%d",&Range);
  srand (nSeed); /* srand sets the seed for the generator */
  for(i=0; i < N; i++)
  {
    RandomNum = rand()%Range; /* rand generates an integer random number 0..Range-1 */
    steps=STinsert(T,RandomNum);
	/*printf("Number inserted is %d.\n",RandomNum);*/
	sum=sum+steps;
	if (steps>max) max=steps;
  }
  STshow(T);
  ave=sum/N;
  printf("The max is %d and the average %d.\n",max,ave);
 /*now start deleting*/
  printf("M for deletions? ");
     scanf("%d",&M);
  for (j=0;j<M;j++)
  {
  for (i=0;i<N;i++)
  {
	RandomNum = rand()%Range;
	/*printf("the choosen number is %d.\n",RandomNum);*/
	small=-1;
	big=-1;
	steps=STwhatToDel(T,&small,&big,RandomNum);
	sum=sum+steps;
	if (max<steps) max=steps;
	/*printf("max so far is %d.\n",max);*/
	/*printf("The choices are %d and %d.\n",small,big);*/
	if (small==-1) RandomNum=big;
	else if (big==-1) RandomNum=small;
	else if (big-RandomNum>RandomNum-small) RandomNum=small;
	else RandomNum=big;
	/*printf("The number to be deleted is %d.\n",RandomNum);*/
	steps2=STdelete(T,RandomNum);
	if (max<steps+steps2) max=steps+steps2;
	STshow(T);
	/*printf("max is %d after delete.\n",max);
     scanf("%d",&M);*/

	RandomNum = rand()%Range; /* rand generates an integer random number 0..Range-1 */
    steps=STinsert(T,RandomNum);
	/*printf("Number inserted is %d.\n",RandomNum);*/
	sum=sum+steps;
	if (steps>max) max=steps;
  }
  STshow(T);
  /*printf("M after insert?");
  scanf("%d",&M);*/
  ave=sum/(N+N*(j+1));
  printf("The max is %d and the average %d.\n",max,ave);
  }
}