CSE373 Data Structures Wi07, Homework 5

Programming part due online Thursday, 2/8/07, at 11pm.
Written problems and code printout due at the beginning of class, Friday, 2/9/07
No late assignments will be accepted.

Here are some questions involving search trees. One question involves coding, the rest are fairly short written questions.

Written Problems

  1. Weiss, question 4.19
  2. Weiss, question 4.27
  3. Weiss, question 4.28

A 2-4 tree is a multiway search tree (like a B-tree) where each interior node has 2, 3, or 4 children. If an addition to the tree would result in a node with 5 children, then it is split into two nodes with 2 and 3 children; if a deletion would result in a node with only 1 child, it is combined with adjacent nodes to restore the property that all nodes have 2-4 children.

  1. Suppose we have a set of keys {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}.
    1. Draw a (2,4) tree storing this set of keys using the fewest number of nodes.
    2. Draw a (2,4) tree storing this set of keys using the maximum number of nodes.
  2. Consider the sequence of keys {5,16,22,45,2,10,18,30,50,12,1}. Draw the result of inserting entries with these keys in this order into an initially empty (2,4) tree.

Programming Problem

Create a Java class BasicOrderedSplayTreeSet that implements the BasicSet interface from homework 4 using a splay tree. You only need to provide implementations for the add(item) and contains(item) operations of BasicSet. The other operations, particularly remove(item) and iterator() may be "implemented" by throwing an OperationNotSupportedException UnsupportedOperationException if they are called.

(In other words, the point of this problem is just to implement the splay operations and not spend the time re-implementing things like tree iterators which we have already done in previous assignments. However, feel free to implement these additional operations if you'd like. You probably can adapt your code from homework 4 to handle most of the work if you do this.)

The splay tree representation is quite similar to that needed for the AVL tree, with two changes. First, there is no need to store an AVL balance factor or tree height in each node. Second you should add a "parent" pointer to each node that refers to that node's parent. To be efficient, splay operations require fast access to parent nodes.

As before, you are not required to provide a comprehensive test suite, but you will want to test your code, of course, to verify that it works as you expect. You also are not required to use generics, but you can add this as an extra feature if you'd like.