Splay Trees

Sample Implementation

A polymorphic C implementation of Splay trees is available here: https://github.com/Tyresius92/splay-tree

Splay Tree Basics

Splay trees are a form of dynamic binary search tree that uses a series of rotations to move an item to the root when it is accessed.

The basic idea with splay trees is that the most recently accessed items are more likely to be accessed again. Therefore, it would be wise to move those items closer to the root.

In order to do this, we define an operation Splay(T, n), where T is the tree in which we are accessing an item, and n is the item which we are accessing. Following the splay operation, n is the root of T.

What is an "access"?

Any operation on a particular value counts as an access. For instance, if I:

Search for 5 in a Splay Tree, I have accessed 5, so I bring it to the root.
- In an unsuccessful search, we would splay the leaf node where we fell off the tree.
Insert a value, I insert it as normal, and then splay it to the root.
Delete a value, I actually have two options, which result in the same tree.
- I could find the value to delete, splay it to the root, and then perform a normal BST deletion (where the value at the root would then be replaced with its successor).
- Alternatively, I could delete the value in its original position, replace it with its successor in the original location, and then splay the successor. This option is slightly more efficient, since if I were deleting a leaf node, I could just delete it, but in the first option, I would be unnecessarily splaying the node.

Splay(T, n)

There are 6 possible cases with splay trees, but they are symmetric, so we will discuss only 3. In the following discussions, let P be the parent of n, and G be the parent of P.

Splay Algorithm

While n is not the root
- Case 1: if n is the left child of the root
  - Perform a zig operation.
- Case 2: if n is the left child of P and P is the left child of G
  - Perform a zig-zig operation
- Case 3: if n is the left child of P, and P is the right child of G
  - Perform a zig-zag operation

Zig Operation

If we are performing a zig operation, then n is the child of the root. Therefore, we just perform a single rotation to make n the root. (You can read more about rotations on this page.) Following a zig operation, the Splay algorithm terminates.

Zig-Zig Operation

In a zig-zig operation, n is the left child of P, and P is the left child of G. (The symmetric case can be derived trivially.)

We will perform right rotation on G, followed by a right rotation on P. This results in a subtree where x is at the root of the subtree, P is n's right child, and G is P's right child.

The Splay algorithm may terminate after a zig-zig operation, but only if G was the root.

Zig-Zag Operation

In a zig-zag operation, n is the right child of P, and P is the left child of G. (Again, the symmetric case can be derived trivially.)

We will perform a left rotation on P, followed by a right rotation on G. This results in a subtree where x is at the root of the subtree, P is n's left child, and G is n's right child.

The Splay algorithm may terminate after a zig-zag operation, but only if G was the root.

Runtime of Splay Trees

It can be shown that the amortized runtime of a single search/splay operation in a splay tree is O(lg n).

For a more concrete discussion of the topic, and to see the proof, please click here.

Google Sites

Report abuse