copyright 2012 Felleisen, Proulx, et. al.

CS 2510 Spring 2012:Assignment 8 - Binary Trees and Binary Search Trees

Practice Problems

Complete part 3 of Lab 8. You do not need to add this to your assignment submission, though you should keep them in your electronic portfolio in your own svn repository. This problem is good practice for the upcoming exam.

Pair Programming Assignment

These problems should be checked into your pair's SVN repository by the due date, which is WEDNESDAY 3/14/2012 at 11:59pm.

Project naming requirements

The names of the projects and some of the project files must be exactly the same as specified in the assignment. Failure to do so makes it impossible for the graders to run your submission and results in immediate loss of at least 50% of the homework credit. Every file you submit must have a header that identifies you and the problem it solves. So, for the first problem the header should look like this: 
// Assignment 8 Problem 1
// Partner Name1
// partner1username
// Partner Name2
// partner2username
// 14 March 2012

Problem 1: Parameterized Types

Create a project with the name HW08Problem1.

Complete part 1 of Lab 8.

Problem 2: User-Defined Exceptions

Create a project with the name HW08Problem2.

Complete part 2 of Lab 8.

Problem 3: Binary Trees and their Visitors

Create a project with the name HW08Problem3.

Here is the class diagram for binary trees parameterized over the type of their elements: 

          +-------------+
          |  IBT<T>     |<----------+
          +-------------+<--------+ |
            /_\   /_\             | |
             |     |              | |
+--------------+  +-----------+   | |
| Node<T>      |  | Leaf<T>   |   | |
+--------------+  +-----------+   | |
| T val        |                  | |
| IBT<T> left  |------------------+ |
| IBT<T> right |--------------------+
+--------------+

(This may be a slightly different representation of binary trees than you saw in class. The important point is that a Leaf has no data, which let's us represent empty binary trees, as well trees with only two values; neither of which is possible if a Leaf contains a value.)

Give class and interface definitions for the diagram above, then implement the visitor pattern for binary trees. Visitors should be parameteric in both the type of elements in the tree they visit and the type of result they compute.

Design the following two implementations of a binary tree visitor:

It may be useful to design two helper visitors, LeftMostAcc and RightMostAcc, which accumulate the leftmost (or rightmost) element seen so far.

Binary trees are particularly useful when their elements are sorted according to some ordering. For example, you can find out if a given element is contained in a sorted binary tree must faster than you in one which is not. Of course, whether a given binary tree is sorted or not depends on the ordering of elements we have in mind. For example, recalling our discussion of the Boston Marathon, a binary tree of runners that is sorted by runners' finish times is probably not the same as if we sorted by runners' bib number. So the question "is the tree sorted?" depends on the ordering we'd like to impose on the elements.

Since ordering elements is such a fundamental operation, and since orders exist independently of elements (for example runners may be ordered by bib number, finish time, age, etc.), Java has an interface for comparisons defined by the Comparator<T> interface. A Comparator<T> which are represented by a functional object that has a method: 

  // Produces a negative integer if t1 is "less than" t2.
  // Produces a positive integer if t1 is "greater than" t2.
  // Produces zero if t1 is "equal to" t2.
  int compare(T t1, T t2);
Using the following representation of runners: 
// Represents a runner with name, age (in years), bib number, and time
// (in minutes).
class Runner {
    String name;
    Integer age;
    Integer bib;
    Integer time;
    Runner(String name, Integer age, Integer bib, Integer time) {
        this.name = name;
        this.age = age;
        this.bib = bib;
        this.time = time;
    }
}
design a Comparator<Runner> that orders runners by increasing age; design a Comparator<Runner> that orders runners by decreasing bib number.

Design a Comparator<String> that orders strings by reverse alphabetic order.

Now design a binary tree visitor IsSorted<T> that is given a Comparator<T> when constructed, and uses it to determine if the binary tree it visits is sorted or not according to the ordering of the comparator.

This discussion suggests that a binary search tree is just a binary tree that is sorted according to some comparison. Design a representation of binary search trees according to the following class diagram: 

  +-----------+
  | IBST<T>   |
  +-----------+
      /_\
       |
+--------------------+
| BST<T>             |
+--------------------+
| Comparator<T> comp |
| IBT<T> bt          |
+--------------------+
The bt field should contain a binary tree that we assume is sorted acording to the comp ordering.

The IBST<T> interface should include the following methods: 

// Insert given element into this binary search tree.
// (The resulting tree must be sorted.)
IBST<T> insert(T elem);

// Get the smallest element in this binary search tree.
// (Raise a run-time exception if there is no such element.)
T min();

// Get the largest element in this binary search tree.
// (Raise a run-time exception if there is no such element.)
T max();
In addition to the above methods, IBST<T> should also implement the IBT<T> interface, since after all, a binary search tree is just a kind of binary tree, and thus should implement all the behavior of binary trees in addition to that of binary search trees. Finally, the fact that the bt field is assumed to be sorted is not a valid assumption if users of the BST<T> class can construct a BST with an arbitrary IBT<T> and Comparator<T>. Redesign the IBST<T> class to ensure the integrity of the data it contains. That is, have the public constructor for IBST<T> check that the given binary tree is sorted according to comp. If it isn't, you can either raise an exception, or sort the given tree. In either case, it should be impossible to construct a binary search tree that contains a binary tree that is not sorted.

To the extent possible, your code should re-use functionality developed earlier in this problem.

Last modified: Mon Feb 20 10:12:09 EST 2012