Splaying a binary search tree

Below I've provided a brief introduction to the splay, in a bottom-up manner, following Tarjan's treatment in the monograph Data Structures and Network Algorithms. I've also appended a paper by Sleator here, that provides a few more implementation details (for a top-down splay) and explains a bit of the intuition for the complexity analysis. Code and related documents can be through his home page. The code and its analysis will be more fully incorporated into this set of notes and applets as time permits.

To splay a binary search tree at a node n ():

while n is not the root do

Case 1. If the parent of n () is the root, rotate at n - i.e. apply the rotation that makes n the tree's root, and makes its former parent into its child.

The next two cases affect both n and its two immediate ancestors (also ).

Case 2. If n and its parent p have the same orientation - i.e. they are both left or both right childrent - first rotate at p and then at n.

Case 3. On the other hand, if n and its parent p have different orientations - then rotate twice at n.