The TAO of Java

Laboratory: Implementing Dictionaries with Binary Search Trees

Summary: In this laboratory, you will have an opportunity to enhance your understanding of the dictionary ADT and of binary search trees by exploring a binary search tree implementation of dictionaries.


Code Files from Previous Lab:

New Code Files:


Exercise 0: Preparation

In this laboratory, you will use a package entitled username.bst.

a. In a terminal window, type

/home/rebelsky/bin/tao bst

You should see messages about files being copied to a temporary directory.

b. Start Eclipse.

c. In Eclipse, build a project named Temp from /home/username/CSC152/Temp.

d. In the Temp project, you should see a package named username.bst. Drag that package to your Code project.

e. Delete the Temp project.

You can now work with the new package.

Exercise 1: 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 (or both).

Exercise 2: Nodes for Binary Search Trees


Clearly, these nodes are insufficient, by themselves, to implement binary search trees. What we need to do is to wrap them in a class that builds the trees and uses them to support the get and put operations.

a. What fields would you expect that class to have?

b. Binary search trees assume that keys are ordered. How do you plan to compare values to determine what is smaller or larger?

c. How would you expect to implement the get method? (You need not write code, just sketch a strategy.)

d. How would you expect to implement the put method? (You need not write code, just sketch a strategy.) Note that, unlike get, put modifies the tree.

e. Examine to compare that implementation to your suggestions.

f. Explain the strategy used for put.

Exercise 3: Testing, Revisited

As you may recall,, provides a a generic tester for NewDict., uses that generic tester to provide a tester customized for binary search trees.

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

Exercise 4: Testing, Re-revisited

a. Write a new tester for binary search trees that prompts the user for a sequence of key,value pairs, inserts each pair into the tree, and then print out the tree.

For example, we might use this tester as follows.

ji NewTestBST d a b c e
Please enter the key,value pairs, one per line.
Enter a blank line when you are done.
> d,Dog
> a,Apple
> b,Binary
> c,Cute
> e,Echo
d => Dog
 L a => Apple
 L  R b => Binary
 L  R  R c => Cute
 R e => Echo

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

Exercise 5: Removing Values

As you may recall, the general strategy for removing a key/value pair from a binary search tree is somewhat complex.

a. Write a method, BSTNode find(BSTNode top, K key), that finds the node with the designated key. (Hint: You may want to factor out the code from get.)

b. Write a method, BSTNode leftmost(BSTNode top), that finds the leftmost node in a subtree. (Hint: You find the leftmost node by repeatedly following the left branch until there is no left branch.)

c. Write a method, void slideRightUp(BSTNode top), that slides up the values from the right subtree.

d. There are a few special cases for removal. One is that there is no right subtree. Another is that there are no subtrees at all. Determine what you should do for those special cases.

e. Put it all together into a remove(K key) method.

f. Suppose we start with a full binary tree. What do you expect to happen if we repeatedly remove the value at the root? Confirm your answer experimentally.

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.


Monday, 11 April 2005 [Samuel A. Rebelsky]

Tuesday, 12 April 2005 [Samuel A. Rebelsky]

Wednesday, 13 April 2005 [Samuel A. Rebelsky]

Tuesday, 11 April 2006 [Samuel A. Rebelsky]

Wednesday, 12 April 2006 [Samuel A. Rebelsky]

This page was generated by Siteweaver on Wed Apr 12 09:00:40 2006.
The source to the page was last modified on Wed Apr 12 09:00:39 2006.
This page may be found at

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

Samuel A. Rebelsky