Binary Search Tree

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


A Note on Process for 2 Week Project:

This project will be completed in 2 weeks. However to ensure that you are making progress on it during the first week, there is a required checkpoint submission on April 16th worth 5/50 points on the project. Submit your code including the BSTMap.java file to the assignment titled "Project 6 CHECKPOINT: BSTMap."

Late submissions: You can use your late days for this checkpoint (if you think it's worthwhile). If you submit this more than 3 days late, you won't get credit for the checkpoint. You can still get credit for the BSTMap part of the main project rubric under the usual system.


Tasks

Testing

We have supplied you with a partial BSTMapTester for the binary search tree that you will use for the lab checkpoint. You are expected to complete the remainder of the tester, as described in comments in the code, as you're working on your BSTMap implementation. You can and should use it to test your code. We will evaluate your code against a completed version of the tester to grade it (our version, not yours!), and we will grade you on whether you filled in this tester. To run it, you will need to implement everything in the MapSet interface. For methods you haven't implemented yet, define the method, and return a placeholder value (e.g. null, -1, etc.).

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.

    A comparison of the Node-based structures we've seen in this class so far

    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 String toString(): Lets you print your BSTMap for testing and debugging. Paste in the code provided below for this. You might need to change some of the field names to line up with your implementation.
      	private String toString( Node cur , int curDepth ) {
      		if ( cur == null ){
      			return "" ;
      		} else{ //Ordering of these call matters for it to be sorted
      			String output = this.toString( cur.leftChild , curDepth + 1 ) ;
      			output += "\t".repeat(curDepth) + cur.toString() + "\n";
      			output += this.toString( cur.rightChild , curDepth + 1 ) ;
      			return output ;
      		}
      	}
      
      	public String toString() {
      		return this.toString( this.root , 0 );
      	}
      		
    • 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 {
                  inset 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)
    • Lab checkpoint: Run the supplied BSTMapTester that you downloaded at the start of the project and show us it passes the first test!
    • 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 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.