//  DS:  AVL_TREE.
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
class AVL {
//        decleration of members of the tree.
private:
AVL    *left;
AVL    *right;
int    h;
int    x;
public:

int    height(AVL  *TR);     //computes the height of the tree.
AVL    *find_max(AVL  *T);   //finds the max. element in the tree.
void   print_max(AVL *tr);   //prints the max. element after it's found.
AVL    *find_min(AVL  *T);   //finds the min. element.
void   print_min(AVL *tr);   //prints the min. element.
void   print_in(AVL  *T);    //prints all the elements in the tree(in order);
AVL    *make_empty(void);    //makes the tree empty.
int    max(int n1,int n2);   //finds the max. of two numbers.
void   print_post(AVL *T);
AVL    *s_r_left(AVL *k2);   //makes single left rotation.
AVL    *s_r_right(AVL *k1);  //makes single right rotation.
AVL    *d_r_left(AVL *k3);   //makes double left rotation.
AVL    *d_r_right(AVL *k3);  //=       =    right   =    .
AVL    *insert(int n,AVL *T,AVL  *parent);//inserts an element in the tree.
AVL    *inser(int n,AVL  *T);             //calls the above procedure.
AVL    *Delete(int n,AVL *T);             //deletes element from tree.
int    find_sum(AVL *T);
};
//  building of the tree procedures.

int  AVL::height(AVL  *TR)
{
 if (TR==NULL)
	return -1;
 else
	return (TR->h);
}
//==============================
int AVL::find_sum(AVL *T)
{
	if      (T==NULL) return 0;
	else    return(find_sum(T->left)+find_sum(T->right)+T->x);
}
//=============================
AVL *AVL::find_max(AVL *T)
{
if     (T==NULL) return NULL;
else
       while (T->right !=  NULL)
	     T=T->right;
return T;
}
//===============================
void AVL::print_max(AVL *tr)
{

	if  (	tr==NULL)
		cout<<"                      empty \n";
	else

		cout<<"                    max is :  "<<tr->x<<"\n";

}
//================================
AVL *AVL::find_min(AVL *T)
{
if     (T==NULL) return NULL;
else
	while(T->left != NULL)
	      T=T->left;
return T;
}

//==============================
void  AVL::print_min(AVL *tr)
{
	if  (tr==NULL)
		cout<<"                           empty\n";
	else
		cout<<"                           min is :  "<<tr->x<<"\n";
}
//=============================

void AVL::print_in(AVL *T)
{

  if (T !=NULL)

	{
		print_in(T->left);
		cout<<"                    "<<T->x<<"\n";
		print_in(T->right);
	 }
}
//===============================
void AVL::print_post(AVL *T)
{
	if (T !=NULL)
		{
		 print_post(T->left);
		 print_post(T->right);
		 cout<<"		"<<T->x<<"\n";
		}
}
//===============================
AVL  *AVL::make_empty(void)
{
return    NULL;
}
//================================
int  AVL::max(int n1,int n2)
{
if (n1 > n2)
	return n1;
else
	return n2;
}
//=================================

AVL *AVL::s_r_left(AVL *k2)
{
AVL  *k1;
k1=k2->left;
k2->left=k1->right;
k1->right=k2;
k2->h=max(height(k2->left),height(k2->right))+1;
k1->h=max(height(k1->left),k2->h)+1;
return k1;      // new root.
}
//===================================
AVL *AVL::s_r_right(AVL *k1)
{
AVL *k2;

k2=k1->right;
k1->right=k2->left;
k2->left=k1;

k1->h=max(height(k1->left),height(k1->right))+1;
k2->h=max(height(k2->right),k1->h)+1;

return k2;    // new root.
}
//=======================================
AVL   *AVL::d_r_left(AVL *k3)
{
k3->left=s_r_right(k3->left);     // rotates k1 and k2.
return(s_r_left(k3));             // rotates k2 and k3.
}
//=======================================
AVL *AVL::d_r_right(AVL *k3)
{
k3->right=s_r_left(k3->right);   //rotates k1 and k2.

return(s_r_right(k3));           // =      k2 and k3.
}
//=======================================
AVL  *AVL::inser(int n,AVL  *T)
{
       return	insert(n,T,NULL);
}
//========================================
AVL  *AVL::insert(int n,AVL *T,AVL *parent)
{
AVL  *rotated_tree;
if (T == NULL)
  {
    T=new AVL;
    if (T==NULL)            // creates and returns one node tree.
	   cout<<"             out of space";
    else
    {
      T->x = n ; T->h=0;
      T->left=T->right=NULL;
    }
  }
  else
  {
     if(n< T->x )
     {
	T->left=insert(n,T->left,T);
	if ((height(T->left)-height(T->right))==2)
	{
	  if (n<T->left->x)
	      rotated_tree=s_r_left(T);
	  else
	      rotated_tree=d_r_left(T);
	/*  if (parent->left==T)
		parent->left=rotated_tree;
	  else
		parent->right=rotated_tree; */
	  T=rotated_tree;
	}
	else
	  T->h=max(height(T->left),height(T->right))+1;
     }
     else

      if (n>T->x)
      {
	 T->right=insert(n,T->right,T);
	 if(height(T->right)-height(T->left)==2)
	 {
	    if(n>T->right->x)
	       rotated_tree=s_r_right(T);
	    else
	       rotated_tree=d_r_right(T);

	 /*   if (parent->right==T)
		parent->right=rotated_tree;
	    else
		parent->left=rotated_tree;  */
	     T=rotated_tree;
	 }
	 else
	     T->h=max(height(T->left),height(T->right))+1;
       }

  }

  return T;
}
//=======================================
AVL  *AVL::Delete(int n,AVL  *T)
{
   AVL  *tmp_cell,*child,*rotated_tree;
   if(	T==NULL)
	 cout<<"                    element not found ";
   else
	if(n<T->x)           // go left
	  {
	     T->left=Delete(n,T->left);
	     if((height(T->right)-height(T->left))==2)
	     {
		// make rotation.
		if(n<T->left->x)
			rotated_tree=d_r_right(T);
		else
			rotated_tree=s_r_right(T);
		T=rotated_tree;
	    }
	    else
		T->h=max(height(T->left),height(T->right));
	  }
	  else

	       if(n>T->x)        //go right.
	       {
			T->right=Delete(n,T->right);
			if((height(T->left)-height(T->right))==2)
			{
			   //make rotation.
				if(n>T->right->x)
					rotated_tree=d_r_left(T);
				else
					rotated_tree=s_r_left(T);
				T=rotated_tree;
			 }
			 else
				T->h=max(height(T->left),height(T->right));
	      }
	      else
	    if(T->left && T->right)      //two children.
	    {
	      // replace with the smallest in right subtree.
	      tmp_cell=find_min(T->right);
	      T->x=tmp_cell->x;
	      T->right=Delete(T->x,T->right);
	      if((height(T->left)-height(T->right))==2)
	      {
			if(n>T->right->x)
				rotated_tree=d_r_left(T);
			else
				rotated_tree=s_r_left(T);
				T=rotated_tree;
	      }
	      else
				T->h=max(height(T->left),height(T->right));

	   }
	   else
	   {
		tmp_cell=T;
		if(T->left==NULL)       // only a right child.
			child=T->right;
		if(T->right==NULL)      // only a left child.
			child=T->left;
		 delete(tmp_cell);
		 return  child;
	   }
     return   T;
 }



//*****************************
//*****************************

       /*   main program   */

//*****************************
//*****************************
void
main()
{
char  ch,chr;
int   i,a,b,c,d,f;
AVL *avl,*tree,*tr;
avl = NULL;
while (chr !='n' && chr !='N')
{
clrscr();
for (i=1;i<6;i++)  cout<<"\n";
//cout<<"		find    height        :    press  0 \n";
cout<<"		find    max           :    press  1 \n";
cout<<"		find    min           :    press  2 \n";
cout<<"		print   tree          :    press  3 \n";
cout<<"  	        make    empty         :    press  4 \n";

/*cout<<"         s_rotate_left         :    press  5 \n";
cout<<"		s_rotate_right        :    press  6 \n";
cout<<"         d_rotate_left         :    press  7 \n";
cout<<"		d_rotate_right        :    press  8 \n"; */
cout<<"		insert                :    press  5 \n";
cout<<"     	        delete                :    press  6 \n";
cout<<"                print_post order      :    press  7 \n";
cout<<"                find  sum             :    press  8 \n";
cout<<"                ***********************************\n";
ch=getche();
/*if(ch=='0')
   {
    a=avl->height(avl);cout<<"\n"<<"   height is : "<<a<<"\n";
   }     */
if (ch=='1')
   {
    tree=tr->find_max(avl);avl->print_max(tree);
   }
if (ch=='2')
	{
	 tree=tr->find_min(avl);avl->print_min(tree);
	}
if (ch=='3')
	{
	 cout<<"\n";
	 tr->print_in(avl);
	}
if (ch=='4')
	{
	 avl=tr->make_empty();
	}
if (ch=='5')
	{
	 cout<<"\n"<<"                enter element to insert \n" ;
	 cin>>b;
	 avl=tr->inser(b,avl);
	}
if (ch=='6')
	{
	 cout<<"\n"<<"                enter element to delete\n" ;
	 cin>>b;
	 avl=tr->Delete(b,avl);
	}
if (ch=='7')
	{
	 cout<<"\n";
	 tr->print_post(avl);
	}
if (ch=='8')
	{
	 f=tr->find_sum(avl);
	 cout<<"                           sum   =   "<<f<<"\n";
	}
 cout<< "                ***********************************\n";
 cout<< "            continue :   if      not press (n) or (N)\n";
 cout<< "                         else    press  any other key\n";
 chr=getche();cout<<"\n";
 }


}