AVL TREES

//EX: 1C Program to insert and delete elements in an AVL Tree 1
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define FALSE 0
#define TRUE 1
struct AVLNode
{
  int data;
  int balfact;
  struct AVLNode *left;
  struct AVLNode *right;
};

struct AVLNode * insert(struct AVLNode *,int,int *);
struct AVLNode * deldata(struct AVLNode *,int,int *);
struct AVLNode * del(struct AVLNode *,struct AVLNode *,int *);
struct AVLNode * balr(struct AVLNode *,int *);
struct AVLNode * ball(struct AVLNode *,int *);
void display(struct AVLNode *);
void deltree(struct AVLNode *);
void main()
{
  struct AVLNode *avl=NULL;
  int h;
  clrscr();
  avl=insert(avl,20,&h);
  avl=insert(avl,6,&h);
  avl=insert(avl,29,&h);
  avl=insert(avl,5,&h);
  avl=insert(avl,12,&h);
  avl=insert(avl,25,&h);
  avl=insert(avl,32,&h);
  avl=insert(avl,10,&h);
  avl=insert(avl,15,&h);
  avl=insert(avl,27,&h);
 // avl=insert(avl,13,&h);
  printf("\n AVL Tree : \n");
  display(avl);
  avl=deldata(avl,5,&h);
  avl=deldata(avl,12,&h);
  printf("\n AVL tree after deletion of a node : \n");
  display(avl);
  deltree(avl);
  getch();

}



/* Inserts an element intp tree */
struct  AVLNode * insert(struct AVLNode *root,int data,int *h)
{
  struct AVLNode *node1,*node2;
  if(!root)
  {
     root=(struct AVLNode *)malloc(sizeof(struct AVLNode));
     root->data=data;
     root->left=NULL;
     root->right=NULL;
     root->balfact=0;
     *h=TRUE;
     return(root);
  }
  if(data < root->data)
  {
     root->left=insert(root->left,data,h);
     /* If left subtree is higher */
     if(*h)
     {
    switch(root->balfact)
    {
       case 1:
         node1=root->left;
         if(node1->balfact==1)
         {
           printf("\n Right Rotation alond %d. ",root->data);
           root->left=node1->right;
           node1->right=root;
           root->balfact=0;
           root=node1;
         }
         else
         {
          printf("\n Double rotation , left along %d",node1->data);
          node2=node1->right;
          node1->right=node2->left;

          printf(" then right along %d. \n",root->data);
          node2->left=node1;
          root->left=node2->right;
          node2->right=root;

          if(node2->balfact==1)
         root->balfact=-1;
          else
         root->balfact=0;
          if(node2->balfact==-1)
         node1->balfact=1;
          else
         node1->balfact=0;
          root=node2;
      }
      root->balfact=0;
      *h=FALSE;
      break;
       case 0:
         root->balfact=1;
         break;
       case -1:
         root->balfact=0;
         *h=FALSE;
      }
      }

  }

  if(data > root->data)
  {
    root->right=insert(root->right,data,h);
    /* If the right subtree is higher */
    if(*h)
    {
       switch(root->balfact)
       {
      case 1:
           root->balfact=0;
           *h=FALSE;
           break;
      case 0:
           root->balfact=-1;
           break;
      case -1:
           node1=root->right;
           if(node1->balfact==-1)
           {
          printf("\n Left rotation along %d. ",root->data);
          root->right=node1->left;
          node1->left=root;
          root->balfact=0;
          root=node1;
           }
           else
           {
          printf("\n Double rotation , right along %d",node1->data);
          node2=node1->left;
          node1->left=node2->right;
          node2->right=node1;
          printf(" then left along %d. \n",root->data);
          root->right=node2->left;
          node2->left=root;
          if(node2->balfact==-1)
             root->balfact=1;
          else
             root->balfact=0;
          if(node2->balfact==1)
             node1->balfact=-1;
          else
             node1->balfact=0;
          root=node2;
          }
          root->balfact=0;
          *h=FALSE;
    }
    }
 }
  return(root);

}


/* Deletes an item from the tree */
struct AVLNode * deldata(struct AVLNode *root,int data,int *h)
{
   struct AVLNode *node;
   if(!root)
   {
      printf("\n No such data. ");
      return (root);
   }
   else
   {
      if(data < root->data)
      {
     root->left=deldata(root->left,data,h);
     if(*h)
       root=balr(root,h);
      }
      else
      {
     if(data > root->data)
     {
        root->right=deldata(root->right,data,h);
          if(*h)
         root=ball(root,h);
     }
     else
     {
        node=root;
        if(node->right==NULL)
        {
           root=node->left;
           *h=TRUE;
           free(node);
        }
        else
        {
          node->right=del(node->right,node,h);
          if(*h)
         root=ball(root,h);
        }
      }
    }
      }

   return(root);
 }


 struct AVLNode * del(struct AVLNode *succ,struct AVLNode *node,int *h)
 {
    struct AVLNode *temp=succ;
    if(succ->left!=NULL)
    {
       succ->left=del(succ->left,node,h);
       if(*h)
      succ=balr(succ,h);
    }
    else
    {
       temp=succ;
       node->data=succ->data;
       succ=succ->right;
       free(temp);
       *h=TRUE;
    }
     return(succ);
}


/* Balance the tree , if right subtree is higher */
struct AVLNode * balr(struct AVLNode *root,int *h)
{
   struct AVLNode *node1,*node2;
   switch(root->balfact)
   {
     case 1:
    root->balfact=0;
    break;
     case 0:
    root->balfact=-1;
    *h=FALSE;
    break;
     case -1:
    node1=root->right;
    if(node1->balfact <= 0)
    {
      printf("\n Left rotation along %d. ",root->data);
      root->right=node1->left;
      node1->left=root;
      if(node1->balfact==0)
      {
          root->balfact=-1;
          node1->balfact=1;
        *h=FALSE;
      }
      else
      {
          root->balfact=node1->balfact=0;
      }
      root=node1;
    }
     else
     {
       printf("\n Double rotation , right along %d ",node1->data);
       node2=node1->left;
       node1->left=node2->right;
       node2->right=node1;
       printf(" then left along %d. \n",root->data);
       root->right=node2->left;
       node2->left=root;

       if(node2->balfact==-1)
      root->balfact=1;
       else
      root->balfact=0;
       if(node2->balfact==1)
     node1->balfact=-1;
       else
     node1->balfact=0;
       root=node2;
       node2->balfact=0;
    }
}
  return (root);
}


/* Balances the tree , if the left subtree is higher */
struct AVLNode * ball(struct AVLNode * root,int *h)
{
   struct AVLNode *node1,*node2;
   switch(root->balfact)
   {
      case -1:
     root->balfact=0;
     break;
      case 0:
     root->balfact=1;
     *h=FALSE;
     break;
      case 1:
     node1=root->left;
     if(node1->balfact >= 0)
     {
         printf("]n Right rotation along %d. ",root->data);
         root->left=node1->right;
         node1->right=root;
         if(node1->balfact==0)
         {
        root->balfact=1;
        node1->balfact=-1;
        *h=FALSE;
         }
         else
         {
           root->balfact=node1->balfact=0;
         }
         root=node1;
     }
     else
       {
      printf("\n Double rotation , left along %d ",node1->data);
      node2=node1->right;
      node1->right=node2->left;
      node2->left=node1;
      printf(" then right along %d .\n",root->data);

      root->left=node2->right;
      node2->right=root;

      if(node2->balfact==1)
          root->balfact=-1;
      else
          root->balfact=0;

      if(node2->balfact==-1)
          node1->balfact=1;
      else
          node1->balfact=0;
      root=node2;
      node2->balfact=0;
       }
    }
    return (root);
}




/*n Displays the tree in-order */
void display(struct AVLNode *root)
{
  if(root!=NULL)
  {
    display(root->left);
    printf("%d\t",root->data);
    display(root->right);
  }
}


/* Deletes the tree */
void deltree(struct AVLNode * root)
{
   if(root!=NULL)
   {
    deltree(root->left);
    deltree(root->right);
   }
   free(root);
}
//: CLICK HERE AVL TREES IN CPP

AVL Tree | Set 1 (Insertion)


AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
Why AVL Trees?
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree (See this  video lecture for proof).
Insertion
To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).
1) Left Rotation
2) Right Rotation
T1, T2 and T3 are subtrees of the tree rooted with y (on left side)
or x (on right side)
                y                               x
               / \     Right Rotation          /  \
              x   T3   – - – - – - – >        T1   y
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3
Keys in both of the above trees follow the following order
      keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.
Steps to follow for insertion
Let the newly nserted node be w
1) Perform standard BST insert for w.
2) Starting from w, travel up and find the first unbalanced node. Let z be the first unbalanced node, y be the child of z that comes on the path from w to z and x be the grandchild of z that comes on the path from w to z.
3) Re-balance the tree by performing appropriate rotations on the subtree rooted with z. There can be 4 possible cases that needs to be handled as x, y and z can be arranged in 4 ways. Following are the possible 4 arrangements:
a) y is left child of z and x is left child of y (Left Left Case)
b) y is left child of z and x is right child of y (Left Right Case)
c) y is right child of z and x is right child of y (Right Right Case)
d) y is right child of z and x is left child of y (Right Left Case)
Following are the operations to be performed in above mentioned 4 cases. In all of the cases, we only need to re-balance the subtree rooted with z and the complete tree becomes balanced as the height of subtree (After appropriate rotations) rooted with z becomes same as it was before insertion. (See this video lecture for proof)

a) Left Left Case
T1, T2, T3 and T4 are subtrees.
         z                                      y
        / \                                   /   \
       y   T4      Right Rotate (z)          x      z
      / \          - - - - - - - - ->      /  \    /  \
     x   T3                               T1  T2  T3  T4
    / \
  T1   T2
b) Left Right Case
     z                               z                           x
    / \                            /   \                        /  \
   y   T4  Left Rotate (y)        x    T4  Right Rotate(z)    y      z
  / \      - - - - - - - - ->    /  \      - - - - - - - ->  / \    / \
T1   x                          y    T3                    T1  T2 T3  T4
    / \                        / \
  T2   T3                    T1   T2
c) Right Right Case
  z                                y
 /  \                            /   \
T1   y     Left Rotate(z)       z      x
    /  \   - - - - - - - ->    / \    / \
   T2   x                     T1  T2 T3  T4
       / \
     T3  T4
d) Right Left Case
   z                            z                            x
  / \                          / \                          /  \
T1   y   Right Rotate (y)    T1   x      Left Rotate(z)   z      x
    / \  - - - - - - - - ->     /  \   - - - - - - - ->  / \    / \
   x   T4                      T2   y                  T1  T2  T3  T4
  / \                              /  \
T2   T3                           T3   T4

C implementation
Following is the C implementation for AVL Tree Insertion. The following C implementation uses the recursive BST insert to insert a new node. In the recursive BST insert, after insertion, we get pointers to all ancestors one by one in bottom up manner. So we don’t need parent pointer to travel up. The recursive code itself travels up and visits all the ancestors of the newly inserted node.
1) Perform the normal BST insertion.
2) The current node must be one of the ancestors of the newly inserted node. Update the height of the current node.
3) Get the balance factor (left subtree height – right subtree height) of the current node.
4) If balance factor is greater than 1, then the current node is unbalanced and we are either in Left Left case or left Right case. To check whether it is left left case or not, compare the newly inserted key with the key in left subtree root.
5) If balance factor is less than 1, then the current node is unbalanced and we are either in Right Right case or Right Left case. To check whether it is Right Right case or not, compare the newly inserted key with the key in right subtree root.

#include<stdio.h>

#include<stdlib.h>



// An AVL tree node

struct node

{

    int key;

    struct node *left;

    struct node *right;

    int height;

};



// A utility function to get maximum of two integers

int max(int a, int b);



// A utility function to get height of the tree

int height(struct node *N)

{

    if (N == NULL)

        return 0;

    return N->height;

}



// A utility function to get maximum of two integers

int max(int a, int b)

{

    return (a > b)? a : b;

}



/* Helper function that allocates a new node with the given key and

    NULL left and right pointers. */

struct node* newNode(int key)

{

    struct node* node = (struct node*)

                        malloc(sizeof(struct node));

    node->key   = key;

    node->left   = NULL;

    node->right  = NULL;

    node->height = 1;  // new node is initially added at leaf

    return(node);

}



// A utility function to right rotate subtree rooted with y

// See the diagram given above.

struct node *rightRotate(struct node *y)

{

    struct node *x = y->left;

    struct node *T2 = x->right;



    // Perform rotation

    x->right = y;

    y->left = T2;



    // Update heights

    y->height = max(height(y->left), height(y->right))+1;

    x->height = max(height(x->left), height(x->right))+1;



    // Return new root

    return x;

}



// A utility function to left rotate subtree rooted with x

// See the diagram given above.

struct node *leftRotate(struct node *x)

{

    struct node *y = x->right;

    struct node *T2 = y->left;



    // Perform rotation

    y->left = x;

    x->right = T2;



    //  Update heights

    x->height = max(height(x->left), height(x->right))+1;

    y->height = max(height(y->left), height(y->right))+1;



    // Return new root

    return y;

}



// Get Balance factor of node N

int getBalance(struct node *N)

{

    if (N == NULL)

        return 0;

    return height(N->left) - height(N->right);

}



struct node* insert(struct node* node, int key)

{

    /* 1.  Perform the normal BST rotation */

    if (node == NULL)

        return(newNode(key));



    if (key < node->key)

        node->left  = insert(node->left, key);

    else

        node->right = insert(node->right, key);



    /* 2. Update height of this ancestor node */

    node->height = max(height(node->left), height(node->right)) + 1;



    /* 3. Get the balance factor of this ancestor node to check whether

       this node became unbalanced */

    int balance = getBalance(node);



    // If this node becomes unbalanced, then there are 4 cases



    // Left Left Case

    if (balance > 1 && key < node->left->key)

        return rightRotate(node);



    // Right Right Case

    if (balance < -1 && key > node->right->key)

        return leftRotate(node);



    // Left Right Case

    if (balance > 1 && key > node->left->key)

    {

        node->left =  leftRotate(node->left);

        return rightRotate(node);

    }



    // Right Left Case

    if (balance < -1 && key < node->right->key)

    {

        node->right = rightRotate(node->right);

        return leftRotate(node);

    }



    /* return the (unchanged) node pointer */

    return node;

}



// A utility function to print preorder traversal of the tree.

// The function also prints height of every node

void preOrder(struct node *root)

{

    if(root != NULL)

    {

        printf("%d ", root->key);

        preOrder(root->left);

        preOrder(root->right);

    }

}



/* Drier program to test above function*/

int main()

{

  struct node *root = NULL;



  /* Constructing tree given in the above figure */

  root = insert(root, 10);

  root = insert(root, 20);

  root = insert(root, 30);

  root = insert(root, 40);

  root = insert(root, 50);

  root = insert(root, 25);



  /* The constructed AVL Tree would be

            30

           /  \

         20   40

        /  \     \

       10  25    50

  */



  printf("Pre order traversal of the constructed AVL tree is \n");

  preOrder(root);



  return 0;

}
Output:
  Pre order traversal of the constructed AVL tree is
  30 20 10 25 40 50
Time Complexity: The rotation operations (left and right rotate) take constant time as only few pointers are being changed there. Updating the height and getting the balance factor also take constant time. So the time complexity of AVL insert remains same as BST insert which is O(h) where h is height of the tree. Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).
The AVL tree and other self balancing search trees like Red Black are useful to get all basic operations done in O(Logn) time. The AVL trees are more balanced compared to Red Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is more frequent operation, then AVL tree should be preferred over Red Black Tree