Implementation of AVL Tree

In this post I will give the C program for the implementation of AVL tree.

AVL TREE

In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented.In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.

ALGORITHM

Program written based on the algorithm given in the book "Data Structures and Algorithm Analysis in C " written by Mark Allen Weiss.

PROGRAM


#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct avlnode;
typedef struct avlnode *position;
typedef struct avlnode *avltree;
struct avlnode
{
  int element;
  avltree left;
  avltree right;
  int height;
};

avltree makeempty(avltree T)
{
  if(T!=NULL)
  {
    makeempty(T->left);
    makeempty(T->right);
    free(T);
  }
  return NULL;
}

position find(int X,avltree T)
{
  if(T==NULL)
    return NULL;
  if(X<T->element)
    return find(X,T->left);
  else if(X>T->element)
    return find(X,T->right);
  else
    return T;
}

static int height(position p)
{
  if(p==NULL)
    return -1;
  else
    return p->height;
}

static int max(int lhs,int rhs)
{
  return lhs>rhs ? lhs : rhs;
}

static position singlerotatewithleft(position k2)
{
  position k1;
  k1=k2->left;
  k2->left = k1->right;
  k1->right = k2;
  k2->height = max(height(k2->left),height(k2->right))+1;
  k1->height = max(height(k1->left),k2->height)+1;
  return k1;
}

static position singlerotatewithright(position k1)
{
  position k2;
  k2=k1->right;
  k1->right = k2->left;
  k2->left = k1;
  k1->height = max(height(k1->left),height(k1->right))+1;
  k2->height = max(height(k2->right),k1->height)+1;
  return k2;
}

static position doublerotatewithleft(position k3)
{
  k3->left = singlerotatewithright(k3->left);
  return singlerotatewithleft(k3);
}

static position doublerotatewithright(position k1)
{
  k1->right = singlerotatewithleft(k1->right);
  return singlerotatewithright(k1);
}

//////Insert routine

avltree insert(int X,avltree T)
{
  if(T==NULL)
  {
    T=(avlnode*)malloc(sizeof(struct avlnode));
    if(T==NULL)
      return NULL;
    else
    {
      T->element=X;
      T->height=0;
      T->left=T->right=NULL;
    }
  }
  else if(X<T->element)
  {
    T->left = insert(X,T->left);
    if(height(T->left)-height(T->right)==2)
    {
      if(X<T->left->element)
T = singlerotatewithleft(T);
      else
T = doublerotatewithleft(T);
    }
  }
  else if(X>T->element)
  {
    T->right=insert(X,T->right);
    if(height(T->right)-height(T->left)==2)
    {
      if(X>T->right->element)
T= singlerotatewithright(T);
      else
T=doublerotatewithright(T);
    }
  }
  T->height = max(height(T->left),height(T->right))+1;
  return T;
}

inorder(avltree ptr)
{
  if(ptr!=NULL)
  {
     inorder(ptr->left);
     printf("%d ",ptr->element);
     inorder(ptr->right);
  }
}

display(avltree ptr,int level)
{
  int i;
  if(ptr!=NULL)
  {
    display(ptr->right,level+1);
    printf("\n");
    for(i=0;i<level;i++)
      printf(" ");
    printf("%d",ptr->element);
    display(ptr->left,level+1);
  }
}

void main()
{
  clrscr();
  int choice=0,data;
  avltree T;
  position p;
  T=makeempty(NULL);
  while(1)
  {
    printf("\n\n 1.Insert");
    printf("\n\n 2.Display");
    printf("\n\n 3.Exit\n");
    printf("\n\n Enter your choice:");
    scanf("%d",&choice);
    if(choice==3)
      break;
    switch(choice)
    {
      case 1:
printf("\n\n Enter the value to be inserted:");
scanf("%d",&data);
if(find(data,T)==NULL)
    T=insert(data,T);
else
  printf("\n\n Duplicate value ignored\n");
break;
      case 2:
if(T==NULL)
{
  printf("\n Empty tree...");
  continue;
}
printf("\n\n");
display(T,1);
printf("\n\n Inorder traversal of Tree is:");
inorder(T);
break;
      default:
printf("\n wrong choice...");
break;
    }
  }
  getch();
}


OUTPUT

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:23

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:16

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:35

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:12

1.Insert
2.Display
3.Exit

Enter your choice:1

Enter the value to be inserted:24

1.Insert
2.Display
3.Exit

Enter your choice:2


35
   24
23
  16
   12



Inorder traversal of Tree is:12 16 23 24 35

1.Insert
2.Display
3.Exit

Enter your choice:3