title: Deletion in AVL Tree
body: <p>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.</p>
  
  <p>For Example a Tree:</p>
  
  <pre><code>        10
        /     \
       5      17
     /  \    /  \ 
     2  9   12  20
      \           \
       3          50
  </code></pre>
  
  <p><em>Lets say deletevalue(12);</em></p>
  
  <p>Then Tree should be after deletion:</p>
  
  <pre><code>        10
        /     \
       5      17
     /  \       \ 
     2  9       20
      \           \
       3          50
  </code></pre>
  
  <p>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</p>
  
  <p>So we balance the tree by checking if its right-right case or right-left case. </p>
  
  <pre><code>If BalanceFactor(17's right) = -1
      perform SingleLeftRotation(17);
  else if BalanceFactor(17's right) = -1
      perform DoubleRightLeftRotation(17);
  </code></pre>
  
  <p>Similar is case if Balance Factor of 17 is 2, i.e. it is left high, then its respective rotations.
  //for bF(17) = 2</p>
  
  <pre><code>If BalanceFactor(17's left) = 1
      perform SingleLeftRotation(17);
  else if BalanceFactor(17's left) = -1
      perform DoubleLeftRightRotation(17);
  </code></pre>
  
  <p>After balancing, tree should become this:</p>
  
  <pre><code>          10
        /     \
       5      20
     /  \    /  \ 
     2  9   17  50
      \           
       3  
  </code></pre>
  
  <p><strong>This is deletion I have designed.</strong></p>
  
  <p>From main function, I call</p>
  
  <pre><code>bool deletevalue(WA value)
  {
      AvLNode&lt;WA&gt; *temp = search(root, value);    //calling search function to find node which has user-specified data &amp; stored its address in temp pointer
      if(temp!=0) //if temp node is not null then
      {
          if(temp-&gt;left==0 &amp;&amp; temp-&gt;right==0) //if temp node don't have any children
          {   deletewithNochild(root, value); }   //call to respective function
          else if( (temp-&gt;left!=0 &amp;&amp; temp-&gt;right==0) || (temp-&gt;left==0 &amp;&amp; temp-&gt;right!=0) )   //if temp node has any 1 child, left or right
          {   deletewithOneChild(temp);   }   //call to respective function
          else if(temp-&gt;left!=0 &amp;&amp; temp-&gt;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
  }
  </code></pre>
  
  <p><em>as our required node has no child so, following function is envoked.</em></p>
  
  <pre><code>void deletewithNochild(AvLNode&lt;WA&gt; *temp, WA value) //temp is node which is to be deleted
  {
      if(value == root-&gt;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 &lt; temp-&gt;key)
          {
              deletewithNochild(temp-&gt;left, value);
          }
          else if (value &gt; temp-&gt;key)
          {
              deletewithNochild(temp-&gt;right, value);
          }
          else if (value == temp-&gt;key)
          {
              AvLNode&lt;WA&gt; *father = findfather(temp, root);   //calling findfather func to find father of temp node &amp; store its address in father node pointer
  
              if(father-&gt;left==temp)  //if temp is left child of its father
              {
                  delete temp;    //free memory of temp node
                  father-&gt;left=0; //nullify father's left
              }
              else if(father-&gt;right==temp)    //if temp is right child of its father
              {
                  delete temp;    //free memory of temp node
                  father-&gt;right=0;//nullify father's right
              }
              return;
          }
          cout&lt;&lt;"\nBalancing";
          if ( balancefactor(temp) == 2)  //if temp is left higher, ie. temp's Balance Factor = 2, then
          {
              cout&lt;&lt;"\t2 ";
              if ( balancefactor(temp-&gt;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-&gt;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&lt;&lt;"\t-2 ";
              if ( balancefactor(temp-&gt;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-&gt;right) == 1 ) //if temp's right node has Balance Factor 1, then
              {
                  DoubleRightLeftRotation(temp);  //send temp for double rotation because temp is unbalance
              }
          }
  
      }
  }
  </code></pre>
  
  <p>Here are two utility functions of HEIGHT of node &amp; BALANCE FACTOR of node</p>
  
  <pre><code>int heightofnode(AvLNode&lt;WA&gt; *temp) const
  {
      return temp==NULL ? -1 : temp-&gt;height;
  }
  
  
  int balancefactor(AvLNode&lt;WA&gt; *temp) const
  {
      return ( heightofnode(temp-&gt;left) - heightofnode(temp-&gt;right) );
  }
  </code></pre>
  
  <p><strong>My output, when I delete 12 becomes</strong>
  (Breadth First Travers) -->> [10] [9] [17] </p>
  
  <p><strong>Kindly help me out</strong>, is there any problem with recursion? I have dry-runned again &amp; again but can't understand. Deleteion must be done through recursion otherwise balancing tree would be a bigger hell.
  <em>Thanks in advance for giving time. :-)</em></p>