AVL Balance Tree in C++

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;
}
    }


    }

Share this

Programming Seeker