Espresso: A Concentrated Introduction to Java

Laboratory: Binary Search Trees and Other Implementations of the Dictionary ADT

Summary: In this laboratory, you will have an opportunity to enhance your understanding of the dictionary by exploring two implementations of dictionaries: a simple, array-based implementation and, more importantly, a form of binary search tree.

Contents:

Required Code Files:

Exercises

Exercise 0: Preparation

a. Create a package named username.dict.

b. Put all of the files linked above in that package.

c. Make sure to change the package name in each file.

Exercise 1: The Dictionary Interface

Read through NewDict.java.

a. What purpose does I serve in this interface?

b. What purpose does V serve in this interface?

c. What other methods would you suggest adding to the interface?

Exercise 2: Array-Based Dictionary Implementation

Look at ArrayBasedNewDict.java, an array-based implementation of NewDict.

a. Describe, in your own words, how this implementation works.

b. What is the purpose of find in this code?

Exercise 3: Testing

Look at NewDictTester.java, a generic tester for NewDict, and TestABND.java, a tester customized for ArrayBasedNewDict.

a. Explain what the tests do.

b. Compile and run TestABND and confirm that it produces the results you expect.

Exercise 4: Running Times

Give an approximate but close upper bound on the running time of put and get.

Exercise 5: Deletion

Sketch an algorithm that one could use to delete an element from the dictionary. (You can assume that we provide only the index as a parameter to this method.)

Exercise 6: Binary Search Trees

Look at BST.java and BSTNode.java.

a. Explain the differences between the two classes.

b. Explain, in your own words, how binary search trees are structured.

Exercise 7: Some Sample Binary Search Trees

a. Sketch the binary search trees that would be created by adding the following lists of indices (each list creates a separate tree, assume the elements are added in order).

b. Is there a better or worse order to put values into a binary search tree?

c. Estimate the running time of put and get in terms of the number of elements in the tree or the depth of the tree.

Exercise 8: Testing, Revisited

Look at NewDictTester.java, a generic tester for NewDict, and TestBST.java, a tester customized for binary search trees.

a. Explain what the tests do.

b. Compile and run TestBST and confirm that it produces the results you expect.

Exercise 9: Testing, Re-revisited

a. Write a new tester for binary search trees that lets you specify the index on the command line and then prints out the try. Assume that the value associated with each index is the uppercase version of that index. For example, we might use this tester as follows. 

ji NewTestBST d a b c e
d => D
 L a => A
 L  R b => B
 L  R  R c => C
 R e => E

b. Use the tester to check your answers from exercise 7.

For Those With Extra Time

Extra 1: Balancing Trees

As you may have noted, binary search trees only work well when elements are split nearly evenly between subtrees. (Similarly, each subtree should have about the same number of elements in each of its sub-subtrees, and so on and so forth.)

Design (but do not implement) a strategy for keeping the number of elements in each subtree approximately equivalent.

Extra 2: Deletion

a. Design (but do not implement) a strategy for deleting indices from binary search trees.

b. Starting with a mostly balanced tree of size 9, see what happens if you repeatedly delete the index at the root using your strategy.

History

Monday, 11 April 2005 [Samuel A. Rebelsky]

Tuesday, 12 April 2005 [Samuel A. Rebelsky]

Wednesday, 13 April 2005 [Samuel A. Rebelsky]

This page was generated by Siteweaver on Thu Mar 30 15:24:34 2006.
The source to the page was last modified on Wed Apr 13 11:18:12 2005.
This page may be found at http://www.cs.grinnell.edu/~rebelsky/Espresso/Labs/bst.html.

You may wish to validate this page's HTML ; Valid CSS! ; Check with Bobby

Samuel A. Rebelsky
rebelsky@grinnell.edu