CSC 271
Homework 8 in C++

Assigned Nov 22, due Dec 6

A common abstract data type in computer science is the "dictionary", a collection of key/value pairs. It should be possible to look up a given key in a dictionary, find out whether it's there at all, find what value is associated with it, etc. For example, an ordinary dictionary is a "dictionary" in the computer science sense, with words as the keys and definitions as the values. A telephone book is a "dictionary" with names as the keys and phone numbers as the values. A reverse telephone book is a "dictionary" with phone numbers as the keys and names as the values. And so on. We'll implement one in C++.

  1. Define a BST class that represents a binary search tree with integer keys and string values. That is, the tree is ordered by the integer keys, and each integer key has a string associated with it. It should have the following public methods:

    As usual, there should be a test function that runs a bunch of test cases on the BST class and reports which test cases failed (or at least prints out both the actual answer and the right answer).

    You may do this with a null-terminated data structure, as you saw in CSC 172, or with a polymorphic data structure (an abstract class Tree with two concrete subclasses Leaf and Node). In either case, you may want the BST class to be just a "front end", using one or more other classes internally to actually represent the tree.

    The various methods must take advantage of the binary-search-tree structure: they should each search only either the left subtree or the right subtree, depending on whether the key being searched for is less than or greater than the key in the node at hand.

  2. Generalize your BST class to a template with two parameters KeyType and ValueType. The above version would then be BST<int,string>; one should also be able to build easily a BST<float,string> with float keys and string values, or a BST<string,Employee> with string keys and Employee values, etc.

  3. Once we've implemented a BST that can keep integer, float, or string keys in increasing order, it should be (almost) equally easy to build a BST with integer keys in decreasing order, or integer keys sorted by the number of prime factors, or string keys sorted by length rather than alphabetically, or Employee keys sorted by their id fields, etc. So let's modify the BST class so its constructor takes in a Comparator object, and the tree-traversing methods all use this Comparator to decide whether to go left or right.

    What is a comparator? If you were writing in Scheme, it would be just a function with contract KeyType KeyType -> boolean. In C++, it's difficult (though not impossible) to pass functions as arguments to other functions, so what we do instead is define a class with (usually) no data fields and one method, an overridden () operator that takes in two KeyType parameters. Suppose you had an instance of such a class, and you happened to store it in a variable named less. If obj1 and obj2 were both variables of type KeyType, then you could compare them by writing

    if (less(obj1, obj2)) { ... }
    

    So far that sounds like just a gee-whiz syntax hack. But suppose you had an abstract class Comparator with no data fields and a pure-virtual overridden () operator. You could define several subclasses of it -- class IncreasingIntOrder, class DecreasingIntOrder, class StringsByDecreasingLength, etc. -- each with its own definition of the () operator, and then you could create several differently-ordered BST's as follows:

    BST<int,string> tree1(IncreasingIntOrder());
    BST<int,string> tree2(DecreasingIntOrder());
    BST<string,string> tree3(StringsByDecreasingLength());
    
    The constructor for BST would take in an object of (abstract) type Comparator (presumably parameterized to the correct KeyType), memorize it in an instance variable, and use it subsequently to decide whether to go left or right in a tree.

    It probably makes sense for the constructor argument to default to a < comparison, so BST<int,string>() produces a BST with int keys, string values, with the keys sorted in increasing integer order.

    You can do a Web search for ideas on this; a few relevant hits are here and here.


Last modified: 
Stephen Bloch / bloch@adelphi.edu