Friday, September 25, 2015

Implementation of AVL tree in C

#include<stdio.h>
#include<stdlib.h>
int kk;
typedef struct node{
int key;
int height;
struct node * left;
struct node * right;
}node;

node * create(node * n,int k)
{ n=(node *)malloc(sizeof(node));
  kk=k;
  n->key=k;
  n->height=1;
  n->left=NULL;
  n->right=NULL;
  return n;
}

int max(int a,int b){return (a<b)?b:a;}

node *updateheight(node *n )
{
  if(n->left!=NULL&&n->right!=NULL)
  {n->height=max(n->left->height,n->right->height)+1;printf("height updated\n");}
  else if(n->left!=NULL)
  {n->height=n->left->height;printf("height updated\n");}
  else if(n->right!=NULL)
  {n->height=n->right->height;printf("height updated\n");}
  else
  n->height=1;

  return n;
}
node * rotateR(node * r)
{
 
  node *n=r->left;
  node *temp;
  if(r->left->right!=NULL)
    temp=r->left->right;
  else temp=NULL;
  n->right=r;
  r->left=temp;
  if(n->right!=NULL)
  n->right=updateheight(n->right);
  n=updateheight(n);
  printf(".R.");
 return n;
 
}
node * rotateL(node * r)
{ node *n=r->right;
  node *temp;
  if(r->right->left!=NULL)
  temp=r->right->left;
  else temp =NULL;
  n->left=r;
  r->right=temp;
  updateheight(n->left);
  updateheight(n);
  printf(".L.");
  return n;

}

node * balance(node *n,int k)
{ int balance,l=0,r=0;
   if(n->left)
     l=n->left->height;
   if(n->right)
     r=n->right->height;
   balance=l-r;
     if(balance>1&&k<=n->left->key)
        {n=rotateR(n);printf("LL..");}
     else if(balance>1&&k>n->left->key)
       {printf("LR..");n=rotateL(n);n=rotateR(n);}
     else if(balance<-1&&k>n->right->key)
       {n=rotateL(n);printf("RR..");}
     else if(balance<-1&&k<=n->left->key)
       {n=rotateR(n);n=rotateL(n);printf("RL..");}

  return n;

}

node * insert(node * r,int k)
{
   if(r==NULL){node *n=create(n,k);r=n;}
   else if(k<=r->key){r->left=insert(r->left,k);r->height=r->left->height+1;r=balance(r,kk);}
   else if(k>r->key){r->right=insert(r->right,k);r->height=r->right->height+1;r=balance(r,kk);}
   return r;
}
void printAVLIO(node *r)
{
    if(!r)return;
    if(r->left)printAVLIO(r->left);
    printf("\n%d..",r->key);
    printf(".height.%d..\n",r->height);
    if(r->right)printAVLIO(r->right);
}

int main()
{
  node *root=NULL;
  int i,a[]={50,25,75,70,60},k=sizeof(a)/sizeof(int);
  printf("Inseting sequence into the AVL tree\n");
  for(i=0;i<k;i++)
     printf("%d..",a[i]);printf("\n");
  i=0;
  while(i<k)
     {root=insert(root,a[i]);i++;}
  printAVLIO(root);
return 0;
}