CS231

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.

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 the 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

This class will be a Binary Search Tree that implements the MapSet methods. In order to do so, we will need to have that our Keys be comparable so that we can sort them accordingly. However, we still want to use generics in creating our BSTMap; to do this in Java, we can make sure that whatever data type is passed in for the keys extends Comparator via the following:

public class BSTMap<K extends Comparable<K>, V> implements MapSet<K, V>

After declaring the class, we'll want an inner Node class, just as in our previous LinkedLists. However, this time we'll want to keep track of the following fields:

A field for a KeyValuePair: this is the actual 'data' of the Node
A field for a left Node: this is the left child Node
A field for a right Node: this is the right child Node

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

The root Node, from which I can reach every other Node
The int size, or the number of entries in the mapping.

The methods you need to create are simply the methods inherited from the MapSet interface.

public BSTMap(): standard constructor, initializes fields to defaults 0/null
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 (the following pseudocode assumes your Node class has a getKey() method):

private V put(K key, V value, Node cur) {
    if (key.compareTo(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 (key.compareTo(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 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 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:
```
root    <10, ten>
left      <1, one>
right     <20, twenty>
left        <15, fifteen>
```

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