#include<iostream.h>
#include<stdlib.h>
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 *);
void remove2(AVLNODE *,AVLNODE *);
void search(int x);
void search1(AVLNODE *,int);
};
int AVL::insert(int x)
{
AVLNODE *a,*b,*c,*f,*p,*q,*y;
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 1; }
f=NULL;
a=p=root;
q=NULL;
found=0;
while(p&&!found)
{
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=1;
}
} //end while
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;
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;
}
unbalanced=1;
if(!(a->bf)||!(a->bf+d))
{ //tree still balanced
a->bf+=d;
unbalanced=0;
}
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
}
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 1;
} //end of if(!found)
return 0;
} //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);
else
remove2(loc,par);
}
void AVL::remove1(AVLNODE *l,AVLNODE *p)
{
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);
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)
{
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(x<ptr->data)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(flag!=1)
{
cout<<"item is not there in tree";
loc=NULL;
par=NULL;
cout<
cout<
}
}
void 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');
}
OUTPUT:
1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree1
Enter an element to insert into tree4
do u want to continuey
1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree1
Enter an element to insert into tree5
do u want to continuey
1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree3
Enter an item to deletion5
itemfound
do u want to continuey
1.insert 2.display 3.delete 4.search 5.exit
Enter u r choice to perform on AVL tree2
4
do u want to continue4
