AVL TREE IMPLEMENTAION:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct avl_node
{
int data;
struct avl_node *left;
struct avl_node *right;
}*root;
int max(int a,int b){
if (a>b){
return a;}
else { return b;
}
}
class avlTree
{
public:
avlTree()
{
root = NULL;
}
int height(avl_node *temp)
{
int h = 0;
if (temp != NULL)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int max_height = max (l_height, r_height);
h = max_height + 1;
}
return h;
}
int diff(avl_node *temp)
{
int l_height = height (temp->left);
int r_height = height (temp->right);
int b_factor= l_height - r_height;
return b_factor;
}
avl_node* rr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}
avl_node *ll_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}
avl_node* lr_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}
avl_node *rl_rotation(avl_node *parent)
{
avl_node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}
avl_node* balance(avl_node *temp)
{
int bal_factor = diff (temp);
if (bal_factor > 1)
{
if (diff (temp->left) > 0)
temp = ll_rotation (temp);
else
temp = lr_rotation (temp);
}
else if (bal_factor < -1)
{
if (diff (temp->right) > 0)
temp = rl_rotation (temp);
else
temp = rr_rotation (temp);
}
return temp;
}
avl_node *insert(avl_node *root, int value)
{
if (root == NULL)
{
root = new avl_node;
root->data = value;
root->left = NULL;
root->right = NULL;
return root;
}
else if (value < root->data)
{
root->left = insert(root->left, value);
root = balance (root);
}
else if (value >= root->data)
{
root->right = insert(root->right, value);
root = balance (root);
}
return root;
}
void display(avl_node *ptr, int level)
{
int i;
if (ptr!=NULL)
{
display(ptr->right, level + 1);
cout<<endl;
if (ptr == root)
cout<<"Root -> ";
for (i = 0; i < level && ptr != root; i++)
cout<<" ";
cout<<ptr->data;
display(ptr->left, level + 1);
}
}
void inorder(avl_node *tree)
{
if (tree == NULL)
return;
inorder (tree->left);
cout<<tree->data<<" ";
inorder (tree->right);
}
void preorder(avl_node *tree)
{
if (tree == NULL)
return;
cout<<tree->data<<" ";
preorder (tree->left);
preorder (tree->right);
}
void postorder(avl_node *tree)
{
if (tree == NULL)
return;
postorder ( tree ->left );
postorder ( tree ->right );
cout<<tree->data<<" ";
}
};
void main()
{
int choice, item;
avlTree avl;
clrscr();
while (1)
{
cout<<"\n\n-----------------------------------\n"<<endl;
cout<<" AVL Tree Implementation "<<endl;
cout<<"\n---------------------------------------\n"<<endl;
cout<<"[ 1. Insert Element into the tree]"<<endl;
cout<<"[ 2. Display Balanced AVL Tree ]"<<endl;
cout<<"[ 3. InOrder traversal ]"<<endl;
cout<<"[ 4. PreOrder traversal ]"<<endl;
cout<<"[ 5. PostOrder traversal ]"<<endl;
cout<<"[ 6. Exit ]"<<endl<<endl;
cout<<"[ Enter your Choice:. . . .: ";
cin>>choice;
cout<<"\n\n--------------------------------------\n\n";
switch(choice)
{
case 1:
cout<<"\nHow Many Node You want to insert: ";
cin>>choice;
for(int x=0;x<=choice;x++){
cout<<"\nEnter value to be inserted: ";
cin>>item;
root = avl.insert(root, item);}
break;
case 2:
if (root == NULL)
{
cout<<"\nTree is Empty\n"<<endl;
continue;
}
cout<<"\nBalanced AVL Tree:"<<endl;
avl.display(root, 1);
break;
case 3:
cout<<"\nInorder Traversal:"<<endl;
avl.inorder(root);
cout<<endl;
break;
case 4:
cout<<"\nPreorder Traversal:"<<endl;
avl.preorder(root);
cout<<endl;
break;
case 5:
cout<<"\nPostorder Traversal:"<<endl;
avl.postorder(root);
cout<<endl;
break;
case 6:
exit(1);
break;
default:
cout<<"\nWrong Choice\n"<<endl;
}
}
}
0 comments:
Post a Comment