/******************************************************
NAME : JABIR DAUD PATHAN
PROGRAM : IMPLEMENTATION OF AVL TREE
*******************************************************/
/*---------------<< Header File
>>------------------*/
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct
node
{
int data;
node *left,*right;
int ht;
};
/*----------<< Declaration of class AVL >>---------*/
class
avl
{
private :
node*root;
node*ll(node*);
node*rr(node*);
node*lr(node*);
node*rl(node*);
node*rotateright(node*);
node*rotateleft(node*);
int height(node*);
int bf(node*);
public
:
avl() // Default constructor
{
root=NULL;
}
node*create();
node*insert(node*,int);
node*del(node*,int);
void preorder(node*);
void inorder(node*);
void postorder(node*);
};
/*-------<<
Function defination for Right Rotation >>---------*/
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;
}
/*-------<<
Function defination for Left Rotation >>--------*/
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;
}
/*-------<<
Function defination for RR Rotation >>---------*/
node*avl::rr(node*t)
{
t=rotateleft(t);
return t;
}
/*-------<<
Function defination for LL Rotation >>---------*/
node*avl::ll(node*t)
{
t=rotateright(t);
return t;
}
/*-------<<
Function defination for LR Rotation >>--------*/
node*avl::lr(node*t)
{
t->left=rotateleft(t->left);
t=rotateright(t);
return t;
}
/*-------<<
Function defination for RL Rotation >>--------*/
node*avl::rl(node*t)
{
t->right=rotateright(t->right);
t=rotateleft(t);
return t;
}
/*-------<<
Function defination for Height >>--------*/
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);
}
/*----<<Function
defination for Calculate Balance Factor>>---*/
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);
}
/*--------<<
Function defination for create >>----------*/
node*avl::create()
{
avl a;
int n,x,i;
cout<<"\nEnter no.of nodes
:";
cin>>n;
cout<<"\nEnter the root node :
" ;
cin>>x;
root=insert(root,x);
for(i=1;i<n;i++)
{
cout<<"\nEnter the data : "
;
cin>>x;
root=a.insert(root,x);
}
return root;
}
/*-------<<
Function defination for Insert node >>--------*/
node*avl::insert(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=insert(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=insert(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;
}
/*--------<< Function defination for Delete node
>>--------*/
node*avl::del(node
*t,int x)
{
node *p;
if(t==NULL)
{
return NULL;
}
else
if(x > t->data)
{
t->right=del(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=del(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=del(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;
}
/*------<<
Function defination for Preorder Traversal >>-------*/
void
avl::preorder(node *t)
{
if(t!=NULL)
{
cout<<t->data<<"
(BF="<<bf(t)<<") "<<" ";
preorder(t->left);
preorder(t->right);
}
}
/*-------<<
Function defination for Inorder Traversal >>-------*/
void
avl::inorder(node *t)
{
if(t!=NULL)
{
inorder(t->left);
cout<<t->data<<"
(BF="<<bf(t)<<") "<<" ";
inorder(t->right);
}
}
/*-------<<
Function defination for Postorder Traversal >>-------*/
void
avl::postorder(node *t)
{
if(t!=NULL)
{
postorder(t->left);
postorder(t->right);
cout<<t->data<<"
(BF="<<bf(t)<<") "<<" ";
}
}
/*-----------<< Main Function Starts >>---------*/
void
main()
{
avl a;
node*root,*temp;
int ch,n,x,i;
char ans;
do
{
clrscr();
cout<<"\n\n\n\t\t\t------<<
MENU >>--------";
cout<<"\n\n\t\t\t1.Create ";
cout<<"\n\n\t\t\t2.Display ";
cout<<"\n\n\t\t\t3.Insert";
cout<<"\n\n\t\t\t4.Delete";
cout<<"\n\n\t\t\t5.Exit";
cout<<"\n\n\t\t\t-----------------------";
cout <<"\n\n\t\t\tEnter Your
Choice : ";
cin>>ch;
switch(ch)
{
case 1:
root=a.create();
break;
case 2:
cout<<"\nPreorder Traversal :\n\n";
a.preorder(root);
cout<<"\n\n\nInorder Traversal :\n\n";
a.inorder(root);
cout<<"\n\n\nPostorder Traversal :\n\n";
a.postorder(root);
break;
case 3:
cout<<"\nEnter the node that you want to insert in avl tree :
";
cin>>x;
root=a.insert(root,x);
break;
case 4:
cout<<"\nEnter the node that you want to delete from avl tree
: ";
cin>>x;
a.del(root,x);
break;
case 5:
exit(0);
break;
}
cout<<"\n\n\n\tDo you want to
continue(y/n): ";
ans=getche();
}while(ans=='y'||ans=='Y');
getch();
}
/*--------<< End Of Main Function >>------------*/
/*-----------------<< OUTPUT
SCREEN >>-------------------*/
------<< MENU
>>--------
1.Create
2.Display
3.Insert
4.Delete
5.Exit
-----------------------
Enter Your Choice : 1
Enter
no.of nodes :12
Enter
the root node : 30
Enter
the data : 31
Enter
the data : 32
Enter
the data : 23
Enter
the data : 22
Enter
the data : 28
Enter
the data : 24
Enter
the data : 29
Enter
the data : 26
Enter
the data : 27
Enter
the data : 34
Enter
the data : 36
Do you want to continue(y/n):y
------<< MENU
>>--------
1.Create
2.Display
3.Insert
4.Delete
5.Exit
-----------------------
Enter Your Choice : 2
Preorder
Traversal :
28
(BF=0) 24 (BF=0) 23 (BF=1)
22 (BF=0) 26 (BF=-1) 27 (BF=0)
32 (BF=0)
30
(BF=0) 29 (BF=0) 31 (BF=0)
34 (BF=-1) 36 (BF=0)
Inorder
Traversal :
22
(BF=0) 23 (BF=1) 24 (BF=0)
26 (BF=-1) 27 (BF=0) 28 (BF=0)
29 (BF=0)
30
(BF=0) 31 (BF=0) 32 (BF=0)
34 (BF=-1) 36 (BF=0)
Postorder
Traversal :
22
(BF=0) 23 (BF=1) 27 (BF=0)
26 (BF=-1) 24 (BF=0) 29 (BF=0)
31 (BF=0)
30
(BF=0) 36 (BF=0) 34 (BF=-1)
32 (BF=0) 28 (BF=0)
Do you want to continue(y/n):y
------<< MENU
>>--------
1.Create
2.Display
3.Insert
4.Delete
5.Exit
-----------------------
Enter Your Choice : 3
Enter
the node that you want to insert in avl tree : 40
Do you want to continue(y/n):y
------<< MENU
>>--------
1.Create
2.Display
3.Insert
4.Delete
5.Exit
-----------------------
Enter Your Choice : 2
Preorder
Traversal :
28
(BF=0) 24 (BF=0) 23 (BF=1)
22 (BF=0) 26 (BF=-1) 27 (BF=0)
32 (BF=0)
30
(BF=0) 29 (BF=0) 31 (BF=0)
36 (BF=0) 34 (BF=0) 40 (BF=0)
Inorder
Traversal :
22
(BF=0) 23 (BF=1) 24 (BF=0)
26 (BF=-1) 27 (BF=0) 28 (BF=0)
29 (BF=0)
30
(BF=0) 31 (BF=0) 32 (BF=0)
34 (BF=0) 36 (BF=0) 40 (BF=0)
Postorder
Traversal :
22
(BF=0) 23 (BF=1) 27 (BF=0)
26 (BF=-1) 24 (BF=0) 29 (BF=0)
31 (BF=0)
30
(BF=0) 34 (BF=0) 40 (BF=0)
36 (BF=0) 32 (BF=0) 28 (BF=0)
Do you want to continue(y/n):y
------<< MENU
>>--------
1.Create
2.Display
3.Insert
4.Delete
5.Exit
-----------------------
Enter Your Choice : 4
Enter
the node that you want to delete from avl tree : 28
Do you want to continue(y/n):y
------<< MENU
>>--------
1.Create
2.Display
3.Insert
4.Delete
5.Exit
-----------------------
Enter Your Choice : 2
Preorder
Traversal :
29
(BF=0) 24 (BF=0) 23 (BF=1)
22 (BF=0) 26 (BF=-1) 27 (BF=0)
32 (BF=0)
30
(BF=-1) 31 (BF=0) 36 (BF=0)
34 (BF=0) 40 (BF=0)
Inorder
Traversal :
22
(BF=0) 23 (BF=1) 24 (BF=0)
26 (BF=-1) 27 (BF=0) 29 (BF=0)
30 (BF=-1)
31
(BF=0) 32 (BF=0) 34 (BF=0)
36 (BF=0) 40 (BF=0)
Postorder
Traversal :
22
(BF=0) 23 (BF=1) 27 (BF=0)
26 (BF=-1) 24 (BF=0) 31 (BF=0)
30 (BF=-1)
34
(BF=0) 40 (BF=0) 36 (BF=0)
32 (BF=0) 29 (BF=0)
Do you want to continue(y/n):y
------<< MENU
>>--------
1.Create
2.Display
3.Insert
4.Delete
5.Exit
-----------------------
Enter Your Choice : 5
/********************************************************/
No comments:
Post a Comment