On this page:
Instructions
Practice Problems
Problem 1: Function objects and binary search trees
7.2

Assignment 6: Generic data, function objects

Goals: Practice working with generic objects and function objects.

Instructions

As always, be careful of your naming of classes, interfaces, methods, and files.

The submissions will be organized as follows:

Due Date: Thursday, February 27th at 9:00pm

Practice Problems

Work out these problems on your own. Save them in an electronic portfolio, so you can show them to your instructor, review them before the exam, use them as a reference when working on the homework assignments.

Problem 1: Function objects and binary search trees

A binary search tree represents an ordered collection of data where each node holds one data item and has links to two subtrees, such that all data items in the left subtree come before the current data item and all data items in the right subtree come after the current data item. The tree with no data is represented as a leaf. The trees below demonstrate some (small!) valid and invalid examples of binary search trees over integers (the leaves of the tree are not shown):

  valid:    valid:    invalid:
    3         2         3
   / \       / \       / \
  2   4     1   4     1   4
 /              /        / \
1              3        2   5

(In the last tree, even though the subtree beginning at 4 is a valid binary search tree on its own, the root node is not a valid binary search tree since 2 < 3 but 2 is in the right-subtree.)

Binary search trees are generic over the type of data they contain. To describe an ordering among the values, we need a comparator. We will use Java’s Comparator interface for this purpose.

Do Now!

Valid binary search trees seem to be organized pretty similarly to how well-formed ancestry trees were organized. Try writing out in English a description of the "well-formed ancestry tree property" and of the "valid binary search tree property". What’s the only difference between them?

You will work with a binary search tree that represents a collection of Book objects. Start a new project and define in it the class that represents a Book as shown in the class diagram below. We want to keep track of the books in several different ordered ways - by title, by author, and by price.

The following class diagram should help you:

      +-------------------------+
      | abstract class ABST<T>  |
      +-------------------------+
      | Comparator<T> order -------------+
      +-------------------------+         |
                 / \                      |
                 ---                      |
                  |                       |
          -----------------               |
          |               |               |
     +---------+    +------------+        |
     | Leaf<T> |    | Node<T>    |        |
     +---------+    +------------+        |
                    | T data     |        |
                    | ABST left  |        |
                    | ABST right |        |
                    +------------+        |
                                          V
+---------------+    +-------------------------+
| Book          |    | Comparator<T>          |
+---------------+    +-------------------------+
| String title  |    | int compare(T t1, T t2) |
| String author |    +-------------------------+
| int price     |
+---------------+

Because every node in a BST must know about how the ordering works, we will use Java’s Comparator<T> interface, and use it as a field of the abstract base class of BST nodes and leaves.