Skip to content

TB Schardl: Splay Trees

by on February 19, 2012

I think one of the more surprising results I’ve seen in algorithms is splay trees.Splay trees are self-adjusting binary search trees that achieve optimal performance bounds for many problems on BST’s simultaneously. Splay trees thus address the problem of storing an ordered set of elements and allowing those elements to be accessed efficiently.

The idea behind splay trees is to always move an element to the root of the tree immediately after it is accessed. The element is moved up the tree using BST tree rotation operations. In particular, this movement operation is performed using a sequence of double tree rotations (so called “zig-zig” or “zig-zag” rotations), possibly followed by one single rotation. Hence, after accessing an element x in the tree, the tree is modified to place x at the root of the tree, regardless of the balance of the resulting tree.

What I find remarkable about splay trees is that this simple strategy of invariably placing the most recently accessed element at the root of the tree allows splay trees to achieve optimal performance (amortized) for a variety of problems. For example, splay trees achieve good balance, meaning that for a sequence S of m accesses on n<m elements, the cost of performing S in a splay tree is O((m+n)log n), which is as good as any balanced tree. Furthermore, splay trees achieve “static optimality,” meaning that they are as good as any fixed tree for performing the sequence S of accesses. Formally, if an item i is accessed p_i*m times in S, then the cost of performing S is O(m + m \sum_{i=1}^n p_i log 1/p_i) in a splay tree, which matches the entropic lower bound for performing S on any static tree. Other performance properties on splay trees can be shown, such as the “working set theorem” and the “static finger theorem,” and all of these results follow from the same amortized analysis of splay trees, using different weight functions on the nodes of the tree.

If you would like more of an explanation as to how splay trees or their analysis works, feel free to ask me.

Advertisements
Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: