Here are some questions involving search trees. One question involves coding, the rest are fairly short written questions.
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.
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
(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.