AVL Tree

Input A tree rooted at root.
Output Tree after insertion of node.
Complexity O(logn)

AVL Insertion
   AVL insert (root)
if item <info[root] then
         AVL insert(left[root])
else  AVL insert(right[root])
if (root = null)
		Temp[info]=item;
		Temp =root;
if (left[root]=null and right[root]=null) then
		Root [info]=item;
if (item <info [root]  ) then 
		Left [root] =temp;
if (item >info [root] ) then 
		Right [root]=temp;
AVL rotation (x, p[x] , p[p[x]] );

AVL deletion 
Input A tree rooted at root.
Output	Tree after deletion of node.
Complexity O(logn).

AVL delete (item, p)
If (item=info[root]) then 
    if (right[root] != null) then
        q=successor(root);
        info[root]=q;
        AVL delete(q);
    else if(left[root] !=null) then
            q=predecessor(root)
                                     info[root]=q;
                 AVL delete(q);
    else  AVL delete(p);
else
    if (item <info[p]) then
        AVL delete(left[p]);
    else
        AVL delete(right[p]);
     AVL rotate(p,  pr[p] ,  sib[p]);

#include<stdio.h>
#include<alloc.h>
#include<<stdlib.h>


typedef struct node1
{
  int data;
  int bf;
  struct node1 *left;
  struct node1 *right;
} node;


void insert_node(node **, int);
void delete_node(node **, int);
int find_height(node *);
void delete_tree(node **);
node *findmax(node *);
void traverse_inorder(node *);


int main()
{
  int choice;        /* variable to store choice of user */
  int element;       /* variable to store data of node entered bu user */
  node *root = NULL; /* intialising root node */
  while (1)
  {
    printf("\n\t  MENU\n");
    printf("\t--------\n");
    printf(" 1. Insert node\n");
    printf(" 2. Delete node\n");
    printf(" 3. Height of Tree\n");
    printf(" 4. Traverse inorder\n");
    printf(" 5. Exit\n\n");
    printf("Enter your choice (1-5) ::");
    scanf("%d", &choice);
    switch (choice)
    {
      case 1: printf("\n Enter the element to be inserted::");
	      scanf("%d", &element);
	      insert_node(&root, element);
	      break;
      case 2: printf("\n Enter the element to be deleted ::");
	      scanf("%d", &element);
	      delete_node(&root, element);
	      break;
      case 3: printf("Height of AVL Tree = %d", find_height(root));
	      break;
      case 4: printf("\n\n In-Order Traversal is\n");
	      traverse_inorder(root);
	      break;
      case 5: delete_tree(&root);
	      return;
    }
  }
}

void insert_node(node ** root, int element)
{
  node *ptr1;
  node *ptr2;
  /* checking if there is no elemnt in th tree */
  if(NULL == *root)
  {
    *root          = (node *) malloc (sizeof(node)); /* allocating memory */
    (*root)->data  = element;
    (*root)->left  = NULL;
    (*root)->right = NULL;
    (*root)->bf    = 0;          /* allocating balance factor to root */
  }
  /* element is less than root than */
  else if(element < (*root)->data)
  {
    insert_node(&((*root)->left), element);
    switch((*root)->bf)
    {
      case 1: ptr1 = (*root)->left;
	      if(1 == ptr1->bf)
	      {
		/* right rotation */
		(*root)->left = ptr1->right;
		ptr1->right   = *root;
		(*root)->bf   = 0;
		*root         = ptr1;
	      }
	      else
	      {
		ptr2          = ptr1->right;
		ptr1->right   = ptr2->left;
		ptr2->left    = ptr1;
		(*root)->left = ptr2->right;
		ptr2->right   = *root;
		(*root)->bf   = ptr2->bf == 1 ? -1 : 0;
		ptr1->bf      = ptr2->bf == -1 ? 1 : 0;
		*root = ptr2;
	      }
	      break;
      case 0: (*root)->bf  = 1;
	      break;
      case -1: (*root)->bf = 0;
	      break;
    }
  }
  else
  {
    insert_node(&(*root)->right, element);
    switch((*root)->bf)
    {
      case 1: (*root)->bf = 0;
	      break;
      case 0: (*root)->bf = -1;
	      break;
      case -1: ptr1 = (*root)->right;
	       if(ptr1->bf == -1)
	       {
		 /* left rotation */
		 (*root)->right = ptr1->left;
		 ptr1->left     = *root;
		 (*root)->bf    = 0;
		 *root          = ptr1;
	       }
	       else
	       {
		 /* double rotation ,right left */
		 ptr2           = ptr1->left;
		 ptr1->left     = ptr2->right;
		 ptr2->right    = ptr1;
		 (*root)->right = ptr2->left;
		 ptr2->left     = (*root);
		 (*root)->bf    = ptr2->bf == -1 ? 1 : 0;
		 ptr1->bf       = ptr2->bf == 1 ? -1 : 0;
		 *root          = ptr2;
	       }
    }
  }
}

int find_height (node *tree)
{
  int height_of_left_subtree;
  int height_of_right_subtree;
  int height;
  if (NULL == tree)
  {
    height = 0;
  }
  else
  {
    height_of_left_subtree  = find_height(tree->left);
    height_of_right_subtree = find_height(tree->right);
    if(height_of_left_subtree > height_of_right_subtree)
      height = height_of_left_subtree + 1;
    else
      height = height_of_right_subtree + 1;
  }
  return height;
}

void delete_node (node **h, int element)
{
  node *temp;       /* variable to store node which has to be freed */
  node *ptr1;
  node *ptr2;
  if (NULL == *h)
  {
    printf("Element  %d not found in the AVL tree\n", element);
    printf("press any key to continue....");
    getch();
  }
  else if(element < (*h)->data)
  {
    delete_node(&(*h)->left, element);
    switch((*h)->bf)
    {
      case 1: (*h)->bf = 0;
	      break;
      case 0: (*h)->bf = -1;
	      break;
      case -1: ptr1 = (*h)->right;
	       if(ptr1->bf == -1)
	       {
		 /* left rotation */
		 (*h)->right = ptr1->left;
		 ptr1->left  = *h;
		 (*h)->bf    = 0;
		 *h          = ptr1;
	       }
	       else
	       {
		 ptr2        = ptr1->left;
		 ptr1->left  = ptr2->right;
		 ptr2->right = ptr1;
		 (*h)->right = ptr2->left;
		 ptr2->left  = *h;
		 (*h)->bf    = ptr2->bf == -1 ? 1 : 0;
		 ptr1->bf    = ptr2->bf == 1 ? -1 : 0;
		 *h          = ptr2;
	       }
    }
  }
  else if (element > (*h)->data)
  {
    delete_node (&(*h)->right, element);
    switch ((*h)->bf)
    {
      case 1: ptr1 = (*h)->left;
	      if(ptr1->bf == 1)
	      {
		/* right rotation */
		(*h)->left  = ptr1->right;
		ptr1->right = *h;
		(*h)->bf    = 0;
		*h          = ptr1;
	      }
	      else
	      {
		/* double rotation , left-right */
		ptr2        = ptr1->right;
		ptr1->right = ptr2->left;
		ptr2->left  = ptr1;
		(*h)->left  = ptr2->right;
		(*h)->bf    = ptr2->bf == 1 ? -1 : 0;
		ptr1->bf    = ptr2->bf == -1 ? 1 : 0;
		*h          = ptr2;
	      }
	      break;
      case 0: (*h)->bf = 1;
	      break;
      case -1: (*h)->bf = 0;
	     break;
    }
  }
  /* when element found and it has both the child than find predecessor */
  else if( (*h)->left && (*h)->right)
  {
    temp       = findmax((*h)->left);  /* find predecessor */
    (*h)->data = temp->data;   /* replace node with predecessor */
    delete_node(&(*h)->left, temp->data); /* delete predecessor */
  }
  else
  {
    temp = *h;
    if(((*h)->left == NULL) && ((*h)->right == NULL)) /* terminal node */
      *h = NULL;
    else if ((*h)->right == NULL)   /* left child only */
      *h = (*h)->left;
    else
      *h = (*h)->right;            /* right child only */
    free(temp);
  }
}

node * findmax(node *root)
{
  if((NULL == root) || (NULL == root->right))
  {
    return root;
  }
  else
    return findmax(root->right);
}

void traverse_inorder(node *root)
{
  if(NULL != root)
  {
    traverse_inorder(root->left);
    printf("%d, ", root->data);
    traverse_inorder(root->right);
  }
}
void delete_tree(node **root)
{
  if (NULL != *root)
  {
    delete_tree(&((*root)->left));
    delete_tree(&((*root)->right));
    free(root);
  }
}