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/

C Program to find if Two strings are Rotations of each other

Approach#1: The naive approach will be to find the first character occurrence in another string and then check whether the consecutive characters match with the other strings or not.

Approach#2:
The solution here is pretty simple:
i)  first append string which is rotated, to itself.
ii) find if second string is a substring of above appended string, if yes then return true, else return false.

here's the Implementation of the above algortihm:

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

int check_rotations(char* str1, char* str2)
{
    int x=strlen(str1);
    int y=strlen(str2);

    if(x!=y)
        return 0;

    char *temp=(char*) malloc(sizeof(char)*(2*x+1));
    strcpy(temp,str1);
    strcat(temp,str1);
    return strstr(temp,str2);

}

int main()
{
    char str1[]="DABC";
    char str2[]="ABCD";
    if(check_rotations(str1,str2))
        printf("strings are rotations of each other");
    else
        printf("strings are not rotations of each other");
}

Viva La Raza

Sid

Program to reverse words in a given string

Today's post is all about reversing strings. Without feeling the need to mention the algorithm, I am jumping straight to code after an example.

Input string: "This is yoyo honey singh"
output: "singh honey yoyo is This"

Here's the implementation:

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

void reverse(char* str);
void reverse_wrds(char*str1,char*str2);

void reverse(char* s)
{
    char* temp=s;
    char* beg=s;

    while(*temp)
    {
        temp++;
        if(*temp == '\0')
        {
            reverse_wrds(beg,temp-1);
        }
        if(*temp ==' ')
        {
            reverse_wrds(beg,temp-1);
            beg=temp+1;
        }
    }
reverse_wrds(s,temp-1);
}

void reverse_wrds(char* beg,char* end)
{
    char temp;
    while(beg<end)
    {
        temp=*beg;
        *beg++=*end;
        *end--=temp;

    }
}

int main()
{
    char s[]="This is yoyo honey singh";
    char* temp=s;
    reverse(temp);
    puts(temp);
}

This code to handle cases where starting of the string or in the the middle there are extra spaces a slight modification is required. Here's the pseudo code for that:

beg=NULL;

while(*temp)

{

if(beg==NULL && *temp!=' ' )

{

beg=temp;

}

if(beg!=NULL&& (*temp+1==' '|| *temp+1='\0'))

{

reverse_wrds(beg,temp);

beg=NULL;

}

reverse(the whole string)

}

Viva La Raza

Sid

C Program to Find Factorial Of LARGE NUMBERS

Today's post is all about calculating factorial. Seems to be easy at first look, calculating factorial is not that easy and you can believe that  from the experience of a guy who has lost a bet and a career opportunity due to this.

yes career opportunity.. that's another story which i will write, but later...

Approach #1:

The naive approach will be to run a loop till that number and storing the multiplication in a variable from 1 to that number and finally displaying the result.

But, there's a flaw in this approach, while multiplying numbers as soon as the data goes out OF RANGE of that number there will be discrepancy in the result, No matter you increase the size of data type. even long long unsigned int is not enough even for calculating the factorial of a small number like 55 or 60.   

Approach#2:

I learned from experience that whenever you are struck with something go back to the basics.

we will do the multiplication here exactly the same way we used to do in our maths class.

We will use arrays to store the number and perform multiplication on single integer index by index.

Here's the code for the implementation:

#include<stdio.h>

#define max 10000

void factorial(int);

void multiply(int);

int length=0;

int fact[max];

void factorial(int num)

{

    int i;

    for(i=2;i<=num;i++)

        multiply(i);

}

void multiply(int num)

{

    long i,rem=0;

    int j;

    int arr[max];

    for(i=0;i<=length;i++)

        arr[i]=fact[i];

    for(i=0;i<=length;i++)

    {

        fact[i]=((arr[i]*num)+rem)%10;

        rem=((arr[i]*num)+rem)/10;

    }

 if(rem!=0)

 {

     while(rem!=0)

     {

         fact[i]=rem%10;

         rem=rem/10;

         i++;

     }

 }

    length=i-1;

}

int main()

{

    int num,i;

    printf("\nEnter number whose factorial is to be calculated\n");

    scanf("%d",&num);

    fact[0]=1;

    factorial(num);

    printf("\nFactorial is: \n");

    for(i=length;i>=0;i--)

        printf("%d",fact[i]);

    return 0;

}

Have fun it's an easy code to understand. Comments below if you have any doubt's or suggestions. :)

Viva La Raza

Sid

C Program To Perform Reversal Of A String IN PLACE

Approach:

The trick behind this is very simple maintain two pointers one end pointer and one start pointer and swap their contents iteratively till they meet each other.

Let’s try to code it:

Program:

#include<stdio.h> /*for printf and scanf*/

void InplaceRev(char* str)

{

    char* temp=str; // end pointer

    char var;

    if(str==NULL)

       return str ;

    while(*temp)

        temp++; /*temp is pointing to '\0' i.e. end of string*/

    temp--; /*temp decremented to point to the last character of the string*/

    while(str<temp) // run a loop till the start and end pointer meet

    {

        var=*str;

        *str++=*temp;

        *temp--=var;

    }

}

int main()

{

    char str[]="THIS IS IT..";

    char* temp=str;

    printf("Original String is:\n%s\n\n",str);

    printf("String after reversal is : \n");

    InplaceRev(temp);

    printf("%s",temp);

    return 0;

}

Viva La Raza

Sid

C Program to find Middle element in a linked list

Approach #1:

The Naïve way to do this, is to loop through the linked list and increment a count variable with every iteration till null is encountered. Then finally traverse again from the start to count/2.

Isn’t this the obvious approach…..

Let’s go to the not so obvious one…

 Approach#2:

Maintain two pointers from the start of the linked list. A fast and a slow pointer. Increment slow pointer by one and the fast pointer by two. When the fast one reaches the end , the slow one wil reach the middle node of the linked list.

Let’s try to code it:

Program:

#include<stdio.h> /*for printf & scanf*/

#include<stdlib.h> /*for malloc*/

struct node

{

    int data;

    struct node* next;

};

void insert(struct node** head_ref,int data)

{

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

    temp->data=data;

    temp->next=(*head_ref);

    (*head_ref)=temp;

}

void findMid(struct node* head)

{

    struct node* slow_ptr=head;

    struct node* fast_ptr=head;

    if (head!=NULL)

    {

        while(slow_ptr&&fast_ptr&&fast_ptr->next)

    {

        slow_ptr=slow_ptr->next;

        fast_ptr=fast_ptr->next->next;

    }

    }

    printf("\n\nThe Middle point of the given linked list is %d\n",slow_ptr->data);

}

void printList(struct node* head)

{

    struct node*temp=head;

    while(temp)

    {

       printf("%d -> ",temp->data);

       temp=temp->next;

    }

    printf("NULL");

}

int main()

{

    struct node* head=NULL;

    int i;

    for(i=1;i<=5;i++)

        insert(&head,i);

    printf("\nLinked List : \n\n");

    printList(head);

    findMid(head);

    return 0;

}

Viva La Raza

Sid

C Program to check whether two trees are identical or not

Two trees are identical if they have the same data arrangement w.r.t each other.

Algorithm:

identicalTrees(Tree1,Tree2)

1. Check if both trees are empty if so then return 1;

2. Recursively check for the following tree:

         a.       Return 1 if both have same data

         b.      Check left tree recursively : identicalTrees(tree1->left,tree2->left)

         c.       Check right tree recursively : identicalTrees(tree1->right,tree2->right)

         d.      Return 1 if a,b,c are true else return 0;

      3. Return 0 if one tree is empty and other is not.

    

   Program:

   

   /*Program to check whether two trees are identical or not*/

   #include<stdio.h> /*for printf & scanf*/

   #include<stdlib.h>/*fro malloc & calloc */

   /*structure to define tree node*/

   struct node

  {

    int data;

    struct node* left;

    struct node* right;

   };

   /*function to insert a new node in tree*/

   struct node* insert(int new_data)

  {

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

    temp->data=new_data;

    temp->left=NULL;

    temp->right=NULL;

    return (temp);

  };

   /*function return true or 1 if both trees are idential*/

   int identicalTrees(struct node* tree1,struct node* tree2)

   

{
    else if(tree1!=NULL && tree2!=NULL)
}
}
    tree1=insert(1);
    tree2=insert(1);
        if(identicalTrees(tree1,tree2))
    return 0;

    if(tree1==NULL && tree2==NULL)

       return 1;

        return(

               (tree1->data==tree2->data)&&

               (identicalTrees(tree1->left,tree2->left))&&

               (identicalTrees(tree1->right,tree2->right))

               );

    else

        return 0;

   int main()

  {

    struct node*tree1=NULL;

    struct node*tree2=NULL;

    tree1->left=insert(2);

    tree1->right=insert(3);

    tree1->left->left=insert(4);

    tree1->left->right=insert(5);

    tree2->left=insert(2);

    tree2->right=insert(3);

    tree2->left->left=insert(4);

    tree2->left->right=insert(5);

            printf("Both tree are identical");

        else

            printf("Both tree are not identical");

   

   }

Viva La Raza

Sid