#include
#include

#define TRUE 1
#define FALSE 0
#define NULL 0
class AVL;
class AVLNODE
{
	friend class AVL;
	private:
		int data;
		AVLNODE *left,*right;
		int bf;
};
class AVL
{
	private:
		AVLNODE *root;
	public:
		AVLNODE *loc,*par;
		AVL()
		{
			root=NULL;
		}
		int insert(int);
		void displayitem();
		void display(AVLNODE *);
		void removeitem(int);
		void remove1(AVLNODE *,AVLNODE *,int);
		void remove2(AVLNODE *,AVLNODE *,int);
		void search(int x);
		void search1(AVLNODE *,int);
};
int AVL::insert(int x)
{
	AVLNODE *a,*b,*c,*f,*p,*q,*y,*clchild,*crchild;
	int found,unbalanced;
	int d;
	if(!root)   //special case empty tree
	{          y=new AVLNODE;
		y->data=x;
		root=y;
		root->bf=0;
		root->left=root->right=NULL;
		return TRUE;	}
	//phase 1:locate insertion point for x.a keeps track of the most
	// recent node with balance factor +/-1,and f is the parent of a
	// q follows p through the tree.
	f=NULL;
	a=p=root;
	q=NULL;
	found=FALSE;
	while(p&&!found)
	{                 //search for insertion point for x
		if(p->bf)
		{
			a=p;
			f=q;
		}
		if(xdata)    //take left branch
		{
			q=p;
			p=p->left;
		}
		else if(x>p->data)
		{
			q=p;
			p=p->right;
		}
		else
		{
			y=p;
			found=TRUE;
		}
	}               //end while
	//phase 2:insert and rebalance.x is not in the tree and
	// may be inserted as the appropriate child of q.
	if(!found)
	{
		y = new AVLNODE;
		y->data=x;
		y->left=y->right=NULL;
		y->bf=0;
		if(xdata)    //insert as left child
		q->left=y;
		else
		q->right=y;    //insert as right child
		//adjust balance factors of nodes on path from a to q
		//note that by the definition of a,all nodes on this
		//path must have balance factors of 0 and so will change
		//to +/- d=+1 implies that x is inserted in the left
		// subtree of a d=-1 implies
		//to that x inserted in the right subtree of a.
		

if(x>a->data)
		{
			p=a->right;
			b=p;
			d=-1;
		}
		else
		{
			p=a->left;
			b=p;
			d=1;
		}
		while(p!=y)
		if(x>p->data)          //height of  right increases by 1
		{
			p->bf=-1;
			p=p->right;
		}
		else                 //height of left increases by 1
		{
			p->bf=1;
			p=p->left;
		}
		//is tree unbalanced
		unbalanced=TRUE;
		if(!(a->bf)||!(a->bf+d))
		{                   //tree still balanced
			a->bf+=d;
			unbalanced=FALSE;
		}
		if(unbalanced)   //tree unbalanced,determine rotation type
		{
			if(d==1)
			{         //left imbalance
				if(b->bf==1)      //rotation type LL
				{
					a->left=b->right;
					b->right=a;
					a->bf=0;
					b->bf=0;
				}
				else    //rotation type LR
				{
					c=b->right;
					b->right=c->left;
					a->left=c->right;
					c->left=b;
					c->right=a;
					

switch(c->bf)
					{
						case 1: a->bf=-1;  //LR(b)
							b->bf=0;
							break;
						case -1:b->bf=1;  //LR(c)
							a->bf=0;
							break;
						case 0: b->bf=0;  //LR(a)
							a->bf=0;
							break;
					}
					c->bf=0;
					b=c; //b is the new root
				} //end of LR
			}         //end of left imbalance
		      else    //right imbalance
		      {
				if(b->bf==-1)      //rotation type RR
				{
					a->right=b->left;
					b->left=a;
					a->bf=0;
					b->bf=0;
				}
				else    //rotation type LR
				{
					c=b->right;
					b->right=c->left;
					a->right=c->left;
					c->right=b;
					c->left=a;
					switch(c->bf)
					{
						case 1: a->bf=-1;  //LR(b)
							b->bf=0;
							break;
						case -1:b->bf=1;  //LR(c)
							a->bf=0;
							break;
						case 0: b->bf=0;  //LR(a)
							a->bf=0;
							break;
					}
					c->bf=0;
					b=c; //b is the new root
				} //end of LR
			   }
//subtree with root b has been rebalanced and is the new subtree
			
if(!f)
			root=b;
			else if(a==f->left)
			f->left=b;
			else if(a==f->right)
			f->right=b;
		}   //end of if unbalanced
		return TRUE;
	}         //end of if(!found)
	return FALSE;
}     //end of AVL INSERTION

void AVL::displayitem()
{
	display(root);
}
void AVL::display(AVLNODE *temp)
{
	if(temp==NULL)
	return;
	cout<data<<" ";
	display(temp->left);
	display(temp->right);
}
void AVL::removeitem(int x)
{
	search(x);
	if(loc==NULL)
	{
		cout<<"\nitem is not in tree";
		return;
	}
	if(loc->right!=NULL&&loc->left!=NULL)
	remove1(loc,par,x);
	else
	remove2(loc,par,x);
}
void AVL::remove1(AVLNODE *l,AVLNODE *p,int x)
{
	AVLNODE *ptr,*save,*suc,*psuc;
	ptr=l->right;
	save=l;
	while(ptr->left!=NULL)
	{
		save=ptr;
		ptr=ptr->left;
	}
	suc=ptr;
	psuc=save;
	remove2(suc,psuc,x);
	if(p!=NULL)
		if(l==p->left)
			p->left=suc;
		else
			p->right=suc;
	else
		root=l;
	 suc->left=l->left;
	 suc->right=l->right;
	  return;
}
void AVL::remove2(AVLNODE *s,AVLNODE *p,int x)
{
	AVLNODE *child;
	if(s->left==NULL && s->right==NULL)
		child=NULL;
	else if(s->left!=NULL)
		child=s->left;
	else
		child=s->right;
	if(p!=NULL)
		if(s==p->left)
			p->left=child;
		else
			p->right=child;
	else
		root=child;

}
void AVL::search(int x)
{
	search1(root,x);
}
void AVL::search1(AVLNODE *temp,int x)
{
       AVLNODE *ptr,*save;
       int flag;
       if(temp==NULL)
       {
		cout<<"\nthe tree is empty";
		return;
       }
       if(temp->data==x)
       {
		cout<<"\nthe item is root and is found";
		par=NULL;
		loc=temp;
		par->left=NULL;
		par->right=NULL;
		return;       }
       if( x < temp->data)
       {
		ptr=temp->left;
		save=temp;
       }
       else
       {
		ptr=temp->right;
		save=temp;
       }
       while(ptr!=NULL)
       {
		if(x==ptr->data)
		{       flag=1;
			cout<<"\nitemfound";
			loc=ptr;
			par=save;

		}
		if(xdata)
		ptr=ptr->left;
		else
		ptr=ptr->right;
       }
       if(flag!=1)
       {
		cout<<"item is not there in tree";
		loc=NULL;
		par=NULL;
		cout<		cout<       }
}

main()
{
	AVL a;
	int x,y,c;
        char ch;	
	do
	{
		cout<<"\n1.insert";
		cout<<"\n2.display";
		cout<<"\n3.delete";
		cout<<"\n4.search";
		cout<<"\n5.exit";
		cout<<"\nEnter u r choice to perform on AVL tree";
		cin>>c;
		

switch(c)
		{
			case 1:cout<<"\nEnter an element to insert into tree";
				cin>>x;
				a.insert(x);
				break;
			case 2:a.displayitem(); break;
			case 3:cout<<"\nEnter an item to deletion";
			       cin>>y;
			       a.removeitem(y);
			       break;
			case 4:cout<<"\nEnter an element to search";
				cin>>c;
				a.search(c);
				break;
			case 5:exit(0);	break;
		      default :cout<<"\nInvalid option try again";
		}
		cout<<"\ndo u want to continue";
		cin>>ch;
	}
	while(ch=='y'||ch=='Y');
}