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/