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.