Tags:

• Computer science
• Data structure
• Java
• JavaScript
• Open source
• Tree

The splay tree is a type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.

The worst case height of a splay tree is nnn, this could be the case if all nodes were accessed in ascending order for example.

This makes the worst case complexity of the splay tree’s operations O(n). Since all operations also splay the tree on the node, the tree ends up roughly balancing itself, this results in a O(logn) amortised worst case time complexity for all operations.

The splay tree is a particularly good choice as a data structure when it’s likely that the same nodes will be accessed multiple times in a short period. This is where the real power in the splay tree lies, in its ability to hoist nodes up to the root when they are accessed, giving speedy access for nearby successive accesses.

This article assumes knowledge of the binary search tree (BST) data structure.

Complexity

* Amortised

Representation

There are two main ways of representing a binary tree. The first is using node objects that have references to their children.

Tree representation

The second is using a regular array and manipulating the index of the node to find its children. The index of the left child of a node is 2i+1 and the index of the right is 2i+2 where i is the index of the parent.

Array representation

The index of node's parent can also be retrieved with ⌊(i−1)/2⌋.

Parallelism

Due to the splay tree adjusting itself even after a “read-only” operation, the splay tree is probably not ideal in a multi-threaded application. If parallelism is desired, additional guards need to be put in place to protect against race conditions.

Operations

Rotation

The generic tree rotation operation is used to perform the below splaying operations. Here is an illustration of the process.

Splay(a)

The splay operation is performed to bring the node a that is being worked on to the root of the tree. It performs a series of operations called zig, zig-zig and zig-zag depending on the characteristics of a. Each operation has two variants depending on whether a or its parent are left or right children.

Zig(a)

This operation is performed when the parent of a is the root of the tree. A left or right rotate is performed to bring a to the root of the tree.

Zig-zig(a)

This operation is performed when a and its parent are the same child type as each other (both left children or both right children). It performs either two right rotations or two left rotations depending on the side. Its name is derived from the fact that the rotations performed are of the same type.

Zig-zag(a)

This operation is performed when a is a different child type to its parent. It performs a rotation of both types (left then right, or right then left) depending on the child type of a.

Delete(a)

Delete can be implemented two different ways:

• by performing a regular BST delete on the node a and then splaying the tree on what was a’s parent, or
• by splaying the node a and then performing a regular BST delete on the a.

Insert(a)

Insert performs a regular BST insert and then splays the tree on the node a, adjusting the tree so that the inserted node is at the root of the tree.

Search(a)

Search performs a regular BST search and then splays the tree on the node a, adjusting the tree so that the searched node is at the root of the tree.

Which binary search tree is best?

The AVL tree, red-black tree and splay tree are all self-adjusting binary search trees, so which one is better in which situation? And when is it better to use a regular BST?

A paper by Ben Pfaff of Stanford University performs an in-depth study of the performance characteristics of each tree under various circumstances. Each data structure excels based on runtime patterns in the input and the calling of operations. It comes to the following conclusions:

• Regular BSTs excel when randomly ordered input can be relied upon.
• Splay trees excel when data is often inserted in a sorted order and later accesses are sequential or clustered.
• AVL trees excel when data is often inserted in a sorted order and later accesses are random.
• Red-black trees excel when data is often inserted in random order but occasional runs of sorted order are expected.

Code

Java

public class SplayTree<T extends Comparable<T>> {
    private SplayTreeNode<T> root;
    public SplayTree() { }
    private void splay(SplayTreeNode<T> node) { ... }
    private void rotateLeft(SplayTreeNode<T> x) { ... }
    private void rotateRight(SplayTreeNode<T> x) { ... }
    public void insert(T key) { ... }
    public void delete(T key) { ... }
    public boolean search(T key) { ... }
}

JavaScript

var SplayTree = function (customCompare) { ... }

TypeScript

export class SplayTree<K, V> implements ISplayTree<K, V> { ... }

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms.