Binary Search Tree – Part 3

Share on Google+Share on LinkedInEmail this to someoneShare on FacebookTweet about this on Twitter

Finally this is third article on BST and in this last one we are going to go trough implementation details of algorithm for removing element from binary tree, keep in mind that code below will rely on code that has been presented in first part of this article. We shall first take a look at method in the Node class:

public Node removeValue(Node parent, int removeValue){
   if(value == removeValue){
      //case when value for removal is same as value of the current node - this node needs to be removed from the tree
      if(this.leftNode == null && this.rightNode==null){
         //case when node is leaf
      }else if(leftNode!=null && rightNode==null){
         //case when node has left child and no right child
      }else if(leftNode==null && rightNode!=null){
         //case when node has left child and no right child
      }else if(leftNode!=null && rightNode!=null){
         //case when node has two children
      }</pre>
<pre>      return this;
  }else if(value>removeValue){
      // this is case when current node value is greater than value for removal
  }else{
      //this case is when current node value is smaller than value for removal
  }
}

Since we are going to use recursion in this method and based on algorithm for removing node from the tree, this method requires to have Node parameter representing parent of the current node.

I guess comments in the code gives you explanation about this part of implementation, so now I shall just dive into details of implementing each point in above code,  so let’s start with case when value for removal is same as value of the current node – case when algorithm finds node that is supposed to be for removal, as stated in part 2 in this series of articles on BST, there are tree cases to be considered when removing node from the tree, first one is when node is leaf and in that case node should be removed by setting parent’s child to null

if(this.leftNode == null && this.rightNode==null){
   if(parent.leftNode == this){
      parent.leftNode = null;
   }else{
      parent.rightNode = null;
   }
}

Simply determining if current node is same node as the parent left or right child code above sets proper child of parent to null.

Second case when removing node from tree is when there is only once child of node marked for removal:


else if(leftNode!=null && rightNode==null){
   if(parent.leftNode == this){
      parent.leftNode = this.leftNode;
   }else{
      parent.rightNode = this.leftNode;
   }
 }else if(leftNode==null && rightNode!=null){
   if(parent.leftNode == this){
      parent.leftNode = this.rightNode;
   }else{
      parent.rightNode = this.rightNode;
   }
 }

 

So in case there is a left child of a node for removal, this child should take current node’s  position, in that case what we do is first determine if current node is left or right child of parent and then just set that parent points to the child of node for removal. Code for the case when node for removal has right child follows same logic.

Now third and most complex case in this algorithm is when there are both children for node that is determined for removal. Algorithm specifies that first we need to find node with minimum value for right sub-tree of node and then do the swap of places in the tree for node with minimal value and node for removal:


else if(leftNode!=null && rightNode!=null){
   Node minNode = this.rightNode.findMin();
   rightNode.removeValue(this, minNode.getValue());
   minNode.leftNode = this.leftNode;
   minNode.rightNode = this.rightNode;
   if(parent.rightNode == this){
      parent.rightNode = minNode;
   }else{
      parent.leftNode = minNode;
   }
}

Looking at the code above you can see as first step we determine node with minimal value in right sub-tree of current node, this is done by using method we described and implemented in first part of this article’s series. Next step is actually calling recursively removeValue method in order to remove node with minimal value in the right sub-tree. Once this node with minimal is removed from sub-tree what is left is to replace position of a current node, first pointers to the children of node and than pointer of a parent to the replacing node.

So with this part of code we have covered all tree cases when node is supposed to be removed. Now the rest of the method is recursively calling removeValue method for left or right child depending on the case if current node’s value is greater or smaller than the value provided as method parameter.


else if(value>removeValue){
   if(leftNode!=null){
      return leftNode.removeValue(this, removeValue);
   }else{
      return null;
   }
}else{
   if(rightNode!=null){
      return rightNode.removeValue(this, removeValue);
   }else{
      return null;
   }
}

I believe that last peace of this code is self explanatory so there is no need to go into deeper analysis of this piece of code.

Full code of the method looks like this:


public Node removeValue(Node parent, int removeValue){
   if(value == removeValue){
      if(this.leftNode == null && this.rightNode==null){
         if(parent.leftNode == this){
            parent.leftNode = null;
         }else{
            parent.rightNode = null;
         }
      }else if(leftNode!=null && rightNode==null){
         if(parent.leftNode == this){
             parent.leftNode = this.leftNode;
         }else{
             parent.rightNode = this.leftNode;
         }
      }else if(leftNode==null && rightNode!=null){
         if(parent.leftNode == this){
            parent.leftNode = this.rightNode;
         }else{
            parent.rightNode = this.rightNode;
         }
       }else if(leftNode!=null && rightNode!=null){
          Node minNode = this.rightNode.findMin();
          rightNode.removeValue(this, minNode.getValue());
          minNode.leftNode = this.leftNode;
          minNode.rightNode = this.rightNode;
          if(parent.rightNode == this){
             parent.rightNode = minNode;
          }else{
             parent.leftNode = minNode;
          }
       }
       return this;
     }else if(value>removeValue){
        if(leftNode!=null){
           return leftNode.removeValue(this, removeValue);
        }else{
           return null;
        }
      }else{
        if(rightNode!=null){
           return rightNode.removeValue(this, removeValue);
        }else{
           return null;
        }
      }
   }

One more thing that we need to implement so that we have this picture complete is method in the class BinaryTree. We have to be aware that this method needs to take care of one case and that is when node in the root has value that we are looking to remove from the tree, in that case based on what we implemented as removeValue method in Node class can not be directly called since we need to provide parent node, in this case simple thing is to add “virtual node” as a parent of root node and call removeValue method by passing root node as a parameter.

public Node removeValue(int removeValue){
   if(root.getValue()==removeValue){
      Node n = new Node();
      n.setLeftNode(root);
      return n.removeValue(root, removeValue);
   }else if(root.getValue()>removeValue){
      return root.getLeftNode().removeValue(root, removeValue);
   }else{
      return root.getRightNode().removeValue(root, removeValue);
   }
 }

So as you can see above, again tree cases are handled, when value for removal is same as root node’s value (case explained above code), when root’s value is greater and when root’s value is less than value provided as a parameter of a method.

Finally, lets do small test that will produce output of the tree for several executions of removal method. We shall initially construct a tree that was used as an example in second part of this article series:

public class Test {
   public static void main(String[] args) {
      BinaryTree tree = buildNewTree();
      tree.printTree();
      System.out.println("removing 31");
      tree.removeValue(31);
      tree.printTree();
      System.out.println("removing 14");
      tree.removeValue(14);
      tree.printTree();
      System.out.println("removing 19");
      tree.removeValue(19);
      tree.printTree();
  }

  public static BinaryTree buildNewTree(){
     BinaryTree tree = new BinaryTree(16);
     tree.addNewValue(14);
     tree.addNewValue(11);
     tree.addNewValue(12);
     tree.addNewValue(5);
     tree.addNewValue(8);
     tree.addNewValue(19);
     tree.addNewValue(17);
     tree.addNewValue(29);
     tree.addNewValue(21);
     tree.addNewValue(26);
     tree.addNewValue(25);
     tree.addNewValue(27);
     tree.addNewValue(31);
    return tree;
   }
}

The code above should produce output:

5, 8, 11, 12, 14, 16, 17, 19, 21, 25, 26, 27, 29, 31, ;
removing 31
5, 8, 11, 12, 14, 16, 17, 19, 21, 25, 26, 27, 29, ;
removing 14
5, 8, 11, 12, 16, 17, 19, 21, 25, 26, 27, 29, ;
removing 19
5, 8, 11, 12, 16, 17, 21, 25, 26, 27, 29, ;

I hope that you have enjoyed reading this three part series on the BST implementation. I am planing next to start writing on algorithms for sorting so I hope that you shall enjoy reading those too. Have a nice day …

Share on Google+Share on LinkedInEmail this to someoneShare on FacebookTweet about this on Twitter
Posted in General Programming Tagged with: , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

*

Subscribe for Newsletter

Categories