CS 231: Lab #6

Title image Spring 2018

Binary Search Trees

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


  1. Make a new folder for this week's project.
  2. 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.
  3. 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. You can use any legal name, including descriptive ones.

    public class KeyValuePair<Key,Value>

    It supports a generic type for the key (Key) and a generic type for the value (Value), and should have fields to contain a key and 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.

  4. 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. 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.

    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.