CSE373—Data Structures and Algorithms for Nonmajors

Programming Assignment #3

due: Monday, 11/21/05, 10:00 PM

Overview:

In this assignment, you will be playing with different types of binary search trees.

Experiment (60%):

Included are a bunch of obfuscated class files, a.class through w.class. A class called MysteryTree gives you access to three trees (by methods tree1(), tree2(), tree3()). You need to construct a MysteryTree by passing it an integer, namely your student number with no leading zeros. One of the trees is a basic BST, one an AVL tree, and one a red-black tree (what Java uses in its TreeMap implementation). Your student number determines the mapping of the trees to the methods.

We haven’t talked much about red-black trees, so I’ll say a few words about them now. They do not necessarily meet the strict AVL balance-factor rule, but they still have O(log n) height. The case-by-case analysis of red-black trees is much more complicated than AVL trees, especially deletion, but one advantage of red-black trees is that only O(1) rotations are necessary to restore the red-black invariants following a delete, whereas O(log n) rotations may be necessary for an AVL tree following a delete.

In class, we were drawing pictures of trees with just the keys, and the keys were numbers. The trees in this assignment take keys and values that are both Object. The trees implement the Dictionary interface, where you will be focusing on the following three methods:

public Entry find(Object key)

public Entry insert(Object key, Object value)

public Entry remove(Entry e)

An Entry encapsulates two Objects, accessible by key() and value().

The trees figure out the ordering of the keys by calling the compareTo methods for the keys. The keys must therefore implement the interface Comparable. See the link in the short answer for more information the interface. Because everything so far is a black box, our only chance to understand what is going on inside is to have compareTo produce side effects, such as printing or saving state. We provide a sample class StringWrap that you can use as-is or modify. We also provide a TreeTest program with a skeleton of main to get you started.

You will not need to turn in any of your code.

Put your answers to the following in a file called questions.txt (you can use Notepad for editing). You will be graded on content, not on spelling or grammar.

1. Write your student number. (5 points)

2. What are tree1(), tree2(), and tree3()? (15 points)

3. Describe in detail how you decided which was the BST tree. (20 points)

4. Describe in detail how you decided which was the AVL tree. (20 points)

Short Answer Questions (40%):

Answers also go in questions.txt (10 pts each)

1) Suppose a splay tree were also among the mystery trees. Describe a simple test to identify quickly which tree is the splay tree.

2) You have a splay tree with a root of 1 and right children 2-15 (completely imbalanced). List a series of finds to put the tree into a completely balanced state (every leaf is height 3). The shorter the list the better.

3) You have a splay tree containing values 1 to 15 and it is completely balanced. List a series of finds to put the tree such that the root is 15 and every child is a left child (completely imbalanced). The shorter the list the better.

4) Skim the Java pages on Comparable and Comparator (don’t worry about the details with .equals). Write a few sentences on how a Comparator is more generic than having a class implement Comparable, and give an example of a classic Comparator.

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Comparable.html

http://java.sun.com/j2se/1.4.2/docs/api/java/util/Comparator.html

Bonus (5%):

Can include as an optional file “bonus.jpg” or can turn in on paper during class or office hours.

Draw an AVL tree such that three rounds of restructuring are needed to restore balance after deleting a node. Circle the node that is to be deleted. Don’t make the tree larger than necessary.

Turn in your work electronically from the “assignments” link on the class webpage.