Homework 5: BST implementation of Map

This is the archived website of IC 312 from the Fall 2014 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

• Due before class on Wednesday, October 8
• Submit using the submit program as 312 hw 05.

All of you are always identified by alpha, which is very frustrating for those of us who have no interest in memorizing which alpha corresponds to which midshipman. Let's fix the problem by making a Map implemented with a Binary Search Tree.

Details

You'll write a class called AlphaMap which will map alphas to names, organizing data in the tree by alphas (small ones to the left, big ones to the right), and have methods such that main methods like the one below will work:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  public class MapMain {   public static void main(String[] args) {     Map map = new AlphaMap();     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   } }

Your AlphaMap class must implement the interface Map<Integer,String> as defined in the Map.java file:

 1 2 3 4 5 6 7 8 9 10 11 12 13  public interface Map {   /** Retrieves the value associated with this key, or null if not found. */   public V get(K key);     /** Assigns a value to be associated with the given key.    * If the key is not already in the map, it gets added.    * Otherwise, if it's already in the map, its associated value is modified.    */   public void set(K key, V value);     /** Returns the number of distinct keys in this map. */   public int size(); }

You'll use methods very similar to ones we've already written in class, you just have to turn it into a Map.

For fun, I've included an implementation of Map<Integer,String>using linked lists, in the class AlphaMapLL.