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;

     

    }

}

implementing queue using two stacks

THE BELOW PROGRAM FAILS IN FEW TEST CASES

#include<stdio.h>
int front_val,s1[100],s2[100],top1=-1,top2=-1;
void enqueue(int x) {
int t;
    while(top2 != -1)
    {
     t=s2[top2--];
     s1[++top1]=t;
    }
if(top1==-1) {
        front_val = x;
    }
    s1[++top1]=x;
}

int dequeue() {
int t,x;
    while(top1 != -1) {
    t=s1[top1--];
    s2[++top2]=t;
    }
     x = s2[top2--];
 
    if(top2 != -1) {
        front_val = s2[top2];
    }
    return x;
}

int peek() {
    return front_val;
}

main()
{
int t,i,opt,val;
    scanf("%d", &t);
    for(i=0;i<t;i++)
{
        scanf("%d", &opt);
        switch(opt)
{
            case 1:
                scanf("%d", &val);
                enqueue(val);
                break;
            case 2:
                dequeue();
                break;
            case 3:
                printf("%d\n", peek());
                break;
        }
}
}

Creation or insertion, deletion, inorder, preorder, postorder traversals in BST : JAVA and C program

minimum height of bst = log2(n+1)-1 if height of the tree is 0 if it contains single node.

import java.util.Scanner;

class BSTNode
{
    int data;
    BSTNode left,right;
}
class BST
{
    BSTNode root=null;
    public BSTNode insert(BSTNode root, int val)
    {
        if(root == null)
        {
            BSTNode newnode = new BSTNode();
            newnode.data=val;
            newnode.left=newnode.right=null;
            root=newnode;
        }
        else if(val<root.data)
            root.left=insert(root.left,val);
        else
            root.right=insert(root.right,val);
        return root;
    }
    public void inorder(BSTNode root)
    {
        if(root != null)
        {
            inorder(root.left);
            System.out.println(root.data);
            inorder(root.right);
        }
    }
     public void preorder(BSTNode root)
    {
        if(root != null)
        {
            System.out.println(root.data);
            preorder(root.left);
            preorder(root.right);
        }
    }
    public void postorder(BSTNode root)
    {
        if(root != null)
        {
            postorder(root.left);
            postorder(root.right);
            System.out.println(root.data);
        }
    }
    public BSTNode findmin(BSTNode root)
    {
        if(root == null)
            return null;
        if(root.left == null)
            return root;
        return findmin(root.left);
    }
    
     public BSTNode delete(BSTNode root, int val)
    {
        if(root == null)
        {
                 System.out.println("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.left == null && root.right != 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
                {
                    BSTNode 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;
                }
        }
        return root;
    }
}
public class BSTDemo
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        BST ob = new BST();
        while(true)
        {
             System.out.println("1. insert 2. inorder 3. preorder 4. postorder 5. delete 6. 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;
                case 3:
                        ob.preorder(ob.root);
                        break;
                case 4:
                        ob.postorder(ob.root);
                        break;
                case 5:
                        System.out.println("enter the value to be deleted");
                        val=sc.nextInt();
                        ob.root=ob.delete(ob.root,val);
                        break;
                default:
                        System.exit(0);
             }
        }
    }
}

Sample input for which you can check the program
1 10
1 20
1 30
1 2
1 45
1 55
2
5 55
2
5 10
2
5 20
2

6
===========================================================

#include <stdio.h>

#include <stdlib.h>

struct node * insert(struct node *,int l);

void inorder(struct node *);

void preorder(struct node *);

void postorder(struct node *);

struct node * findMin(struct node *);

struct node * delete(struct node *, int);

struct node

{

               int data;

               struct node *left,*right;

};

void main()

{

               int val,opt;

               struct node *root = NULL,*c;

  while(1)

  {

               printf("\n Press 1. insert \t 2. inorder\t 3. preorder \t4. postorder \t 5. delete \t 6. exit\n");

               scanf("%d",&opt);

               switch(opt)

               {

                              case 1:  printf("\nenter a value");

                                             scanf("%d",&val);

                                             root=insert(root,val);

                                             break;

                              case 2: printf("\n inorder traversal\t");

                                             inorder(root);

                                             break;

                              case 3:  printf("\n preorder traversal\t");

                                             preorder(root);

                                             break;

                              case 4:  printf("\n postorder traversal\t");

                                             postorder(root);

                                             break;

                              case 5:  printf("\n enter the element to delete");

                                             scanf("%d",&val);

                                             root=delete(root,val);

                                             break;

                              case 6: exit(0);

               }

    }

}

struct node * insert(struct node *root,int val)

{

               if(root == NULL)

               {

                              struct node *newnode=(struct node *)malloc(sizeof(struct node));

                              newnode->data = val;

                              newnode->left = NULL;

                              newnode->right = NULL;

                              root=newnode;

               }

               else if(val < root->data)

                              root->left=insert(root->left,val);

               else

                              root->right = insert(root->right,val);

return root;

}

void inorder(struct node * root)

{

               if(root != NULL)

               {

                              inorder(root->left);

                              printf("%d\t",root->data);

                              inorder(root->right);

               }

}

void preorder(struct node * root)

{

               if(root != NULL)

               {

                              printf("%d\t",root->data);

                              preorder(root->left);

                              preorder(root->right);

               }

}

void postorder(struct node * root)

{

               if(root != NULL)

               {

                              postorder(root->left);

                              postorder(root->right);

                              printf("%d\t",root->data);

               }

}

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;

                              }
               }
}

insert and deletemin operation in binary heap : c program

#include <stdio.h>
#include <stdlib.h>
int LeftChild(int);
void heapify(int *,int,int);
void Build_maxheap(int *,int);
int insert(int *,int,int);
main()
{
 int n,i,a[100],opt,val;
 printf("enter n value");
 scanf("%d",&n);
 for(i=0;i<n;i++)      //reading values into array
  scanf("%d",&a[i]);
 Build_maxheap(a,n);   //building max heap
 printf("\n max heap\n"); // printing max heap
 for(i=0;i<n;i++)
  printf("%d\t",a[i]);
while(1)
{
 printf("\nPress 1. Insert \t 2. DeleteMax \t 3. exit\n");
 scanf("%d",&opt);
 switch(opt)
 {
  case 1: printf("\nenter the value to insert\n");
    scanf("%d",&val);
    n=insert(a,val,n);
    printf("\nafter inserting\n");
    for(i=0;i<n;i++)
     printf("%d\t",a[i]);
    break;
      
  case 2: DeleteMax(a,n);
    printf("\nafter deleting\n");
    for(i=0;i<n;i++)
     printf("%d\t",a[i]);
    break;
  case 3: exit(0);
 }
}
}
int insert(int *a,int val,int n)
{
 int k,t,i;
 a[n]=val;

 for(k=n;(k-1)/2>=0;k=(k-1)/2)
 {
  if(a[k]>a[(k-1)/2])
  {
   t=a[k];
   a[k]=a[(k-1)/2];
   a[(k-1)/2]=t;
  }
  else
   break;
 }
 n=n+1;
 return n;
}
int DeleteMax(int *a, int n)
{
 int max;
 if(n<1)
 {
  printf("no elements to delete");
 }
 else
 {
  max=a[0];
  printf("deleted maximum = %d",max);
  a[0] = a[n-1];
   heapify(a,0,n-1);
  n=n-1;
  return n;
 }
}
int LeftChild(int i)
{
 return (2*(i)+1);
}
void heapify(int *a,int j, int n)
{
 int bci,t;
 for(;LeftChild(j) <n;j=bci) //as long as left child exists
 {
  bci=LeftChild(j); //bci means biggest child index
  if( bci != n-1 &&  a[bci+1] > a[bci])//bci+1 means right child index of i
    bci= bci+1;

  if(a[bci]> a[j])// if big child value is > parent, swap big child value and parent value.
   {
    t=a[j];
    a[j]=a[bci];
    a[bci]=t;
   }
  else    //if big child value is < parent, then this is following max heap property
   break;
 }
   
}
void Build_maxheap(int *a, int n)
{
 int i;
 for(i=n/2;i>=0;i--)// loop for converting complete binary tree to max heap
  heapify(a,i,n);
}

Output:

Best, Average and Worst Case Time complexities of different Sorting Methods

Sorting Technique	Best	Average	Worst	in-place	Stable	Method
Insertion sort	n	n2	n2	Yes	Yes	Insertion
Shell Sort	n	nlog2n or n3/2	Depends	Yes	No	Insertion
Selection Sort	n2	n2	n2	Yes	No	Selection
Heap Sort	nlogn	nlogn	nlogn	Yes	No	Selection
Bubble Sort	n	n2	n2	Yes	Yes	Exchanging
Merge Sort	nlogn	nlogn	nlogn	No	Yes	Merging
Quick Sort	nlogn	nlogn	n2	Yes	Depends	Partitioning