Algorithms and OOD (CSC 207 2014F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [Learning Outcomes] [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Student-Curated Resources] [Java 8 API] [Java 8 Tutorials] [Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2014S (Rebelsky)] [CSC 207 2014F (Walker)] [CSC 207 2011S (Weinman)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Summary: We explore the design and implementation of binary search trees, focusing on the ways in which we navigate and iterate such trees.
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
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).
Our BST.java
class includes a method,
dump
, that prints a tree using a simple format.
In particular, given a node, we print
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.
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.)
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
.
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.)
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
.
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();
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.)
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?
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.)
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.