AVL Search Tree Insertion (Height-Balanced Tree)

#include<stdio.h>
#include<malloc.h>

struct tree
{
        int data;
        struct tree *left,*right,*par;
}*head=NULL,*r=NULL,*p=NULL,*q=NULL,*tmp=NULL;

max(int a,int b)
{
        if(a>b)
                return a;
        else
                return b;
}

height(struct tree *t)
{
        if(t==NULL)
                return 0;
        else
                return (max(height(t->left),height(t->right))+1);

}

ll()
{
        q->left=p->right;
        if(q->left!=NULL)
        q->left->par=q;
        r=q->par;
        p->right=q;
        q->par=p;
        p->par=r;



        if(r==NULL)
                head=p;
        else if(r->left==q)
                r->left=p;
        else
        {
                r->right=p;
        }
}


rr()
{
        q->right=p->left;
        r=q->par;
        p->left=q;
        q->par=p;
        p->par=r;
        if(q->right!=NULL)
        q->right->par=q;



        if(r==NULL)
                head=p;
        else if(r->left==q)
                r->left=p;
        else
        {
                r->right=p;
        }
}


rl()
{

        r=q->par;

        if(r==NULL)
                head=tmp;
        else if(r->left==q)
                r->left=tmp;
        else
        {
                r->right=tmp;
        }

        p->left=tmp->right;
        q->right=tmp->left;
        tmp->par=r;
        tmp->right=p;
        tmp->left=q;
        p->par=tmp;
        q->par=tmp;
        if(p->left!=NULL)
        p->left->par=p;
        if(q->right!=NULL)
        q->right->par=q;
}

lr()
{

        r=q->par;

        if(r==NULL)
                head=tmp;
        else if(r->left==q)
                r->left=tmp;
        else
        {
                r->right=tmp;
        }

        p->right=tmp->left;
        q->left=tmp->right;
        tmp->par=r;
        tmp->left=p;
        tmp->right=q;
        p->par=tmp;
        q->par=tmp;
        if(p->right!=NULL)
        p->right->par=p;
        if(q->left!=NULL)
        q->left->par=q;
}

insert()
{
        printf("Enter the data: ");
        int num;
        scanf("%d",&num);

        tmp=malloc(sizeof(struct tree));
        tmp->data=num;
        tmp->left=NULL;
        tmp->right=NULL;
        tmp->par=NULL;

        p=head;
        q=p;
        while(p!=NULL)
        {
                if(num>p->data)
                {
                        q=p;
                        p=p->right;
                }
                else
                {
                        q=p;
                        p=p->left;
                }

        }
        if(q==NULL)
        {
                tmp->par=q;
                head=tmp;
        }


        else if(num>q->data)
        {
                tmp->par=q;
                q->right=tmp;
        }
        else
        {
                tmp->par=q;
                q->left=tmp;
        }
        //balancing;

        p=tmp;

        while(q!=NULL)
        {
                int fac=height(q->left)-height(q->right);
                if(fac>1)
                {
                        if(p->left==tmp)
                                ll();
                        else if(p->right==tmp)
                                lr();
                }
                else if(fac<-1)
                {
                        if(p->right==tmp)
                                rr();
                        else if(p->left==tmp)
                                rl();
                }
                tmp=p;
                p=q;
                q=q->par;



        }



}


inorder(struct tree *node)
{

        if(node->left!=0)
                inorder(node->left);
        printf("%d ",node->data);
        if(node->right!=0)
                inorder(node->right);
}

main()
{
        int ch=1;

        while(ch!=0)
        {

                insert();
                printf("\nINorder traversal\n");
                inorder(head);

                printf("\nwanna enter data (0=no,1=yes) :");
                scanf("%d",&ch);
        }
}

OUTPUT:-