C Program to insert and delete elements in an AVL Tree

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define FALSE 0
#define TRUE 1
struct AVLNode
{
  int data;
  int balfact;
  struct AVLNode *left;
  struct AVLNode *right;
};

struct AVLNode * insert(struct AVLNode *,int,int *);
struct AVLNode * deldata(struct AVLNode *,int,int *);
struct AVLNode * del(struct AVLNode *,struct AVLNode *,int *);
struct AVLNode * balr(struct AVLNode *,int *);
struct AVLNode * ball(struct AVLNode *,int *);
void display(struct AVLNode *);
void deltree(struct AVLNode *);
void main()
{
  struct AVLNode *avl=NULL;
  int h;
  clrscr();
  avl=insert(avl,20,&h);
  avl=insert(avl,6,&h);
  avl=insert(avl,29,&h);
  avl=insert(avl,5,&h);
  avl=insert(avl,12,&h);
  avl=insert(avl,25,&h);
  avl=insert(avl,32,&h);
  avl=insert(avl,10,&h);
  avl=insert(avl,15,&h);
  avl=insert(avl,27,&h);
 // avl=insert(avl,13,&h);
  printf("\n AVL Tree : \n");
  display(avl);
  avl=deldata(avl,5,&h);
  avl=deldata(avl,12,&h);
  printf("\n AVL tree after deletion of a node : \n");
  display(avl);
  deltree(avl);
  getch();

}



/* Inserts an element intp tree */
struct  AVLNode * insert(struct AVLNode *root,int data,int *h)
{
  struct AVLNode *node1,*node2;
  if(!root)
  {
     root=(struct AVLNode *)malloc(sizeof(struct AVLNode));
     root->data=data;
     root->left=NULL;
     root->right=NULL;
     root->balfact=0;
     *h=TRUE;
     return(root);
  }
  if(data < root->data)
  {
     root->left=insert(root->left,data,h);
     /* If left subtree is higher */
     if(*h)
     {
    switch(root->balfact)
    {
       case 1:
         node1=root->left;
         if(node1->balfact==1)
         {
           printf("\n Right Rotation alond %d. ",root->data);
           root->left=node1->right;
           node1->right=root;
           root->balfact=0;
           root=node1;
         }
         else
         {
          printf("\n Double rotation , left along %d",node1->data);
          node2=node1->right;
          node1->right=node2->left;

          printf(" then right along %d. \n",root->data);
          node2->left=node1;
          root->left=node2->right;
          node2->right=root;

          if(node2->balfact==1)
         root->balfact=-1;
          else
         root->balfact=0;
          if(node2->balfact==-1)
         node1->balfact=1;
          else
         node1->balfact=0;
          root=node2;
      }
      root->balfact=0;
      *h=FALSE;
      break;
       case 0:
         root->balfact=1;
         break;
       case -1:
         root->balfact=0;
         *h=FALSE;
      }
      }

  }

  if(data > root->data)
  {
    root->right=insert(root->right,data,h);
    /* If the right subtree is higher */
    if(*h)
    {
       switch(root->balfact)
       {
      case 1:
           root->balfact=0;
           *h=FALSE;
           break;
      case 0:
           root->balfact=-1;
           break;
      case -1:
           node1=root->right;
           if(node1->balfact==-1)
           {
          printf("\n Left rotation along %d. ",root->data);
          root->right=node1->left;
          node1->left=root;
          root->balfact=0;
          root=node1;
           }
           else
           {
          printf("\n Double rotation , right along %d",node1->data);
          node2=node1->left;
          node1->left=node2->right;
          node2->right=node1;
          printf(" then left along %d. \n",root->data);
          root->right=node2->left;
          node2->left=root;
          if(node2->balfact==-1)
             root->balfact=1;
          else
             root->balfact=0;
          if(node2->balfact==1)
             node1->balfact=-1;
          else
             node1->balfact=0;
          root=node2;
          }
          root->balfact=0;
          *h=FALSE;
    }
    }
 }
  return(root);

}


/* Deletes an item from the tree */
struct AVLNode * deldata(struct AVLNode *root,int data,int *h)
{
   struct AVLNode *node;
   if(!root)
   {
      printf("\n No such data. ");
      return (root);
   }
   else
   {
      if(data < root->data)
      {
     root->left=deldata(root->left,data,h);
     if(*h)
       root=balr(root,h);
      }
      else
      {
     if(data > root->data)
     {
        root->right=deldata(root->right,data,h);
          if(*h)
         root=ball(root,h);
     }
     else
     {
        node=root;
        if(node->right==NULL)
        {
           root=node->left;
           *h=TRUE;
           free(node);
        }
        else
        {
          node->right=del(node->right,node,h);
          if(*h)
         root=ball(root,h);
        }
      }
    }
      }

   return(root);
 }


 struct AVLNode * del(struct AVLNode *succ,struct AVLNode *node,int *h)
 {
    struct AVLNode *temp=succ;
    if(succ->left!=NULL)
    {
       succ->left=del(succ->left,node,h);
       if(*h)
      succ=balr(succ,h);
    }
    else
    {
       temp=succ;
       node->data=succ->data;
       succ=succ->right;
       free(temp);
       *h=TRUE;
    }
     return(succ);
}


/* Balance the tree , if right subtree is higher */
struct AVLNode * balr(struct AVLNode *root,int *h)
{
   struct AVLNode *node1,*node2;
   switch(root->balfact)
   {
     case 1:
    root->balfact=0;
    break;
     case 0:
    root->balfact=-1;
    *h=FALSE;
    break;
     case -1:
    node1=root->right;
    if(node1->balfact <= 0)
    {
      printf("\n Left rotation along %d. ",root->data);
      root->right=node1->left;
      node1->left=root;
      if(node1->balfact==0)
      {
          root->balfact=-1;
          node1->balfact=1;
        *h=FALSE;
      }
      else
      {
          root->balfact=node1->balfact=0;
      }
      root=node1;
    }
     else
     {
       printf("\n Double rotation , right along %d ",node1->data);
       node2=node1->left;
       node1->left=node2->right;
       node2->right=node1;
       printf(" then left along %d. \n",root->data);
       root->right=node2->left;
       node2->left=root;

       if(node2->balfact==-1)
      root->balfact=1;
       else
      root->balfact=0;
       if(node2->balfact==1)
     node1->balfact=-1;
       else
     node1->balfact=0;
       root=node2;
       node2->balfact=0;
    }
}
  return (root);
}


/* Balances the tree , if the left subtree is higher */
struct AVLNode * ball(struct AVLNode * root,int *h)
{
   struct AVLNode *node1,*node2;
   switch(root->balfact)
   {
      case -1:
     root->balfact=0;
     break;
      case 0:
     root->balfact=1;
     *h=FALSE;
     break;
      case 1:
     node1=root->left;
     if(node1->balfact >= 0)
     {
         printf("]n Right rotation along %d. ",root->data);
         root->left=node1->right;
         node1->right=root;
         if(node1->balfact==0)
         {
        root->balfact=1;
        node1->balfact=-1;
        *h=FALSE;
         }
         else
         {
           root->balfact=node1->balfact=0;
         }
         root=node1;
     }
     else
       {
      printf("\n Double rotation , left along %d ",node1->data);
      node2=node1->right;
      node1->right=node2->left;
      node2->left=node1;
      printf(" then right along %d .\n",root->data);

      root->left=node2->right;
      node2->right=root;

      if(node2->balfact==1)
          root->balfact=-1;
      else
          root->balfact=0;

      if(node2->balfact==-1)
          node1->balfact=1;
      else
          node1->balfact=0;
      root=node2;
      node2->balfact=0;
       }
    }
    return (root);
}


/*n Displays the tree in-order */
void display(struct AVLNode *root)
{
  if(root!=NULL)
  {
    display(root->left);
    printf("%d\t",root->data);
    display(root->right);
  }
}


/* Deletes the tree */
void deltree(struct AVLNode * root)
{
   if(root!=NULL)
   {
    deltree(root->left);
    deltree(root->right);
   }
   free(root);
}