Deletion in AVL Tree

Question

As you know how avl should be balanced after deletion of a node, I'll get to point. For starting, Im considering deleting a node with no children.

For Example a Tree:

        10
      /     \
     5      17
   /  \    /  \ 
   2  9   12  20
    \           \
     3          50

Lets say deletevalue(12);

Then Tree should be after deletion:

        10
      /     \
     5      17
   /  \       \ 
   2  9       20
    \           \
     3          50

Now, we see tree is balanced at node 17, because by formula, its Balance Factor = height( left subtree [left tree is null so -1] ) - height (right subtree) = -2

So we balance the tree by checking if its right-right case or right-left case.

If BalanceFactor(17's right) = -1
    perform SingleLeftRotation(17);
else if BalanceFactor(17's right) = -1
    perform DoubleRightLeftRotation(17);

Similar is case if Balance Factor of 17 is 2, i.e. it is left high, then its respective rotations. //for bF(17) = 2

If BalanceFactor(17's left) = 1
    perform SingleLeftRotation(17);
else if BalanceFactor(17's left) = -1
    perform DoubleLeftRightRotation(17);

After balancing, tree should become this:

          10
      /     \
     5      20
   /  \    /  \ 
   2  9   17  50
    \           
     3  

This is deletion I have designed.

From main function, I call

bool deletevalue(WA value)
{
    AvLNode<WA> *temp = search(root, value);    //calling search function to find node which has user-specified data & stored its address in temp pointer
    if(temp!=0) //if temp node is not null then
    {
        if(temp->left==0 && temp->right==0) //if temp node don't have any children
        {   deletewithNochild(root, value); }   //call to respective function
        else if( (temp->left!=0 && temp->right==0) || (temp->left==0 && temp->right!=0) )   //if temp node has any 1 child, left or right
        {   deletewithOneChild(temp);   }   //call to respective function
        else if(temp->left!=0 && temp->right!=0)    //if temp node has 2 children
        {   deletewith2Child(temp);     }   //call to respective function

        return true;    //for prompting respective output message
    }
    else
        return false;   //for prompting respective output message
}

as our required node has no child so, following function is envoked.

void deletewithNochild(AvLNode<WA> *temp, WA value) //temp is node which is to be deleted
{
    if(value == root->key)  //if temp is root node then
    {
        delete root;    //free memory of root node
        root = 0;   //nullify root
    }
    else    //if temp is some other node 
    {
        if (value < temp->key)
        {
            deletewithNochild(temp->left, value);
        }
        else if (value > temp->key)
        {
            deletewithNochild(temp->right, value);
        }
        else if (value == temp->key)
        {
            AvLNode<WA> *father = findfather(temp, root);   //calling findfather func to find father of temp node & store its address in father node pointer

            if(father->left==temp)  //if temp is left child of its father
            {
                delete temp;    //free memory of temp node
                father->left=0; //nullify father's left
            }
            else if(father->right==temp)    //if temp is right child of its father
            {
                delete temp;    //free memory of temp node
                father->right=0;//nullify father's right
            }
            return;
        }
        cout<<"\nBalancing";
        if ( balancefactor(temp) == 2)  //if temp is left higher, ie. temp's Balance Factor = 2, then
        {
            cout<<"\t2 ";
            if ( balancefactor(temp->left) == 1 ) //if temp's left node has Balance Factor 1 then
            {
                SingleRightRotation(temp);  //send temp node for rotation because temp is unbalance
            }
            else if ( balancefactor(temp->left) == -1 ) //if temp's left node has Balance Factor -1, then
            {
                DoubleLeftRightRotation(temp);  //send temp for double rotation because temp is unbalance
            }
        }
        else if ( balancefactor(temp) == -2 )   //if temp is right higher, ie. temp's Balance Factor = -2, then
        {
            cout<<"\t-2 ";
            if ( balancefactor(temp->right) == -1 ) //if temp's left node has Balance Factor -1 then
            {
                SingleLeftRotation(temp);   //send temp node for rotation because temp is unbalance
            }
            else if ( balancefactor(temp->right) == 1 ) //if temp's right node has Balance Factor 1, then
            {
                DoubleRightLeftRotation(temp);  //send temp for double rotation because temp is unbalance
            }
        }

    }
}

Here are two utility functions of HEIGHT of node & BALANCE FACTOR of node

int heightofnode(AvLNode<WA> *temp) const
{
    return temp==NULL ? -1 : temp->height;
}


int balancefactor(AvLNode<WA> *temp) const
{
    return ( heightofnode(temp->left) - heightofnode(temp->right) );
}

My output, when I delete 12 becomes (Breadth First Travers) -->> [10] [9] [17]

Kindly help me out, is there any problem with recursion? I have dry-runned again & again but can't understand. Deleteion must be done through recursion otherwise balancing tree would be a bigger hell. Thanks in advance for giving time. :-)

Answer 1

Why does deletewithNochild() call any other delete* methods? If deletewithNochild is called, you are at the node to delete. Simply delete it, move up to it's parent, and check the parents balance factor and rotate if needed. Repeat the rebalancing for each node's parent until you get to the root.

If it helps, I've implemented an AVL tree in Java, if you want a reference.