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.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Some Sample Binary Search Trees
  • Exercise 2: Nodes for Binary Search Trees
  • Exercise 3: Testing, Revisited
  • Exercise 4: Testing, Re-revisited
  • Exercise 5: Removing Values
• For Those With Extra Time
  • Extra 1: Balancing Trees

Code Files from Previous Lab:

• Dict.java (the interface)
• DictTester.java (a generic tester for Dict)

New Code Files:

• BST.java (binary search trees)
• BSTNode.java (the nodes for BST)
• TestBST.java (a tester for BST)

Exercises

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).

• Chinchilla, Aardvark, Baboon, Frog, Dingo, Elephant, Ant
• Aardvark, Ant, Baboon, Chinchilla, Dingo, Elephant, Frog
• Frog, Elephant, Dingo, Chinchilla, Baboon, Ant, Aardvark
• Chinchilla, Frog, Dingo, Elephant, Aardvark, Baboon, Ant

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

Consider BSTNode.java.

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 BST.java to compare that implementation to your suggestions.

f. Explain the strategy used for put.

Exercise 3: Testing, Revisited

As you may recall, DictTester.java, provides a a generic tester for NewDict.

TestBST.java, 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.

• You find the node with the correct key.
• You determine the leftmost node in the right subtree. (Alternately, you find the rightmost node in the left subtree.)
• You move the key/value pair from the leftmost node of the right subtree to the node to be deleted.
• You slide up the right subtree of that leftmost node.

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.

History

Monday, 11 April 2005 [Samuel A. Rebelsky]

• Wrote code.

Tuesday, 12 April 2005 [Samuel A. Rebelsky]

• Wrote lab.

Wednesday, 13 April 2005 [Samuel A. Rebelsky]

• Added the two extra time questions.

Tuesday, 11 April 2006 [Samuel A. Rebelsky]

• Significant rewrite.
• Dropped questions about vector-based dictionaries (now covered in a separate lab).
• Reorganized questions about BSTs.
• Added the remove question.
• Removed a much less detailed remove question.

Wednesday, 12 April 2006 [Samuel A. Rebelsky]

• Added special cases to the remove question.