Binary Search Tree

The goal of this lab period is to build a Binary Search Tree.

---

Tasks

Testing

As always, as you are coding up this project create testing files for each class you create exercising the public methods implemented in this class. A reminder that from here on we'll be expecting you to write complete tester classes.

MapSet

This week, we will be building a Binary Search Tree that maps a set of keys to specific values. For example, perhaps we might want to keep track of a list of student IDs and map the IDs to the student they represent. In this case, the keys would be the IDs and the Students themselves would be the values. Because our keys are inherently just Strings, we could use lexicographic ordering to sort them, and hence store them in a binary search tree for relatively fast lookup.

In particular for this project, we will be implementing this MapSet interface. Take a minute to peruse the file: you will notice an inner class called KeyValuePair: think of this as the specific pairing of the key to its asociated value. These KeyValuePairs will be the objects that are actually getting stored into the BST, which will be sorted by the keys within the pair.

KeyValuePairs are generic-based, so they can be used with any underyling data type. For example, in the above idea of mapping String IDs to Student objects, I might make a KeyValuePair by writing something like KeyValuePair<String,Student>.

BSTMap

1. Declaring the class

   This class will be a Binary Search Tree that implements the MapSet methods: as such, our class declaration should in the very least have: public class BSTMap<K, V> implements MapSet<K, V> . If you'd like, you can add other interfaces to implement (like Iterable<K>, or Iterable<V>, etc.) but they are not required.

   This BST will be Node-based: as such, we'll need an inner Node class to organize our entries.

2. The Node class

   After declaring the class, we'll want an inner Node class, just as in our previous LinkedLists. However, this time our data is the KeyValuePair holding the associated Key and Value. The easiest way to implement Nodes in this case is to declare the class as: private static class Node<K, V> extends KeyValuePair<K, V>. By doing it this way, we'll build the Node class on top of the KeyValuePair class, to reduce the amount of new code we have to write. The only new fields the Node class will introduce are 2 fields for the left and right child nodes.

   

   The only method you (probably) need for the Node class is just a constructor: public Node(K key, V value). This should call the constructor of its parent class (using the super keyword) and leave the left and right children as null.

3. The fields of the BSTMap class

   The BSTMap itself only needs to keep track of 3 fields:

   • The root Node<K, V>, from which we can reach every other Node
   • The int size, or the number of entries in the mapping.
   • The Comparator<K> of the structure, which will help us organize the structure.

4. The constructor(s) of the BSTMap class

   In order to organize the structure of our BSTMap, we'll look to our Comparator field above. A Comparator<K> has a compare(K key1, K key2) method by which we can compare two keys to determine which is greater. See Java's doc page for more info.

   If the user gives us a comparator, then we can just use it. If they don't, then whatever the underlying type K is, it must be 'naturally' comparable. There is a Java interface that marks this, namely the Comparable interface.

   Implement the following two constructors:

   • public BSTMap(Comparator<K> comparator): if comparator isn't null, saves it to the matching field. Otherwise (if it is null), creates a new Comparator<K> assuming that K is Comparable.
   • public BSTMap(): calls the first constructor with a null Comparator.

5. The methods of the BSTMap class The methods you need to create are simply the methods inherited from the MapSet interface.
   • public int size(): returns the size.
   • public void clear(): resets fields to default values
   • public V put(K key, V value): Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced. Does nothing if value is null. Returns the previous value associated with key, or null if there was no mapping for key. For this method, you should implement a recursive helper function:

     private V put(K key, V value, Node<K, V> cur) {
         if (comparator.compare(key, cur.getKey()) < 0){
             if (there is a Node to the left of cur){
                 return the recursive call's result to the left
             } else {
                 insert a new Node with the given KeyValuePair to the left of cur
                 return null
             }
         } else if (comparator.compare(key, cur.getKey()) > 0){
             if (there is a Node to the right of cur){
                 return the recursive call's result to the right
             } else {
                 insert a new Node with the given KeyValuePair to the right of cur
                 return null
             }
         } else { // in this case, cur.getKey() == key
             Set the value of cur's KeyValuePair to be the given value and return the old one
         }

   • public V get(K key): Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key. For this method, you should implement a private recursive helper function: private V get(K key, Node<K, V> cur)
   • public boolean containsKey(K key): Returns true if this map contains a mapping for the specified key to a value.
   • public ArrayList<K> keySet(): Returns an ArrayList of all the keys in the map in sorted order from least to greatest. While not required, I would probably use a helper function such as

     private void keySet(Node<K, V> cur, ArrayList<K> output)
         if cur is null
             return;
         
         recurse to the left
         add my own key to the output
         recurse to the right 

     By doing so, the method for keySet() is as simple as calling our recursive helper function with a new ArrayList.
   • public ArrayList<V> values(): Returns an ArrayList of all the values in the map in the same order returned by keySet()
   • public ArrayList<KeyValuePair<K, V>> entrySet(): Returns an ArrayList of each KeyValuePair in the map in the same order as the keys as returned by keySet().
   • public String toString(): Returns a String that represents the BSTMap accurately depicting the levels. For example, if I input the KVPs (10, "ten"), (1, "one"), (20, "twenty"), (15, "fifteen") in that order, I might use the following String representation:

       right: <20 -> twenty>
         left: <15 -> fifteen>
     root: <10 -> ten>
       left: <1 -> one>

   • public int maxDepth(): returns the length of a maximal root to leaf (a leaf is a Node which has no children) path.
   • public V remove(K key): removes the given key from the structure and returns whatever value is currently associated with it. Be careful to not delete all of that Node's children though! As a suggestion, I recommend the following pseudocode:

     public V remove(K key){
         find the Node to remove
         call handleReplacement (that node, its parent)
     }
     
     private void handleReplacement(Node toDelete, Node toDeleteParent){
         Node replacement; // to be found in the following conditionals
         if (no left child) replacement is just the right
         else if (no right child) replacement is just the left
         else { // we'll have to find it. 
             set replacement to be the next largest (or smallest) Node
             recursively call handleReplacement on this Node (or just do it yourself, I guarantee you this node has just one child)
         }
     
         update toDeleteParent's child (which ever one is currently toDelete) to be replacement
     }

   To help you understand the use of both constructors, here's some code you could try running:

   public static void main(String[] args) {
       // this will sort the strings lexicographically (dictionary-order)
       BSTMap<String, Integer> words = new BSTMap<>();
       words.put("ten", 10);
       words.put("five", 5);
       words.put("three", 3);
       System.out.println(words);
   
       // this will sort the strings in reverse lexicographic order
       BSTMap<String, Integer> wordsReverse = new BSTMap<>(new Comparator<String>() {
   
           @Override
           public int compare(String o1, String o2) {
               return o2.compareTo(o1);
           }
   
       });
       wordsReverse.put("ten", 10);
       wordsReverse.put("five", 5);
       wordsReverse.put("three", 3);
       System.out.println(wordsReverse);
   }
                   

---

When you are done, you can proceed to the project.

---