-1

As you know how avl should be balanced after deletion of a node, I'll get to point. For starting, Im considering deleteing 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. :-)

2
Contributors
1
Reply
2
Views
4 Years
Discussion Span
Last Post by nitin1
-1

hey! i will advice you one thing here. Just read once CLRS topic AVL trees. the explaination which they have given is blossom! believe me. seen you code a little bit and seen some logical error. have made full AVL tree in last semester. just read once and you will be able to judge yourself. if you still find any problem, then post it here. thanks

Votes + Comments
NO Idea what you are talking.
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.