CMSC206 Data Structures
Fall 2015

Assignment 6
Due on Tuesday, Dec. 1, 2015

This assignment contains THREE parts. Please read carefully before starting on the assignment.

Part #1: Write a simplified Binary Search Tree class by implementing the TreeInterface interface as follows:

  1. Put the following fields in the Binary Search Tree class:
    1. root (a Node<E> with item, left, and right)
    2. size (the number of items)
    3. height (the deepest an item has been added)
  2. Implement the size(), height(), find(), and add() methods first, and create the other methods unimplemented with empty blocks (or returning null, if necessary).
    1. You can implement add() and find() by using a helper method that is recursive and uses a Node<E> in addition to the item to add.
    2. You'll need to write the Node<E> class.
  3. Test add(), find(), size(), and height() using the list from Part 2, BEFORE implementing your other methods.
  4. Implement the preOrder(), postOrder(), and inOrder() methods next
  5. Implement clear() the simple way, by setting the root to null (letting the garbage collector handle it), then reset size and height
  6. Note: Remember that you can have more methods than just the methods defined by the interface.
  7. You may not change the interface. If you think there is a bug with the interface please let me know.

Part #2 Make a program that uses the BST from part #1 to:

  1. Use the add() method to add the following strings to the BST:

    1. Cambridge
    2. Crapo
    3. Your birth place
    4. Bryn Mawr
    5. Boring
    6. Hell
    7. Walla Walla
    8. Surprise
    9. Joseph
    10. Romance
    11. Mars
    12. Nuttsville
    13. Rough and Ready
    14. Dynamite
    15. Good Grief

    After adding the above, do a preorder, postorder, and inorder traversal (printing out each node as you visit). Also print out the number of entries in the tree, and its height. You will need use the three methods: preOrder(), postOrder(), and inOrder() that you implemented in the binary search tree class from Part #1.

  2. Clear the tree, and print out the number of items and its height. Then add the above towns in ascending order. Print out the resulting tree's size, and height, and also the results of all three tree traversals.

Save your output as Part2.txt.

Part #3: Redo Assignment#4 to use 1 entry per town (with a list of all zip codes) and entries stored in a Binary Search Tree (as implemented in Part #1) using the string TOWN+STATE as the ordering relation.

For demonstrating the correctness of your program, include a printout that shows the output from following queries:

  1. Cambridge, MA
  2. Crapo, MD
  3. Your birth place (if in the US)
  4. Bryn Mawr, PA
  5. Boring, OR
  6. Hell, MI
  7. Walla Walla, WA
  8. Surprise, NY
  9. Joe, Montana
  10. Romance, Arkansas
  11. Mars, PA
  12. Nuttsville, VA
  13. Rough and Ready, CA
  14. Dynamite, WA
  15. Good Grief, Idaho

Additionally, after reading in the input file, your program should print the height of the resulting tree.

The objective here is to compare the performance of your program from Assignment#4. As before, once you have completed the program, extend it to count the number of comparisons needed to answer a query. Then, for the input data above, compute the average number of comparions needed to answer a query, the average number of comparisons needed to answer a successful query, the average number of comparisons needed to answer an unsuccessful query. Next, compare these results to those obtained in Assignment#4.

Save the output of the program as Part3.txt.

What to Hand-in (on Moodle):

A zip file containing:
  1. .java and .class file(s) for your programs and data structures (in the correct directories if they are in packages.)
  2. Part2.txt
  3. Part3.txt
  4. A short narrative based on the results of your comparisons from Part 3 (do this in the context of expected time complexity of the two data structures and the search algorithm(s))

Back to CS206 Course Materials