CMSC 341 -- Fall 2004 -- Project 4 Questions

Copy this file into your directory and edit it to add your answers
to the following questions about project 4.

These questions count for 10% of your project grade.

1. (5 points)

   In this project you converted BST code into Splay Tree code.  Describe 
   the changes that would be required to convert your bottom-up Splay Tree 
   code into bottom-up Red-Black Tree code.  What additional data and/or 
   methods would be required?

2. (5 points)

   Suppose you are not allowed to store parent pointers in splay tree 
   nodes and can only store left and right child pointers.  Is it possible
   to implement a bottom-up splay routine recursively?  (Note: You also
   cannot use an auxiliary data structure such as a stack or queue.)
   If so, how?  If not, why not?