Due: Monday, April 17, 2017, 11:59 pm

Binary Search Trees as Maps

The goal of this lab period is to give you an opportunity to implement a map with a binary search tree.

Tasks

  1. Make a new folder for this week's project.
  2. Download MyMap.java. Open and read it. Note that it is a generic interface that requires two types - a type associated with keys and a type associated with values.
  3. Create a KeyValuePair class that is to be used by the binary search tree.

    KeyValuePair<Key,Value>

    It supports a generic type for the key (K) and a generic type for the value (V), and should have fields to contain a key and a value. It also implements the following methods:

    • public KeyValuePair( Key k, Value v ) the constructor initializing the key and value fields.
    • public Key getKey()> returns the key.
    • public Value getValue() returns the value.
    • public void setValue( Value v ) sets the value.
    • public String toString() returns a String containing both the key and value.

    Test your class. Make sure it is in perfect working order.

  4. Create a new file BSTMap.java. In this file, you will need at least 3 classes:
    • BSTMap the main tree class
    • TreeNode the tree node class, which can go after the BSTMap tree, rather than being nested
    • AscendingStringComparator a comparator for keys, which works only for Strings and also shouldn't be nested.

    Below is a template you can use for these three classes.

    	public class BSTMap<K,V> implements MyMap<K,V> {
    
    	    private TreeNode<K,V> root;
    	    private Comparator<K> comparator;
        
    	    public BSTMap( Comparator<K> comparator ) {
    	        this.comparator = comparator;
    	        // WARNING: THIS CODE IS INCOMPLETE. You still need to initialize the root.
    	        // and code that initializes root
    	    }
        
    	    public void put( K key, V value ) {
    	        // Call the TreeNode's put method. It will need the comparator passed in to it.
    	    }
        
    	    public static void main( String[] args ) {
    	        System.out.println( "test code" );
    	        BSTMap<String,Integer> map = new BSTMap<String,Integer>(new AscendingStringComparator());
    	        map.put( "B", 2 );
    	        map.put( "A", 1);
    	        map.put( "D", 2 );
    	        map.put( "C", 2 );
    	        map.printInOrder();
    	        System.out.println();
    	        System.out.println( "Has A: " + map.containsKey( "A" ) );
    	        System.out.println( "Has G: " + map.containsKey( "G" ) );
    	        map.put( "D", 3 );
    	        System.out.println( "D now has value " + map.get( "D" ) );
    	        System.out.println( "The tree has " + map.size() + " elements" );
    	        System.out.println( "The tree has " + map.depth() + " levels" );
    	        ArrayList<KeyValuePair<String,Integer>> pairs  = map.getPairs();
    	        System.out.println( "In useful order: " );
    	        System.out.println( pairs );
    	    }        
    	}
    
    	//---------------------------------------
    
    	class TreeNode<Key,Value> {
    	    private KeyValuePair<Key,Value> pair;
    	    private TreeNode<Key,Value> left;
    	    private TreeNode<Key,Value> right;
    
    	    public TreeNode( Key this_key, Value this_val, TreeNode<Key,Value> l, TreeNode<Key,Value> r ) {
    	        ; // code here
    	    }
        
    	  // Methods to support insert, contains, printing, getPairs, etc.
    
    	} // end class TreeNode
    
    	class AscendingStringComparator implements Comparator<String> {
    	    public int compare( String i1, String i2 ) {
    	        // returns negative number if i2 comes after i1 lexicographically
    	        return i1.compareTo(i2);
    	    }
    	}
    	//---------------------------------------
    

    Implement the methods required to support the MyMap interface. You will probably also want to add code to print the tree, for debugging purposes. It would also be a good idea to implement as few methods as you can at a time, so you can test as you go (just make stubs for the yet-to-be implemented methods). (Note: A stub is a temporary version of a function that doesn't really do anything but which compiles.)

    One of the more complicated aspects of the generic binary search tree is that it requires a comparator. It will use that comparator to add new pairs to the tree as well as to search the tree. The pair comparator itself needs to store and use a comparator for just the tree types.

    Another plan that you should know about right now is that we are designing the tree so that is it easy to reconstruct it. Once we get to the project, we will be constructing a relatively small tree from a very large data set. We will want to look at the tree for a particular data set multiple times. The most efficient way to do this will be to write a file containing the tree data, then read it in, adding the elements to the tree one at a time (instead of re-reading the original data set). The order in which we add these elements matters. If we add them in sorted order, what will the tree look like? However, if we add them in the order we get from a pre-order traversal, then reconstructing the tree by adding the elements one at a time will work beautifully. This means

    public ArrayList<KeyValuePair<K,V>> getPairs(); should return a list of pairs from a pre-order traversal.

    Test your code thoroughly and make sure it is in perfect working order. In particular, make sure your getPairs method returns the pairs in pre-order.

When you are ready, move on to Project 7.

© 2017 Ying Li. Page last modified: .