References:
----------
   Name: splay trees
   Keywords: papers
   Description: Original paper on splay trees, a self-balancing,
       amortized binary tree structure.
   Location:
       \bibitem{splay}
       Sleator, D.D., and R.E.\ Tarjan,
       ``Self-adjusting binary trees,''
       Proc.\ 15th Ann.\ ACM Symp.\ Theory Comput.\ STOC-83, pp.\ 235--245;
       also in final form in
       {\it J.\ ACM\/} {\bf 32} (1985), pp.\ 652--686.
   Record: jimb@totoro.bio.indiana.edu Thur Apr  7 00:00:00 1994
-----------

Jim Blandy sez:
>So what do you think of splay trees for text property representation?
(He's talking about Emacs, folks).

        What is a splay tree?  What is splaying?  Here are some
definitions:

1.  The "rotate" operation:

       A      rotate right   B
      / \       ------>     / \
     B                         A
    / \	        <------       / \
       c      rotate left    c

        Rotations are done to an edge, not a node.  So the right
   rotation above is around edge B<--->A, and ... oh, uh, so is the
   left rotation, but you see what I mean.

        As you can see, it preserves the symmetric ordering of the
   tree: all left descendants of a node X are less than X, all right
   ones are greater, both before and after the rotation.

2. The "Splaying Step" (How to splay at node x):

   - Case 1 (zig): If p(x), the parent of x, is the tree root, rotate
     the edge joining x with p(x).  (This case is terminal).

   - Case 2 (zig-zig): If p(x) is not the root and x and p(x) are both
     left or both right children, rotate the edge joining p(x) with
     its grandparent g(x) and then rotate the edge joining x with
     p(x).

   - Case 3 (zig-zag): If p(x) is not the root and x is a left child
     and p(x) is a right child, or vice-versa, rotate the edge joining
     x with p(x) and then rotate the dege joining x with the new p(x). 

        "Splaying at a node x of depth d takes O(d) time, that is, time
   proportional to the time to access the item in x.  Splaying not
   only moves x to the root, but roughly halves the depth of every
   node along the access path.  This halving effect makes splaying
   efficient and is a property not shared by other, simpler
   heuristics, such as move-to-root.  Producing this effect seems to
   require dealing with the zig-zig and zig-zag cases differently."


        In a splay tree, every time you access a node X, you perform
the splay step at node X (following it in its travels), until X
becomes the root node of the tree.  Thus, you really don't want to use
splay trees unless you have very heavy locality of access, because of
this constant hit on every access.  If you know that you're likely to
access X, or something near it, repeatedly -- before having to access
some unrelated node -- then you can win big, because those nodes will
all be right up around the root of the tree.

        Some definitions of update operations on splay trees (remember
that for a splay tree, even access is in a sense an "update"
operation):

 - access(i,t): If item i is in tree t, return a pointer to its
   location; otherwise, return a pointer to the null node.

 - insert(i,t): Insert item i in tree t, assuming that it is not there
   already. 

 - delete(i,t): Delete item i from tree t, assuming that it is
   present.

 - join(t1,t2): Combine trees t1 and t2 into a single tree containing
   all items from bothe trees and return the resulting tree.  This
   operation assumes that all items in t1 are less than all those in
   t2 and destroys both t1 and t2.

 - split(i,t): Construct and return two trees t1 and t2, where t1
   contains all items in t less than or equal to i, and t2 contains
   all items in t greater than i.  This operation destroys t.

        For true brevity, we'll implement insert() and delete() in
terms of join() and split(), no reason it can't be done that way.