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