CS 61B Lab 14
                                May 1-2, 2014

Goal:  To give you experience with implementing splay tree operations.

Copy the Lab 14 directory by doing the following, starting from your home
directory.

  cp -r ~cs61b/lab/lab14 .

All the code is in the dict package.  You can compile it from your lab14
directory with "javac -g dict/*.java".  Test code is provided and can be run
with "java dict.SplayTree".

The fields and methods of the SplayTree class are the same as the BinaryTree
class you modified in Lab 11; it even uses the same BinaryTreeNodes and
implements the same Dictionary interface.

We have provided implementations of the find() and insert() methods.  (We have
omitted the remove() method.)  These implementations are similar to those in
an ordinary binary search tree, but they always end by splaying a node to the
root.  However, the splay operation splayNode() does not work correctly,
because it does not use the zig-zig operation.  Instead, it splays a node to
the root by doing a sequence of zig operations.  Unfortunately, this improper
splaying operation does not rebalance an extremely unbalanced splay tree.

Your job is to write a method zigZig() that implements the zig-zig step, then
fix splayNode() so that it uses the zig, zig-zag, and zig-zig steps at the
correct times.  After you finish each part, use the test code to check your
progress.

Part I:  Implement zigZig() (2 points)
--------------------------------------------
We have provided implementations of tree rotations in the methods rotateLeft()
and rotateRight().  We have also provided implementations of the zig and
zig-zag steps in the methods zig() and zigZag(); we suggest you examine those
methods.  Then fill in the body of a method zigZig() that implements the
zig-zig step.  Refer to the Lecture 36 notes if you need help remembering the
difference.  Make sure that the test for Part I runs without printing any error
messages; it should say "Successfully completed Part I".

We suggest that you don't change splayNode() until you have Part I working,
because changes to splayNode() might break our tests that tell you whether you
have implemented Part I successfully.

Part II: Fix splayNode() (2 points)
-------------------------------------------
The method splayNode() currently uses only zig().  Fix the implementation so
that it chooses appropriately between zig(), zigZag(), and zigZig() at each
iteration of the loop that splays the node to the root of the tree.  Again,
refer to the Lecture 36 notes for details.

The tests for Part II include a test that shows how some trees cannot be
balanced without zig-zig steps.

Check-off
---------
Show your TA or Lab Assistant the code you have written, and run the test
program.  You'll receive 2 points for each part that runs without printing any
error messages.