C++ program to implement AVL tree

C++ program to implement AVL-tree

#include<iostream>
#include<stdlib.h>
using namespace std;
struct tree_node
{
    int data,bal;
    tree_node *left,*right;
};
class avl_tree
{
    int item,flag;
    tree_node *root,*suc;
    tree_node* ll_rotation(tree_node *);
    tree_node* rr_rotation(tree_node *);
    tree_node* lr_rotation(tree_node *);
    tree_node* rl_rotation(tree_node *);
    void put_in_parent(tree_node *parent,tree_node *temp,tree_node *temp1)
    {
        if(parent->left==temp)
            parent->left=temp1;
        else
            parent->right=temp1;
    }
public:
    avl_tree()
    {
        root=NULL;
        flag=0;
        suc=NULL;
    }
    void getdata();
    void insert(tree_node *,tree_node *);
    void delete_node(tree_node*,tree_node*);
    void search();
    void display(tree_node *);
    tree_node* getroot()
    {
        return root;
    }
};
tree_node* avl_tree::ll_rotation(tree_node *temp)
{
    tree_node *temp1;
    temp1=temp->left;
    temp->left=temp1->right;
    temp1->right=temp;
    return temp1;
}
tree_node* avl_tree::rr_rotation(tree_node *temp)
{
    tree_node *temp1;
    temp1=temp->right;
    temp->right=temp1->left;
    temp1->left=temp;
    return temp1;
}
tree_node* avl_tree::lr_rotation(tree_node *temp)
{
    tree_node *temp1=temp->left;
    if((temp1->right)->bal==0||(temp1->right)->bal==-1)
        temp1->bal=0;
    else
        temp1->bal=-1;
    if(((temp1->right)->bal==0||(temp1->right)->bal==-1)&&temp->right!=NULL&&(temp1->right)->right==NULL)
        temp->bal=1;
    else
        temp->bal=0;
    (temp1->right)->bal=0;
    temp1=rr_rotation(temp->left);
    temp->left=temp1;
    return ll_rotation(temp);
}
tree_node* avl_tree::rl_rotation(tree_node *temp)
{
    tree_node* temp1=temp->right;
    if((temp1->left)->bal==0||(temp1->left)->bal==1)
        temp1->bal=0;
    else
        temp1->bal=1;
    if(((temp1->left)->bal==0||(temp1->left)->bal==1)&&temp->left!=NULL&&(temp1->left)->left==NULL)
        temp->bal=-1;
    else
        temp->bal=0;
    (temp1->left)->bal=0;
    temp1=ll_rotation(temp->right);
    temp->right=temp1;
    return rr_rotation(temp);
}
void avl_tree::getdata()
{
    cout<<"Enter the element ";
    cin>>item;
}
void avl_tree::insert(tree_node *temp,tree_node *parent)
{
    if(temp==NULL)
    {
        tree_node *ne;
        ne=new tree_node;
        ne->data=item;
        ne->right=ne->left=NULL;
        ne->bal=0;
        if(parent==temp)
        {
            root=ne;
            return;
        }
        else if(parent->data<item)
            parent->right=ne;
        else
            parent->left=ne;
        flag=1;
        return;
    }
    else if(item<temp->data)
    {
        insert(temp->left,temp);
        if(flag)
            temp->bal--;
        if(temp->bal==0)
            flag=0;
    }
    else if(item>temp->data)
    {
        insert(temp->right,temp);
        if(flag)
            temp->bal++;
        if(temp->bal==0)
            flag=0;
    }
    else
    {
        cout<<"Duplicate values not allowed ";
        return;
    }
    if(abs(temp->bal)>1)
    {
        tree_node* temp1;
        if(temp->data>item&&(temp->left)!=NULL)
        {
            if((temp->left)->data>item)
            {
                temp->bal=0;
                temp1=ll_rotation(temp);
                temp1->bal=0;
            }
            else
                temp1=lr_rotation(temp);
        }
        else if(temp->data<item&&(temp->right)->data<item)
        {
            temp->bal=0;
            temp1=rr_rotation(temp);
            temp1->bal=0;
        }
        else if(temp->data<item&&(temp->right)->data>item)
            temp1=rl_rotation(temp);
        if(temp!=root)
            put_in_parent(parent,temp,temp1);
        else
            root=temp1;
        flag=0;
    }
}
void avl_tree::delete_node(tree_node *temp,tree_node *parent)
{
    if(temp==NULL)
    {
        cout<<"Element not found ";
        flag=0;
        return ;
    }
    else if(temp->left==NULL&&suc!=NULL)
    {
        suc->data=temp->data;
        parent->left=temp->right;
        delete temp;
        suc=temp=NULL;
        flag=1;
    }
    else if(temp->data==item)
    {
        if(temp==root&&root->right==NULL)
        {
            root=root->left;
            delete temp;
            temp=NULL;
        }
        else if(temp==root&&root->left==NULL)
        {
            root=root->right;
            delete temp;
            temp=NULL;
        }
       else if(temp->left!=NULL&&temp->right!=NULL)
       {
           if((temp->right)->left==NULL)
           {
               tree_node *temp1;
               temp1=temp->right;
               temp->right=temp1->right;
               temp->data=temp1->data;
               delete temp1;
               --temp->bal;
               if(temp->bal==0)
                  flag=1;
           }
           else
           {
               suc=temp;
               delete_node(temp->right,temp);
               if(flag)
                  temp->bal--;
               if(temp->bal==0)
                  flag=1;
               else
                  flag=0;
           }
       }
       else
       {
           if(temp->left==NULL&&temp->right==NULL)
               put_in_parent(parent,temp,NULL);
           else if(temp->left==NULL)
               put_in_parent(parent,temp,temp->right);
           else
               put_in_parent(parent,temp,temp->left);
           delete temp;
           temp==NULL;
           flag=1;
       }
       cout<<"Element Successfully deleted "<<endl;
    }
    else if(item<temp->data||suc!=NULL)
    {
        delete_node(temp->left,temp);
        if(flag)
            temp->bal++;
        if(temp->bal==1)
            flag=0;
    }
    else if(item>temp->data)
    {
        delete_node(temp->right,temp);
        if(flag)
            temp->bal--;
        if(temp->bal==1)
            flag=0;
    }
    if(temp==NULL)
        return;
    if(abs(temp->bal)==2)
    {
        tree_node* temp1;
        switch(temp->bal)
        {
        case 2:
            switch((temp->right)->bal)
            {
            case -1:
                temp1=rl_rotation(temp);
                flag=1;
                break;
            case 0:
                temp->bal=1;
                (temp->right)->bal=-1;
                flag=0;
                temp1=rr_rotation(temp);
                break;
            case 1:
                temp->bal=0;
                (temp->right)->bal=0;
                flag=1;
                temp1=rr_rotation(temp);
                break;
            }
            break;
        case -2:
            switch((temp->left)->bal)
            {
            case 1:
                temp1=lr_rotation(temp);
                flag=1;
                break;
            case 0:
                temp->bal=-1;
                (temp->left)->bal=1;
                flag=0;
                temp1=ll_rotation(temp);
                break;
            case -1:
                temp->bal=0;
                (temp->left)->bal=0;
                flag=1;
                temp1=ll_rotation(temp);
                break;
            }
            break;
        }
        if(temp!=root)
            put_in_parent(parent,temp,temp1);
        else
            root=temp1;
    }
}
void avl_tree::search()
{
    tree_node *temp=root,*parent=NULL;
    int flag=1;
    while(temp!=NULL)
    {
        if(temp->data==item)
        {
            cout<<"Element is present "<<endl;
            if(parent!=NULL)
                cout<<"Parent node of "<<item<<" is "<<parent->data<<endl;
            return;
        }
        parent=temp;
        if(item<temp->data)
            temp=temp->left;
        else
            temp=temp->right;
    }
    cout<<"Element is not present ";
}
void avl_tree::display(tree_node *temp)
{
    if(temp==NULL)
        return;
    display(temp->left);
    cout<<temp->data<<" "<<temp->bal<<" | ";
    display(temp->right);
}
int main()
{
    avl_tree tree;
    int a,flag=1;
    while(flag)
    {
        cout<<"Main Menu\n\t1.) Insertion\n\t2.) Deletion\n\t3.) Search\n\t4.) Display\n\t5.) Exit";
        cout<<"\nEnter your choice ";
        cin>>a;
        switch(a)
        {
        case 1:
            tree.getdata();
            tree.insert(tree.getroot(),tree.getroot());
            break;
        case 2:
            tree.getdata();
            tree.delete_node(tree.getroot(),tree.getroot());
            break;
        case 3:
            tree.getdata();
            tree.search();
            break;
        case 4:
            tree.display(tree.getroot());
            cout<<endl;
            break;
        case 5:
            flag=0;
            break;
        default:
            cout<<"Wrong choice "<<endl;
        }
    }
}