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.