//**************************************
//     
// Name: AVL Rotation
// Description:Illustrates AVL tree rota
//     tion
// By: Adri Jovin
//
//This code is copyrighted and has// limited warranties.Please see http://
//     www.Planet-Source-Code.com/vb/scripts/Sh
//     owCode.asp?txtCodeId=12927&lngWId=3//for details.//**************************************
//     

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
class avltree;
class avlnode


    {
    public:
    int element,ht;
    avlnode *left,*right;
    friend class avltree;
}*root;

class avltree


    {
    public:
    int max(int,int);
    int height(avlnode *t);
    void inorder(avlnode *&t);
    void preorder(avlnode *&t);
    void insert(avlnode *&t,int x);
    void s_rotate_left(avlnode *&t);
    void s_rotate_right(avlnode *&t);
    void d_rotate_left(avlnode *&t);
    void d_rotate_right(avlnode *&t);
};

int avltree::max(int v1,int v2)


    {
    return((v1>v2)?v1:v2);
}

int avltree::height(avlnode *t)


    {
    return(t==NULL?-1:t->ht);
}

void avltree::insert(avlnode *&t,int x)


    {
    if(t==NULL)


        {
        t=new avlnode;
        t->left=NULL;
        t->right=NULL;
        t->ht=NULL;
        t->element=x;
    }

    else if(x<t->element)


        {
        insert(t->left,x);
        if(height(t->left)-height(t->right)==2)


            {
            if(x<t->left->element)
            s_rotate_left(t);
            else
            d_rotate_left(t);
        }

    }

    else if(x>t->element)


        {
        insert(t->right,x);
        if(height(t->right)-height(t->left)==2)


            {
            if(x>t->right->element)
            s_rotate_right(t);
            else
            d_rotate_right(t);
        }

    }

    t->ht=max(height(t->left),height(t->right))+1;
}

void avltree::s_rotate_left(avlnode *&k2)


    {
    avlnode *k1;
    k1=k2->left;
    k2->left=k1->right;
    k1->right=k2;
    k2->ht=max(height(k2->left),height(k2->right))+1;
    k1->ht=max(height(k1->left),k2->ht)+1;
    k2=k1;
    cout<<"\nSINGLE ROATION LEFT\n";
}

void avltree::s_rotate_right(avlnode *&k2)


    {
    avlnode *k1;
    k1=k2->right;
    k2->right=k1->left;
    k1->left=k2;
    k2->ht=max(height(k1->right),height(k1->left))+1;
    k1->ht=max(height(k1->right),k2->ht)+1;
    k2=k1;
    cout<<"\n SINGLY ROTATION RIGHT:\n";
}

void avltree::d_rotate_left(avlnode *&k3)


    {
    s_rotate_right(k3->left);
    s_rotate_left(k3);
}

void avltree::d_rotate_right(avlnode *&k3)


    {
    s_rotate_left(k3->right);
    s_rotate_right(k3);
}

void avltree::inorder(avlnode *&t)


    {
    if(t!=NULL)


        {
        cout<<t->element<<"\t";
        inorder(t->right);
    }

}

void avltree::preorder(avlnode *&t)


    {
    if(t!=NULL)


        {
        cout<<t->element<<"\t";
        preorder(t->left);
        preorder(t->right);
    }

}

void main()


    {
    avltree a1;
    int n,ch,opt,num;
    root=NULL;
    clrscr();
    do


        {
        cout<<"\n AVL ROTATIONS\n";
        cout<<"\n1.Insertion\t2.Display\t3.Exit\n";
        cout<<"Enter your choice:\n";
        cin>>ch;
        switch(ch)


            {
            case 1:
            cout<<"Enter the number to insert\n";
            cin>>num;
            a1.insert(root,num);
            break;
            case 2:
            cout<<"Display\n";
            cout<<"\n1.Inorder 2.Preorder 3.Back to main menu\n";
            do


                {
                cout<<"Enter your choice\n";
                cin>>opt;
                switch(opt)


                    {
                    case 1:
                    a1.inorder(root);
                    break;
                    case 2:
                    a1.preorder(root);
                    break;
                    case 3:
                    cout<<"Back to main menu\n";
                    break;
                }

            }

            while(opt!=3);
            break;
            case 3:
            exit(0);
        }

    }

    while(ch!=4);
    getch();
}