CS 231: Lab #7

Title image Spring 2020

Binary Search Trees and Sets

The goal of this lab period is to give you an opportunity to implement a map with a binary search tree.

Video: Word Frequency and Binary Search Trees


  1. Setup

    Make a new folder for this week's project.

    Download MapSet.java. Open and read it. Note that it is a generic interface that requires two types - a type for the keys and a type for the values.

  2. Make a Key-Value Pair class

    Create a KeyValuePair class that is to be used by the binary search tree. Previously we have always used a single letter to represent a generic type. This time we need two generic types: one for the key and one for the value. You can use any legal name, including descriptive ones to represent generic types.

    public class KeyValuePair<Key,Value>

    Using two type names supports a generic type for the key (Key) and a generic type for the value (Value). The class should a field of type Key to contain a key and field of type Value to contain a value. It also implements the following methods:

    • public KeyValuePair( Key k, Value v ) the constructor initializing the key and value fields.
    • public Key getKey() returns the key.
    • public Value getValue() returns the value.
    • public void setValue( Value v ) sets the value.
    • public String toString() returns a String containing both the key and value.

    Write a main test function for the class and ensure each of the methods works properly.

  3. Create a Binary Search Tree class

    Create a new file BSTMap.java. In this file, you will need at least 3 classes:

    • BSTMap the main tree class
    • TNode the tree node class, which can go after the BSTMap class or be nested within it (your choice).
    • AscendingString a comparator for keys, which works only for Strings and should not be nested in the BSTMap class. You could also put this and any other comparator classes you create in a separate Java file.

    You can use this template for these three classes.

    Implement the methods required by the MapSet interface. A good strategy to follow is to implement the functions one at a time and test them as you go. You can always write stubs for the remaining functions so that the code will compile. A stub is a temporary version of a function that doesn't do anything but which compiles. For example, the stub may contain a single return statement as in the template.

    The following is a summary of the MapSet functions. In the examples below, K is the key's type variable and V is the value's type variable.

    • public V put( K new_key, V new_value ) - adds or updates a key-value pair. If the key is not already in the map, it should add a new node with the given key-value pair. The the key is already in the map, it should replace the existing value with the given value.
    • public boolean containsKey( K key ) - returns true if the map already contains a node with the specified key.
    • public V get( K key ) - returns the value associated with the given key or null if the key does not exist.
    • public ArrayList<K> keySet() - returns an ArrayList that contains all of the keys in the map. No order is specified for the keys.
    • public ArrayList<V> values() - returns an ArrayList that contains all of the values in the map. Their order should match the order returned by keySet.
    • public ArrayList<KeyValuePair<K,V>> entrySet() - returns an ArrayList of KeyValuePair objects. The pairs should be in a pre-order traversal ordering.
    • public int size - returns the number of elements (keys) in the map.
    • public void clear() - clears the map and sets it to the empty map.

    Use print statements liberally in your code to help you debug your tree. It may also be useful to create a function that prints out the tree level by level or in some other manner that tells you about the structure of the tree.

    A generic binary search tree requires a Comparator in order to judge where to insert a new TNode with its Key-Value pair. A class that implements the Comparator<T> interface must have a method compare that takes in two arguments of type T and returns a negative number, 0, or a positive number, depending on whether the first argument comes before, is equal to, or comes after the second argument. The AscendingString class is an example of a Comparator.

    One of the design goals for the BSTMap is to be able to write out the tree to a file and read it back in later on rather than recreating it from the original data. To make recreating the tree easier, the entrySet method should provide an ArrayList of the KeyValuePairs in the order generated by a pre-order traversal.

    Test your code thoroughly after writing each function. In particular, make sure your entrySet method returns the pairs in pre-order.

When you are done, go ahead and start the project.