C CODE FOR AVL TREE

C++ code for AVL TREE :

#include<iostream.h>
#include<conio.h>
class avl
{
private:
  struct node
{
int data;
node *left,*right;
int ht;
};
public:
node *avlroot;
node *insert1(node *,int);
node *delete1(node *,int);
void preorder1(node *);
void inorder1(node *);
int height(node*);
node *rotateright(node *);
node *rotateleft(node *);
node *rr(node *);
node *ll(node *);
node *rl(node *);
node *lr(node *);
int bf(node *);

avl()
{
avlroot=NULL;
}
void insert(int x)
{
avlroot=insert1(avlroot,x);
}
void delet(int x)
{
avlroot=delete1(avlroot,x);
}
void preorder()
{
preorder1(avlroot);
}
void inorder()
{
inorder1(avlroot);
}

void levelwise();

void makenull()
{

avlroot=NULL;
}

};
node *avl::insert1(node *t,int x)
{
if(t==NULL)
{
t=new node;

t->data=x;
t->left=NULL;
t->right=NULL;
}
else
if(x>t->data)
{
t->right=insert1(t->right,x);
if(bf(t)==-2)
if(x>t->right->data)
t=rr(t);
else
t=rl(t);
}
else
if(x<t->data)
{
t->left=insert1(t->left,x);
if(bf(t)==2)
if(x<t->left->data)
t=ll(t);
else
t=lr(t);
}
t->ht=height(t);
return(t);
}

node *avl::delete1(node *t,int x)
{
node *p;
if(t==NULL)
{
return NULL;
}
else
if(x>t->data)
{
t->right=delete1(t->right,x);
if(bf(t)==2)
if(bf(t->left)>=0)
t=ll(t);
else
t=lr(t);
}
else
if(x<t->data)
{
t->left=delete1(t->left,x);
if(bf(t)==-2)
if(bf(t->right)<=0)
t=rr(t);
else
t=rl(t);
}
else
{
if(t->right!=NULL)
{
p=t->right;
while(p->left!=NULL)
p=p->left;

t->data=p->data;
t->right=delete1(t->right,p->data);
if(bf(t)==2)
if(bf(t->left)>=0)
t=ll(t);
else
t=lr(t);
}
else
return(t->left);
}
t->ht=height(t);
return(t);
}

int avl::height(node *t)
{
   int lh,rh;
   if(t==NULL)
   return(0);
   if(t->left==NULL)
   lh=0;
   else
   lh=1+t->left->ht;
   if(t->right==NULL)
   rh=0;
   else
   rh=1+t->right->ht;
   if(lh>rh)
      return(lh);

   return(rh);
}
node *avl::rotateright(node *x)
{
  node *y;
  y=x->left;
  x->left=y->right;
  y->right=x;
  x->ht=height(x);
  y->ht=height(y);
  return(y);
}

node *avl::rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}

node *avl::rr(node *t)
{
t=rotateleft(t);
return(t);
}
node *avl::ll(node *t)
{
t=rotateright(t);
return(t);
}

node *avl::lr(node *t)
{
t->left=rotateleft(t->left);
t=rotateright(t);
return(t);
}

node *avl::rl(node *t)
{
t->right=rotateright(t->right);
t=rotateleft(t);
return(t);
}

int avl::bf(node *t)
{
int lh,rh;
if(t==NULL)
return(0);
if(t->left==NULL)
lh=0;
else
lh=1+t->left->ht;
if(t->right==NULL)
rh=0;
else
rh=1+t->right->ht;
return(lh-rh);
}

void avl::preorder1(node *t)
{
if(t!=NULL)
{
cout<<" "<<t->data<<"(bf="<<bf(t)<<")";
preorder1(t->left);
preorder1(t->right);
}
}

void avl::inorder1(node *t)
{
if(t!=NULL)
{
inorder1(t->left);
cout<<" "<<t->data<<"(bf="<<bf(t)<<")";
inorder1(t->right);
}
}

void main()
{
   avl a;
   int x,n,i,ch;
   char choice;
   clrscr();
   do
   {
cout<<"\n1.create\n2.print\n3.insert\n4.delete\n5.quit\n";
cout<<"\n Enter your choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\n Enter the no.of elements:";
cin>>n;
cout<<"\n Enter tree data:";
a.makenull();
for(i=0;i<n;i++)
{
cin>>x;
a.insert(x);
}
break;

case 2:
cout<<"\npreorder sequence:\n";
a.preorder();
cout<<"\nInorder sequence:\n";
    a.inorder();
    break;
case 3:
cout<<"\nEnter the data:";
cin>>x;
a.insert(x);
break;

case 4:
cout<<"\n Enter the data:";
cin>>x;
a.delet(x);
break;


    }
    cout<<"do u want to continue y/n:";
    cin>>choice;
  }while(choice=='y');

}