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) -->>   

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. :-)

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

commented: NO Idea what you are talking. +0
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.