Thursday, 16 June 2016

Implementing Binary Search Tree in Jeliot tool

The full source code that you can run on Jeliot tool for the Binary Search Tree algorithm is below.

Source Code:

import jeliot.io.*;
import java.util.Scanner;

 /* Class BinarySearchTree */
 public class BinarySearchTree{
     public static void main(String[] args){                
        Scanner scan = new Scanner(System.in);
        /* Creating new Binary Search Tree */
        BST BSTree = new BST();
        System.out.println("Binary Search Tree\n");         
        int ch;
        do{
            System.out.println("Press 1 to Insert and 2 to Search: ");
            int choice = scan.nextInt();           
            switch (choice){
            case 1 :
                System.out.println("Enter element to Insert: ");
                BSTree.insert( scan.nextInt() );                    
                break;                                             
            case 2 :
                System.out.println("Enter element to Search: ");
                System.out.println("Element Found : "+ BSTree.search( scan.nextInt() ));
                break;                                            
            default :
                System.out.println("Invalid Choice!!");
                break;  
            }

            System.out.println("\nPress 1 to continue, anything else to exit: ");
            ch = Integer.parseInt(scan.nextLine());                       
        } while (ch == 1);    
    }
 }

 /* Class BST */
 class BST {
     private BSTNode root;
     int iterations = 0;
     /* Constructor */
     public BST(){
         root = null;
     }
     /* Function to check if tree is empty */
     public boolean isEmpty(){
         return root == null;
     }
     /* Functions to insert data */
     public void insert(int data){
         root = insert(root, data);
     }
     /* Function to insert data recursively */
     private BSTNode insert(BSTNode node, int data){
         if (node == null)
             node = new BSTNode(data);
         else{
             if (data <= node.getData())
                 node.left = insert(node.left, data);
             else
                 node.right = insert(node.right, data);
         }
         return node;
     }
   
     /* Functions to search for an element */
     public boolean search(int val){
         iterations = 0;
         return search(root, val);
     }
     /* Function to search for an element recursively */
     private boolean search(BSTNode r, int val){
         boolean found = false;
         while ((r != null) && !found){
             int rval = r.getData();
             if (val < rval)
                 r = r.getLeft();
             else if (val > rval)
                 r = r.getRight();
             else{
                 found = true;
                 break;
             }
             found = search(r, val);
             iterations++;
         }
         System.out.println("Number of iterations: " + iterations);
         return found;
     }
   
 }

 /* Class BSTNode */
 class BSTNode{
     BSTNode left, right;
     int data;

     /* No argument Constructor*/
     public BSTNode(){
         left = null;
         right = null;
         data = 0;
     }
     /* Constructor with data argument */
     public BSTNode(int n){
         left = null;
         right = null;
         data = n;
     }
     /* Function to set the left node */
     public void setLeft(BSTNode n){
         this.left = n;
     }
     /* Function to set the right node */
     public void setRight(BSTNode n){
         this.right = n;
     }
     /* Function to get the left node */
     public BSTNode getLeft(){
         return this.left;
     }
     /* Function to get the right node */
     public BSTNode getRight(){
         return this.right;
     }
     /* Function to set the data of a node */
     public void setData(int d){
         this.data = d;
     }
     /* Function to get node's data */
     public int getData(){
         return this.data;
     }    
 }

Description of the algorithm:

This is a linked implementation of a Binary Search Tree.

The main class, BinarySearchTree, is the only class that is executable in this and it asks for two options: Insert and Search an element.

The class BST implements the two functions for insertion and searching. The search function recursively searches for an input value and counts the number of iterations required and displays the iteration count when each iteration gets completed. When an element is found, it returns true, otherwise it simply returns false to show that there is no such element in the tree.

BST class depends on BSTNode class which defines the structure of a single node of the Binary Search Tree. The getters and setters for defining the node structure and inserting/retrieving data into node are defined in the BSTNode class. 

Asymptotic analysis of the Search Function:

     /* Function to search for an element recursively */
     private boolean search(BSTNode r, int val){
         boolean found = false;
         while ((r != null) && !found){
             int rval = r.getData();
             if (val < rval)
                 r = r.getLeft();
             else if (val > rval)
                 r = r.getRight();
             else{
                 found = true;
                 break;
             }
             found = search(r, val);
             iterations++;
         }
         System.out.println("Number of iterations: " + iterations);
         return found;
     }

As we can see, the search function only searches a single-half of the tree depending on the search value. If the value is equal to root, it is simply returned. Otherwise, the only right sub-tree is searched for value larger than root and only left sub-tree is searched for value smaller than root. All of this is recursive i.e. the same policy applies to sub-trees of the current node until the value is found or the whole tree is traversed. Hence, the time taken to access nth node is equivalent to log n. Here too, the number of iterations to find ‘9’, which was the 11th item inserted, is 3 log 11 = 3.459 (*Note that base of log here is 2 as it is a binary search).


Therefore, the complexity of Binary Search is O(log n)

No comments:

Post a Comment

Was this post helpful? Ask any questions you have, I will try to answer them for you.

Follow by Email