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: Testing
  • Exercise 3: Testing, Revisited
  • Exercise 4: A Few Additional Methods
  • Exercise 5: Removing Values
• For Those With Extra Time
  • Extra 1: Balancing Trees

Exercises

Exercise 0: Preparation

In this laboratory, you will use two new packages, entitled username.dict and username.bst.

a. In a terminal window, type

/home/rebelsky/bin/tao dict

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

b. In a terminal window, type

/home/rebelsky/bin/tao bst

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

c. Start Eclipse.

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

e. In the Temp project, you should see two packages, username.dict and username.bst. Drag both packages to your Code project.

e. Delete the Temp project.

You can now work with the new packages.

Exercise 1: Some Sample Binary Search Trees

a. Consider the following four lists separately. The animal names will be used as indices in binary search trees. For each list, sketch the binary search tree that would be created by adding each index to the tree in the order given.

• 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 1.5: The Dictionary Interface

Familiarize yourself with the dictionary interface given in Dict.java in the username.dict package. (We will not use all of the files in that package this term.)

Exercise 2: Testing

Read through DictTest.java in the package username.dict. It provides a generic tester for dictionaries.

TestBST.java in the package username.bst 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 3: Testing, 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 4: A Few Additional Methods

a. If we are going to throw an exception when a client tries to get a key that is not in the tree, then we should also provide a way for a client to determine whether a given key is in the tree.

b. Write a method public K findMin() that returns the minimum key currently stored in the tree.

c. Write a method public void printInOrder(pen) that prints each (key,value) pair stored in the tree, in ascending order of the keys. (Hint: This method is much easier to write using recursion than iteration.)

Exercise 5: Removing Values

• You find the node with the correct key.
• If it is a leaf, you delete it.
• If it has one child, you replace it with that child.
• If it has two children:
• You determine the leftmost node in its right subtree. (Alternately, you find the rightmost node in its left subtree.)
• You move the key/value pair from the leftmost node of the right subtree to the node to be deleted.
• You delete the leftmost node of the right subtree, using the same strategy. (It is guaranteed to have at most one child.)

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

b. Write a method, BSTNode removeFromSubtree(BSTNode top, K key), that removes key from the subtree rooted at top. (Hints: Use recursion. Begin by searching for the node to remove. See putInSubtree for a similar example. Return the top of the modified tree.)

c. Write a method, BSTNode remove(K key), that initializes the remove process by calling the method you wrote in part b, and then replaces root with the modified tree. You may want to consult the method put for a similar example. (Note that there is already a stub for this method in BST.java.)

d. Test your method by removing one or more nodes from each of the cases listed above.

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.