AVL Tree Deletion

Algorithm

    Perform  a recursive BST deletion algorithm.

    Now from parent of deleted node(now current node) we have to traverse up to the root.

       For every current node , 
       Find balance of current node.
       If current node is imbalanced,balance it and update heights of required nodes.
       If current node is balanced,just update height of current node.
       return current node to parent.Now parent becomes current node.

   Stop when all nodes become balanced.

Key points

1.    The height changes at only nodes between the parent of deleted node(pd) and the root.

2.    When traversing up from pd to root , rebalancing the 1st imbalanced node doesn’t rebalance other imbalanced nodes.

Code

node* del(node* curr,int key)
{
    int bal;

    if(curr == NULL)
        return curr;

    if(key < curr->key)
        curr->left = del(curr->left,key);

    else if(key > curr->key)
        curr->right = del(curr->right,key);

    else                                                        //key found
    {
        if(curr->left==NULL || curr->right==NULL)               //no child or atmost 1 child
        {
            node* temp = curr->left?curr->left:curr->right;

            if(temp == NULL)                                   //leaf node
                curr = NULL;

            else                                              //1 child
                curr = temp;

        }
        else                                                 //node with 2 children
        {
            node* temp = inorder_succ(curr);
            curr->key = temp->key;

            curr->right = del(curr->right,curr->key);       //go towards temp i.e inorder succ
        }
     }

    if(curr == NULL)                                       //only root node in tree
        return curr;


    bal = getbal(curr);

    if(bal > 1 || bal < -1)
        return balance(bal,curr);


    curr->height = findht(curr);

    return curr;
}

node* inorder_succ(node* curr)
{
    curr = curr->right;

    while(curr->left!=NULL)
        curr=curr->left;

    return curr;
}

int getbal(node* curr)
{
    return findht(curr->left) - findht(curr->right);
}

int findht(node* curr)
{
      if(curr==NULL)
          return -1;
      return maxi(findht(curr->left),findht(curr->right)) + 1;
} 

int maxi(int lh,int rh)
{
     if(lh>=rh)
        return lh;
     return rh;
}

node* balance(int bal,node* curr)
{
    if(bal > 1)
    {
         if(getbal(curr->left) >= 0)                      //  LL
             return rotright(curr);
         else                                             //  LR
         {
             curr->left = rotleft(curr->left);
             return rotright(curr);
         }
    }
    if(bal < -1)
    {
         if(getbal(curr->right) <= 0)                    //  RR
             return rotleft(curr);
         else                                            //  RL
         {
             curr->right = rotright(curr->right);
             return rotleft(curr);
         }
    }
    return NULL;                                         //to avoid warning
}

node* rotright(node* curr)              //curr points to node that violates AVL tree property
{
    node* newroot = curr->left;
    curr->left = newroot->right;
    newroot->right = curr;

    curr->height = findht(curr);
    newroot->height = findht(newroot);

    return newroot;
}


node* rotleft(node* curr)               //curr points to node that violates AVL tree property       
{
    node* newroot = curr->right;
    curr->right = newroot->left;
    newroot->left = curr;

    curr->height = findht(curr);
    newroot->height = findht(newroot);

    return newroot;
}

3 Cases

Deletion of leaf node(28)

Deletion of node with 1 child (25)

Deletion of node with 2 children (20)

Key Point

When 25 is deleted , node 20 becomes imbalanced.As 20 is left burdened (height of left subtree > height of right subtree).First L comes from there.Then we go to left i.e 15.But for 15,left and right sutrees are equally burdened(of same height).So here as we had traversed left first , we again take left.So it becomes LL case.Same goes for RR case.

So,if the two sides are equal, go to the same side as the parent is to the grandparent.

Two sides of node 15 were equal.We went to the left side as 15 was left child of 20.