AVL tree is a balanced tree.
DEFINITION: An AVL tree is a binary search tree with the additional
balance property that, for any node in the tree, the height of the left and
right subtrees can differ by at most 1. As usual, the height of an empty
subtree is -1.
#include<iostream>
using namespace std;
struct avlnode //node structure of node
{ int data;
avlnode *lchild;
avlnode *rchild;
};
int height(avlnode *t) //height of node
{
if(t==NULL)
return -1;
else
{
int a=height(t->lchild);
int b=height(t->rchild);
if(a>b)
return a+1;
else return b+1;
}
}
avlnode *rotatelchild(avlnode *t) //rotate left
{
char k1,k2;
k1=t->data;
k2=t->rchild->data;
t->data=k2;
t->lchild->data=k1;
t->rchild=t->rchild->rchild;
return t;
}
avlnode *rotaterchild(avlnode *t) //rotate right
{
char k1,k2;
k1=t->data;
k2=t->lchild->data;
t->data=k2;
t->rchild->data=k1;
t->lchild=t->lchild->lchild;
return t;
}
void doublerotatelchild(avlnode *&k3) //double rotation right to left
{
rotaterchild(k3->lchild);
rotatelchild(k3);
}
void doublerotaterchild(avlnode *&k3) //double rotation left to right
{
rotatelchild(k3->rchild);
rotaterchild(k3);
}
void creatavltree(avlnode *&t,int k)
{
if(t==NULL)
{
t=new(avlnode);
t->data=k;
t->lchild=NULL;
t->rchild=NULL;
}
else if(k<t->data)
{
creatavltree(t->lchild,k);
if((height(t->lchild)-height(t->rchild))==2||height(t->lchild)-height(t->rchild)==-2)
{
if(k<t->lchild->data)
rotatelchild(t);
else doublerotatelchild(t);
}
}
else if(k>t->data)
{
creatavltree(t->rchild,k);
if((height(t->rchild)-height(t->lchild))==2||height(t->rchild)-height(t->lchild)==-2)
{
if(t->rchild->data<k)
rotaterchild(t);
else doublerotaterchild(t);
}
}
}
void printpreorder(avlnode *t)
{
if(t!=NULL)
{
cout<<t->data<<" ";
printpreorder(t->lchild);
printpreorder(t->rchild);
}
}
int main()
{
avlnode *t;
t=NULL;
int d,h;
cout<<"enter the elements of avl tree and -1 to terminate"<<endl;
cin>>d;
while(d!=-1)
{
creatavltree(t,d);
cin>>d;
}
cout<<"\nthe height of avl tree is\n";
h=height(t);
cout<<h<<endl;
cout<<"\nthe elements of avl tree is\n";
printpreorder(t);
return 0;
}
DEFINITION: An AVL tree is a binary search tree with the additional
balance property that, for any node in the tree, the height of the left and
right subtrees can differ by at most 1. As usual, the height of an empty
subtree is -1.
#include<iostream>
using namespace std;
struct avlnode //node structure of node
{ int data;
avlnode *lchild;
avlnode *rchild;
};
int height(avlnode *t) //height of node
{
if(t==NULL)
return -1;
else
{
int a=height(t->lchild);
int b=height(t->rchild);
if(a>b)
return a+1;
else return b+1;
}
}
avlnode *rotatelchild(avlnode *t) //rotate left
{
char k1,k2;
k1=t->data;
k2=t->rchild->data;
t->data=k2;
t->lchild->data=k1;
t->rchild=t->rchild->rchild;
return t;
}
avlnode *rotaterchild(avlnode *t) //rotate right
{
char k1,k2;
k1=t->data;
k2=t->lchild->data;
t->data=k2;
t->rchild->data=k1;
t->lchild=t->lchild->lchild;
return t;
}
void doublerotatelchild(avlnode *&k3) //double rotation right to left
{
rotaterchild(k3->lchild);
rotatelchild(k3);
}
void doublerotaterchild(avlnode *&k3) //double rotation left to right
{
rotatelchild(k3->rchild);
rotaterchild(k3);
}
void creatavltree(avlnode *&t,int k)
{
if(t==NULL)
{
t=new(avlnode);
t->data=k;
t->lchild=NULL;
t->rchild=NULL;
}
else if(k<t->data)
{
creatavltree(t->lchild,k);
if((height(t->lchild)-height(t->rchild))==2||height(t->lchild)-height(t->rchild)==-2)
{
if(k<t->lchild->data)
rotatelchild(t);
else doublerotatelchild(t);
}
}
else if(k>t->data)
{
creatavltree(t->rchild,k);
if((height(t->rchild)-height(t->lchild))==2||height(t->rchild)-height(t->lchild)==-2)
{
if(t->rchild->data<k)
rotaterchild(t);
else doublerotaterchild(t);
}
}
}
void printpreorder(avlnode *t)
{
if(t!=NULL)
{
cout<<t->data<<" ";
printpreorder(t->lchild);
printpreorder(t->rchild);
}
}
int main()
{
avlnode *t;
t=NULL;
int d,h;
cout<<"enter the elements of avl tree and -1 to terminate"<<endl;
cin>>d;
while(d!=-1)
{
creatavltree(t,d);
cin>>d;
}
cout<<"\nthe height of avl tree is\n";
h=height(t);
cout<<h<<endl;
cout<<"\nthe elements of avl tree is\n";
printpreorder(t);
return 0;
}
No comments:
Post a Comment