Saturday, June 7, 2014

Duplicate Finder [Tree Implementation][Array implementation of nodes] in Java

The program finds duplicate numbers as the users enters them. This is the array implementation using Java.

The array implementation is beneficial when we have to work with a fixed number of almost complete binary trees. This is more space efficient if the tree has more number of leaves so that all the array positions are occupied. If array positions are not being occupied efficiently, consider using the dynamic allocation. If more flexibility of access is needed, dynamically allocated nodes can be used.

The array implementation here uses MAXNODES = 500.
So that we can store a max of 16 numbers in the almost complete binary tree as explained:

As an example let us suppose that the user inputs:

1 2 3 4 5 6 7 8 9 

The numbers up to 8 are stored in array locations: 0 2 6 14 30 62 126 254 according to 2*(p)+2
So that when 9 is entered the next location will be 2*254+2 = 508+2 = 510 >500 (Overflow!)

Now the user can only enter numbers less than 1. So that when the user enters new sequence:

-1 -2 -3 -4 -5 -6 -7 -8  -9

The array location would be: 1 3 7 15 31 63 127 255 according to 2*(p)+1
So that when -9 is encountered the next calculated location is 2*255+1 = 511 > 500 = Overflow!

So that the total number of insertions becomes 8+8 = 16. It is clear that a dynamic allocated implementation would have stored 500 numbers but it would have also included overhead of left and right fields along with the info field for each node in the tree.

Code for the array implementation in Java: 

import java.util.Scanner;

class nodetype{
    int info;
    boolean used;
}

public class arrayDuplicateFinder {

    static int NUMNODES = 500;
    static nodetype[] node = new nodetype[NUMNODES];
       
    static{
        for(int i=0; i<node.length;++i){
            node[i] = new nodetype();
        }
    }
    
    static void maketree(int x){
        
       node[0].info = x;
       node[0].used = true;
       
       for(int i =1;i<NUMNODES;++i){
           node[i].used = false;
       }
   }
   
   static void setleft(int p, int x){
       int q = 2*p+1;
       if(q>=NUMNODES)
            System.out.println("Array overflow!");
       else if(node[q].used)
           System.out.println("Invalid insertion");
       else{
           node[q].info = x;
           node[q].used = true;
       }
   }
   
   static void setright(int p, int x){
       int q = 2*p+2;
       if(q>=NUMNODES)
           System.out.println("Array overflow!");
       else if(node[q].used)
           System.out.println("Invalid insertion");
       else{
           node[q].info = x;
           node[q].used = true;
       }
   }
   
   public static void main(String[] args){
      
       int p = 0,q = 0,number;
       Scanner scan = new Scanner(System.in);
       
       System.out.println("Enter numbers: ");
       number = scan.nextInt();
       maketree(number);
       
       while((number=scan.nextInt())!=-999){
           p = q = 0;
           while(q< NUMNODES && node[q].used && number!=node[p].info){
               p=q;
               if(number<node[p].info)
                   q = 2*p+1;
               else
                   q = 2*p+2;
           }
       
       if(number == node[p].info)
           System.out.println(number+" is a duplicate");
       else if(number<node[p].info)
           setleft(p, number);
       else
           setright(p, number);
     }
   }
}

No comments:

Post a Comment