HW 5: BST Map

Solution

You can find a solution BST here.

Overview

This is a programming homework assignment where you will implement a Binary Search Tree implementation of a Map. It is due via the submission system.

Due Date

This homework is due Wednesday, October 11th at 2359 via ic312-submit

Grading

The assignment is graded out of 100 points. We will grade your assignment on two main dimensions:

Performance: Your BST should be implemented such that it achieves O(h) insert and find
Programming Style: Your BST should be implemented in a natural, recursive manner that matches the tree structure of a BST

While a small main() method is provided as a sanity check. We will test your assignment with many, many, many more insertions/finds than that.

Finally, you are not required to balance the BST. Instead you may let the tree go out of balance if that is what the order of the inserts dictates.

Submission and Starter Code

Submission must occur via ic312-sumit

You can obtain the starter code via ic312-up. You will find the following files in the ~/ic312/hw/05 directory:

BST.java : The file you must complete
ListMap.java : A CircularArrayList implementation of a map
ic312/ : package of ic312 data structures and interfaces
- List.java : List interface
- Stack.java : Stack interface
- Queue.java : Queue interface
- Map.java : Map interface (file you should reference)
- LinkedList.java : Linked List implementation of a List, Stack and Queue
- ArrayList.java : Array List implementation of a List, Stack
- CircularArrayList.java: Circular Array List implementation of a List, Stack, and Queue
- Pair.java : A pair class to store two objects of potentially different types

You are not allowed to use anything from java.util to complete this homework.

Description

In this assignment you will complete the implementation of the Binary Search Tree (BST.java) which implements the Map interface (defined in ic312/Map.java), and as described below:

public interface Map<K,V>{

  /**
   * Retrieve a value from the map via it's key. 
   *
   * @param key : the key to be looked up
   * @return    : the value associated with that key or null if the key
   *              is not in the map
   **/
  public V get(K key);

  /**
   * Set a key to an associated value. If the key is present, the
   * value is updated. If the key is not present, a new key,value is
   * inserted into the map.
   *
   * @param key : the key to be be set
   * @param value : the value associated with that key
   **/
  public void set(K key, V value);


  /**
   * Retrieve the number of distinct keys stored in the map
   *
   * @return : the number of distinct keys stored in the map
   **/
  public int size();

  /**
   * Returns a List of unique keys stored in the map. The order of
   * the keys should match the order of the list return by values().
   *
   * @return : a list of distinct keys stored in the map
   **/
  public List<K> keys();

  /**
   * Returns a List of values stored in the map. The order of
   * the values should match the order of the list return by keys().
   *
   * @return : a list of values stored in the map
   **/
  public List<V> values();

Once you've completed the implementation, the following main method (which you can add to your BST.java file) should function as expected:

public static void main(String args[]){

      Map<Integer,String> map = new BST<Integer,String>();

      map.set(222222, "Ernest Hemingway");
      map.set(111111, "Ray Charles");
      map.set(333333, "John F Kennedy");

      System.out.println(map.get(333333)); // should print John F Kennedy
      System.out.println(map.get(222222)); // should print Ernest Hemingway

      String name = map.get(444444);

      if (name == null)
          System.out.println("444444 is not in the map");   // should do this
      else
          System.out.println("this is not right: " + name); // not this

      System.out.println(map.size()); // should print 3

      System.out.println();
      System.out.println("Keys:");
      for(Integer i : map.keys()){
          System.out.println(i);  //this will print all the keys, in order
      }
      System.out.println();

      System.out.println("Values:");
      for(String v : map.values()){
          System.out.println(v); //this will print all the values, in order of their keys
      }
      System.out.println();

  }

Just to show you one other implementation of a map, we've provided you with ListMap.java, a map implementation that uses a CircularArrayList.