AVL TREES || (INSERTION)

Woah.. First of all a merry Christmas to all my blog readers and to the non-readers also… 

Today’s post is special obviously because of the topic we are going to discuss is super important but also because I am writing this post because, one of my friend called me lately and told that my blog was useful for preparing for this company, which was visiting his campus, Overwhelmed by the response I decided to dedicate this post to my friend Anupam.

Another reason is because today is the birthday of my very special friend shivanshu so Happy b’day to you friend, brother, bestie.. etc.. , my post is dedicated to you also.

Now let’s discuss the topic we are here for (such an irony….) 

Today’s post is all about AVL trees. Now why AVL trees because AVL is a self-balancing binary tree, whose specialty is that operations like finding max, min, delete, insert takes O(h) time, where h is the height of tree. The upper bound for height is (Log n), that’s why this tree is special. As we know that in case of Binary tree all these operations take O(n)  time in case of worst case, which is in case of skewed binary tree.

INSERTION

To make sure that after every insertion the tree remains balanced or the upper bound remains (Log n) some mumbo jumbo magic is required, since we computer scientists have our magic in codes, I will try to do the same to get height balanced after every operation.

The two operations are

1.  Left Rotate
2.  Right Rotate

The idea is to augment the standard BST insert so that the tree remains height balanced.

Now what is height balance??

Height of left child/subtree – Height of right child/subtree should be between [-1,1] i.e. {1,0,-1}. (since these values can be integer only).

The above condition make sure that the height of the BST remain balanced and whenever the above condition violates we apply right rotation or left rotation to make the tree balanced again.

Steps to follow for insertion

Let the newly inserted 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.

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          y

      / \      - - - - - - - - ->          /  \                   - - - - - - - ->              / \        / \

    x   T4                               T2   y                                               T1  T2   T3  T4

  /  \                                           /  \

T2   T3                                    T3   T4

 Uff.. A lot of new things we have learnt today.. Lets Keep the implementation for the next post.. ;-)

Any doubts and suggestions are welcomed.. :)

Viva La Raza

Sid

(Happy Christmas... ;-))

AVL Tree Insertion (Part 2)

C implementation

Following is the C implementation for AVL Tree Deletion. The following C implementation uses the recursive BST delete as basis. In the recursive BST delete, after deletion, 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 deleted node.
1) Perform the normal BST deletion.
2) The current node must be one of the ancestors of the deleted 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 Left Right case, get the balance factor of left subtree. If balance factor of the left subtree is greater than or equal to 0, then it is Left Left case, else Left Right case.
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 Right Left case, get the balance factor of right subtree. If the balance factor of the right subtree is smaller than or equal to 0, then it is Right Right case, else Right Left case.

The code for the above implementation follows :

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

struct node
{
struct node* left;
struct node* right;
int key;
int height;
};

int height(struct node* h)
{
    if(h==NULL)
        return 0;

        return (h->height);
}
int max(int a, int b)
{
    return (a > b)? a : b;
}

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);
}
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;
}

struct node* leftRotate(struct node* y)
{
    struct node* x=y->right;
    struct node* T2=x->left;

    x->left=y;
    y->right=T2;

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

     return x;
}

int getbalance(struct node* a)
{
    if (a==NULL)
        return 0;
    else
        return (height(a->left)-height(a->right));
}

struct node* insert(struct node* a,int key)
{
 if(a==NULL)
        return (newnode(key));

  if(a->key > key)
    a->left=insert(a->left,key);

  else if (a->key < key)
    a->right=insert(a->right,key);

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

    int balance=getbalance(a);

    if(balance > 1 && (key< a->left->key))//left left case
        return rightRotate(a);
    if(balance > 1 && (key> a->left->key))//left right case
    {
        a->left=leftRotate(a->left);
        return (rightRotate(a));
    }

    if(balance < -1 && (key> a->right->key))//right right case
        return leftRotate(a);

    if(balance <-1 && (key< a->right->key))//right left case
    {
        a->right=rightRotate(a->right);
        return (leftRotate(a));
    }


    return a;

}
void preOrder(struct node* root)
{
    if(root)
    {
        printf("%d ",root->key);
        preOrder(root->left);
        preOrder(root->right);
    }
}

int main()
{
  struct node* root=NULL;
  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("the preorder traversal of given tree is\n");
  preOrder(root);



}

Viva La Raza

Sid

The inspiration for the above article has been taken from : http://www.geeksforgeeks.org/