©2005 Felleisen, Proulx, et. al.

5  Abstract Data Types

Etudes: Bags and Sets

Compare the two classes in figure 1. A Set is a collection of integers that contains each element at most once. A Bag is also a collecion of integers, but an integer may show up many times in a bag. Your tasks are:

  1. The two class definitions use lists of integers to keep track of elements. Design a representation of lists of integers with this interface:
    // a list of integers
    interface ILin {
     int howMany(int i);
    The constructors are MTin for the empty list and Cin for constructing a list from an integer and an existing list.
  2. Develop examples of Sets and Bags.

  3. Develop functional examples for all methods in Set and Bag. Turn them into tests.

  4. The two classes clearly share a number of similarities. Create a union and lift the commonalities into an abstract superclass. Name the union interface ICollection. Don't forget to re-run your test suite at each step.

  5. Develop the method size, which determines how many elements a Bag or a Set contain. If a Bag contains an integer n times, it contributes n to size.

  6. Develop the method rem, which removes a given integer. If a Bag contains an integer more than once, only one of them is removed.

    Most object-oriented languages provide libraries like Set, and Bag. Find the documentation for your local Java implementation and read up on Sets.

// Figure 1:
// a set of integers:
// contains an integer at most once>
class Set {
 ILin elements;

 Set(ILin elements) {
   this.elements = elements;

 // add i to this set unless it is already in there
 Set add(int i) {
  if (this.in(i))
   return this;
    new Set(new Cin(i,this.elements));

 // is i a member of this set?
 boolean in(int i) {
   this.elements.howMany(i) > 0;

// a bag of integers
class Bag {
 ILin elements;

 Bag(ILin elements) {
  this.elements = elements;

 // add i to this bag
 Bag add(int i) {
   new Bag(new Cin(i,this.elements));

 // is i a member of this bag?
 boolean in(int i) {
   this.elements.howMany(i) > 0;

 // how often is i a member of this bag?
 int howMany(int i) {

5  Binary Search Trees; Graphics and Interactions

Binary Search Trees

We have the following data definition:

A Binary Search Tree is one of

A Node consists of

Additionally, every Node has the property that all data in the left subtree contains strings that appear in the dictionary before the data in the Node, and all data in the right subtree are strings that appear in the dictionary after the data in this node. The string that is identical to the field data can be in either the left or in the right subtree -- it is not important.

The following are examples of such trees:

             ppp                          mmm  
           ------                      --------
          /      \                    /        \
       ggg        ttt                ddd          rrr 
      -----      -----              -----        -----
     /     \    /     \            /     \      /     \
   bbb      *  sss     *        aaa       kkk  *       xxx
  -----       -----            -----     -----        -----
 /     \     /     \          /     \   /     \      /     \
*       *   *       *        *       * *       *    *       *
      Tree-1                            Tree-2

Your task is to design classes that represent this data as Java classes, and to design several methods to manipulate this data. You will also need an auxilliary classes that represent a list of Strings. You may read more about binary search tree in HtDP.

5.1  Problem

Design the classes that represent binary search trees of Strings. Make examples of data.

5.2  Problem

Design the method same that determines whether two binary search trees are the same, i.e. they have the same structure and contain the same Strings.

5.3  Problem

Design the method insert that insert a String into a binary search tree, preserving the tree property stated earlier.

Java provides the following method for String comparison:

// compare this String with that String lexicographically
// return <0  --- if 'this' is before 'that'
// return 0   --- if 'this' is the same String as 'that'
// return >0  --- if 'this' is after 'that'
int compareTo(String that) ...

If you do not understand how to do it, try some examples by hand, or read about the problem in HtDP.

5.4  Problem

Design the classes that represent a list of Strings. Add the method sort that sorts the list in lexicographical order. Add the method same that determines whether two lists contain the same Strings in the same order. You should just modify your solutions to the previous homework.

5.5  Problem

Design the method inorder that produces a list of Strings that appear in the nodes of this tree, ordered so that all strings in the left subtree appear in the list before the data in the root node, and all strings in the right subtree appear in the list after the data in the root node.

For example, our two examples would produce the lists in the following order:

Tree-1:  bbb ggg ppp sss ttt
Tree-2:  aaa ddd kkk mmm rrr xxx

The method consumes a list of Strings, initially empty, that represents the list of strings that come after all the nodes in this subtree have been entered into the list. So, for our Tree-2, in the Node ddd, the given list of strings will contain (mmm rrr xxx). The nodes in this subtree, ddd, aaa, and kkk, still have to be added to the list. It is clear, that when we start at the node mmm, there is nothing in the list.

Again, make examples until you understand the problem. Follow the design recipe!

5.6  Problem

Design the method contains for both, the classes that represent the binary search trees, and the classes that represent lists of Strings. The method determines whether the given String appears in the tree or list repsectively.

5.7  Problem

Explore the power of the methods you designed through the following examples:

  1. insert the same items into a binary search tree several times in different order, then produce the result from the inorder method and check that they are the same.

  2. insert the same items into a list of Strings, again several times in a different order, and sort these lists.

  3. design a comparison between a binary search tree and a list of Strings to determine whether they contain the same Strings.

  4. design the method sameData for the classes that represent binary
    search trees, that determines whether two trees contain the same
    Strings, not necessarily organized the same way. For example, any pair of the following three trees would pass this test:

          bb                  cc              aa
        /    \              /    \          /    \
      aa      cc          aa      *        *      bb
     /  \    /  \        /  \                    /  \
    *    *  *    *      *   bb                  *   cc
                           /  \                    /  \
                          *    *                  *    *

  5. design the method buildTree for the classes that represent
    binary search trees that consumes a list of Strings and produces a binary search tree, with all Strings in the list inserted in the tree. Verify that you produced the correct list by comparing the result of invoking the inorder method with the given list in sorted order.

5.8  Problem: Challenge - will not be graded

Design the method delete that deletes the given String from the binary search tree, while preserving the binary search tree property. If the tree does not contain the String, the method just returns the original tree.

5.9  Analytical Problem

The height of the binary tree is the longest path from the root Node to an Empty Tree. So for example, Tree-1 and Tree-2 in the first set of examples both have height 3, while the first tree in the Problem 5.7 has height 2.

  1. What is the smallest and what is the greatest height of a binary serch tree with 63 nodes?, with 31 nodes?

  2. Make examples of the binary search tree of minimum and maximum height with 15 nodes.

  3. Show all possible binary search trees that contain the following
    Strings and no others: aa bb cc dd

Last modified: Friday, February 4th, 2005
HTML conversion by TeX2page 2004-09-11