Insertion in AVL tree (or) Creation of AVL tree : JAVA program and C program

General Algorithm to insert a node into AVL tree

1.      Insert the node in the same way as in ordinary binary search tree

2.      Trace insertion path of new node back towards root, checking the difference in height of each node along the path

3.      if you find a node with imbalance, stop trace at this node

4.      Consider the node with imbalance and two other nodes on the insertion path

5.      if these 3 nodes lie in straight line, apply a single rotation (LL or RR) to correct the imbalance

6.      if these 3 nodes lie in a dog-leg pattern, perform double rotation (LR or RL)

import java.util.Scanner;
class AVLNode
{
    int data,ht;
    AVLNode left,right;
}
class AVL
{
    AVLNode root = null;
    public int height(AVLNode root)
    {
        if(root == null)
            return -1;
        return(Math.max(height(root.left),height(root.right))+1);
    }
 
    public int bf(AVLNode root)
    {
        return Math.abs(height(root.left)-height(root.right));
    }
    public AVLNode LL(AVLNode x)
    {
        AVLNode y = x.left;
        x.left=y.right;
        y.right=x;
        x.ht = height(x);
        y.ht=height(y);
        return y;
    }
    public AVLNode RR(AVLNode x)
    {
        AVLNode y = x.right;
        x.right=y.left;
        y.left=x;
        x.ht = height(x);
        y.ht=height(y);
        return y;
    }
    public AVLNode LR(AVLNode x)
    {
        x.left = RR(x.left);
        return LL(x);
    }
    public AVLNode RL(AVLNode x)
    {
        x.right = LL(x.right);
        return RR(x);
    }
    public AVLNode insert(AVLNode root, int val)
    {
        if(root==null)
        {
            AVLNode newnode = new AVLNode();
            newnode.data=val;
            newnode.left=newnode.right=null;
            newnode.ht=0;
            root=newnode;
            return root;
        }
        else if(val < root.data)
        {
            root.left = insert(root.left,val);
            if(bf(root) == 2)
            {
                if(val < root.left.data)
                    return LL(root);
                else
                    return LR(root);
            }
        }
        else
        {
            root.right = insert(root.right, val);
            if(bf(root) == 2)
            {
                if(val > root.right.data)
                    return RR(root);
                else
                    return RL(root);
            }
        }
        return root;
    }
    public void inorder(AVLNode root)
    {
        if(root != null)
        {
            inorder(root.left);
            System.out.println(root.data);
            inorder(root.right);
        }
    }
}
public class AVLDemo
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        AVL ob = new AVL();
        while(true)
        {
             System.out.println("1. insert 2. inorder 3. exit");
             int choice = sc.nextInt();
             switch(choice)
             {
                 case 1:
                         System.out.println("enter the value to be inserted");
                         int val=sc.nextInt();
                         ob.root=ob.insert(ob.root,val);
                         break;
                case 2:
                        ob.inorder(ob.root);
                        break;
             
                default:
                        System.exit(0);
             }
        }
    }
}

Input:
1
10
1
20
1
30
1
40
1
6
2
3
=============================
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
struct node
{
 int data,ht;
 struct node *left, *right;
};
int max(int a,int b)
{
 if(a>b)
  return a;
 else
  return b;
}

int height(struct node *root)
{
 if(root == NULL)
    return -1;
 else
    return (max(height(root->left),height(root->right))+1); 
}

int bf(struct node *root)
{
 return abs(height(root->left)-height(root->right));

}

struct node * LL(struct node *x) /* rotate right*/
{
 struct node * y = x->left;
 x->left=y->right;
 y->right=x;
 x->ht=height(x);
 y->ht=height(y);
 return y;
}


struct node *RR(struct node *x)
{
 struct node *y=x->right;
 x->right=y->left;
 y->left=x;
 x->ht=height(x);
 y->ht=height(y);
 return y;
}
struct node *LR(struct node *x)
{
 x->left=RR(x->left);
 x=LL(x);
 return x;
}


struct node *RL(struct node *x)
{
 x->right=LL(x->right);
 x=RR(x);
 return x;
}


struct node *insert(struct node *root, int val)
{
 if(root == NULL)
 {
  struct node *newnode = (struct node *)malloc(sizeof(struct node));
  newnode->data=val;
  newnode->ht=0;
  newnode->left = NULL;
  newnode->right = NULL;
  root=newnode;
  return root;
 }
 else if(val < root->data)
 {
  root->left=insert(root->left,val);
  if(bf(root)== 2)
  {
   if(val < root->left->data) /* newnode inserted to left of root->left*/
    return LL(root);
   else
    return LR(root);
  }
 }
 else
    {
     root->right = insert(root->right,val);
  if(bf(root)== 2)
  {
   if(val > root->right->data) /* newnode inserted to right of root->right*/
    return RR(root);
   else
    return RL(root);
  }
    }
    root->ht=height(root);
 return root;
}


void inorder(struct node * root)
{
 if(root != NULL)
 {
        inorder(root->left);
        printf("%d\t",root->data);
        inorder(root->right);
    }
}
struct node * findMin(struct node * root)
{
   if(root == NULL)
      return NULL;
   else if(root->left == NULL)
      return root;
   else
      return findMin(root->left);
}
struct node * delete(struct node *root, int val)
{
   struct node *c;
   if(root == NULL)
   {
      printf("deleted element not found");
      return root;
   }
   else if( val < root->data)
      root->left=delete(root->left,val);
   else if( val > root->data)
      root->right=delete(root->right,val);
   else
   {
      if(root->left == NULL && root->right == NULL)
         return NULL;
      else if(root->right != NULL && root->left == NULL) /*if only right child exists*/
         return root->right;
      else if(root->left != NULL && root->right == NULL)  /* if only left child exists*/
         return root->left;
      else
      {
         c=findMin(root->right); /*find the minimum element in right subtree*/
         root->data=c->data;           /* copy the minimum element value into the root */
         root->right=delete(root->right,c->data);  /*delete the duplicate element.*/
         return root;
      }
      root->ht = height(root);
      if (bf(root) >= 2 && root->left && root->left->left)
        return LL(root);
 
      else if (bf(root) >= 2 && root->left && root->left->right)
        root=LR(root);
     
      else if (bf(root) >= 2 && root->right && root->right->right)
        return RR(root);
 
      if (bf(root) >= 2 && root->right && root->right->left)
        root=RL(root);
              
   }
}

main()
{
 int i,n,val,opt;
 struct node *root=NULL;
 while(1)
 {
  printf("\nmenu\n");
  printf("1.insert\n2.display\n3.delete\n4.exit\n");
  printf("enter ur option\n");
  scanf("%d",&opt);
  switch(opt)
  {
   case 1: printf("enter number of elements\n");
           scanf("%d",&n);
           for(i=0;i<n;i++)
           {
            printf("enter an element\n");
            scanf("%d",&val);
            root=insert(root,val);
           }
           break;
   case 2: inorder(root);
           break;
   case 3:
           printf("enter the value to be deleted\n");
           scanf("%d",&val);
           root=delete(root,val);
           break;
   case 4:
           exit(0);
     }
  }
}

Output

menu
1.insert
2.display
3.delete
4.exit
enter ur option
1
enter number of elements
4
enter an element
1
enter an element
2
enter an element
3
enter an element
4

menu
1.insert
2.display
3.delete
4.exit
enter ur option
2
1    2    3    4  
menu
1.insert
2.display
3.delete
4.exit
enter ur option
3
enter the value to be deleted
1

menu
1.insert
2.display
3.delete
4.exit
enter ur option
2
2    3    4  
menu
1.insert
2.display
3.delete
4.exit
enter ur option
3
enter the value to be deleted
3

menu
1.insert
2.display
3.delete
4.exit
enter ur option
2
2    4  
menu
1.insert
2.display
3.delete
4.exit
enter ur option

(OR) 

height function can be as below which is not recursion

int height(struct node *root)

{

   if(root == NULL)

      return -1;

    else

    {

      if(root->left == NULL && root->right == NULL)

          return 0;

      if(root->left == NULL && root->right != NULL)

            return root->right->ht+1;

        else if(root->left != NULL && root->right == NULL)

            return root->left->ht+1;

        else if(root->left != NULL && root->right != NULL)

            return max(root->right->ht,root->left->ht)+1;

     

    }

}