Laboratory: Binary Search Trees

Summary: We explore the design and implementation of binary search trees, focusing on the ways in which we navigate and iterate such trees.

Preliminaries

As you may recall, a binary search tree is a linked data structure designed with the “divide and conquer” strategy. The tree consists of nodes, each of which contains a key, a value, and links to two other trees. (Those links may also lead to null.) We speed up searching by ensuring that all the “smaller” keys fall in the left subtree and that all of the “larger” keys fall in the right subtree.

In such a tree, it should be easy to find a key.

search(key,node)
  If the node is null, the key is not there
    Give up // Return a special value, throw an exception, ...
  Otherwise
    Compare key to the node's key
    If key equals the node's key, we've found it
      Return the value
    Otherwise, if key precedes the node's key,
      Recurse on the left subtree
    Otherwise, key follows the node's key
      Recurse on the right subtree

Preparation

Fork and clone the repository at https://github.com/Grinnell-CSC207/bst.

Sketch the tree that you expect to create by adding the following key/value pairs (in that order).

e: elephant
c: chinchilla
b: baboon
d: dingo
a: aardvark
g: gibbon
f: flying squirrel
h: hippo

Exercises

Exercise 1: Checking Trees

Our BST.java class includes a method, dump, that prints a tree using a simple format. In particular, given a node, we print

the key/value pair for the node,
the left subtree, indented by four spaces, and
the right subtree, indented by four spaces.

Null subtrees are represented as <>.

a. Read through the code of BSTExpt.java. You will note that it uses the same sequence of operations as given above.

b. Run BSTExpt and compare the trees it gives to the trees you predicted.

c. Read the definitions of set and insert to understand how we build binary search trees.

Exercise 2: Exploring Repetition

In some of our previous work, we've seen some errors when we reuse a key or value. So let's consider such situations.

a. Given your reading of set and insert, what do you expect to have happen if we call set with a key that we've used before?

b. What do you expect to have happen if we call set with a value that we've used before?

c. Check your answers experimentally. (You'll see two lines in BSTExpt.java that you can uncomment as a starting point.)

Exercise 3: Printing Trees

a. Suppose you had to implement dump. Sketch the algorithm you would use. Note that each node in the tree contains a key, a value, and links to two subtrees called smaller and larger.

b. Compare your answer to our implementation of dump.

Exercise 4: Similar Trees

Does the order in which we add elements to the tree matter?

a. Suppose we add elements to the tree in alphabetical order. What do you expect the tree to look like?

b. Update BSTExpt so that the elements get added to the tree in alphabetical order and see if the results are similar to what you predicted.

c. As you may have noted, when we add the elements in alphabetical order, we get a fairly unbalanced tree. Spend no more than five minutes considering how you might keep the tree more balanced. Do not attempt to implement your idea, but be prepared to discuss the idea.

d. Rearrange the lines that add elements so that they build some other tree. (It doesn't matter which; we just want something a bit more balanced.)

Exercise 5: Implementing `get`

If you've looked at the BST.java, you'll note that some important methods are left unimplemented. One such method is get. Implement that method and add some experiments that help verify that your implementation is correct.

Note: You may find it easier to implement get with a helper method, similar to the one we used as a helper to insert.

Exercise 6: Iterating Trees

We make it a habit to implement iterators for every collection we create. And so we should implement an iterator for our BST. In fact, we'll implement two, one for the keys and one for the values. Of course, their implementations are likely to be similar.

a. Sketch a strategy for implementing an iterator over binary search trees. Think about what data you will need to store and how you will implement the next and hasNext methods.

b. Compare your answer to the implementation in BST.java.

c. Suppose we create an iterator for the keys in the tree. In what order do you expect to see the values?

d. Check your answer experimentally. Here's some sample code.

for (String key : dict.keys()) 
  {
    pen.print(key + " ");
  } // for each key
pen.println();

For Those with Extra Time

If you find that you have extra time, you may want to attempt one or more of the following. (You can do them in any order.)

Extra 1: Rethinking `get`

Some people find it natural to implement get recursively. Others find it natural to implement get iteratively. (I will admit that I fall in the first category.)

a. If you implemented get recursively, implement it iteratively. If you implemented get iteratively, implement it recursively.

b. Which do you prefer, and why?

Extra 2: Implement `containsKey`

You'll note that we have not implemented containsKey. Implement that method without significantly duplicating code. (In order to avoid significantly duplicating code, you may need to generalize your code that implements get so that both containsKey and get can use the same core code.)

Extra 3: Alternate Iterators

Right now, the iterators for our binary search tree iterate in the same order that we print the tree. But what if we want a different order? Say, suppose we want the root, then all the values that are one away from the root (the children), then all the values that are two away from the root (the grandchildren), then all the values that are three away from the root (the great-grandchildren), and so on and so forth.

Update the iterators to provide the values in that order.