## Splay Trees

Here is the SplayTree.java code
for the applet below.

The splay tree moves any given node of a tree to the
root of the tree by repeatedly hitting the node with
the double rotate function of the previous assignment.
A node with is an odd depth from the root will need
a final single rotate to bring it fully to the root.
The Splay Tree is originally described in D.D. Sleator,
R.E. Tarjan, *Self-adjusting binary search trees*,
Journal of the ACM 32 (1985), 652-686. See also the
description in Mark ALlen Weiss's book *Data Structures
and Algorithm Analysis* by Benjamin Cummings Press.

The single and double rotate has the zig and the zag
case. The zig case brings node N two levels closer to
the root when N is the left child of the left child
of its grandparent, or the right child of the right
child of its grandparent. Let P be the parent of N.
A double rotate in the zig case is first rotate at
P then rotate at N.

The zag case brings node N two levels closer to the
root when N is the left child of the right child of
its grandparent, or the right child of the left
child of its grandparent. That is, from the grandparent
of N to N the journey zags, descending first left than right, or
first right than left. A double rotate at N is two
consecutive rotates at N.

The program can work as follows: if string item s is
found in the tree, splay the node containing s to the root.
If string item s is not found in the tree, insert it in
its proper place, according to the search tree property
of the tree, then immediately splay the newly inserted
node to the root.

Regular splaying will maintain a balanced tree.

It sounds weird, but it's true! And it looks weird too. Often
the splay will give the tree a more imbalanced appearance.
However, a careful analysis, using amortized costs, that is,
the cost averaged over the life of the tree, will show that
you remain overall ahead of the game, even if one or two
steps seem to take you backwards, towards a poorly balanced
tree.