Splay Tree

A self-adjusting binary search tree that moves each accessed node to the root, giving strong amortized guarantees.

Self-adjusting by rotation

A splay tree is a binary search tree with no balance information stored. After every access, insert, or delete, it splays the target node to the root through a sequence of rotations. This restructuring keeps recently accessed items near the root, so all operations run in O(log n) amortized time despite the tree having no explicit balance invariant.

The three splay steps

Kronos motion — classical

Zig: the node's parent is the root; a single rotation lifts the node to the root.
Zig-zig: node and parent are both left (or both right) children; rotate the grandparent then the parent.
Zig-zag: node and parent turn opposite ways; rotate the parent then the grandparent.

Amortized bound

Using the potential defined as the sum of the logarithms of subtree sizes, the access lemma shows each splay costs O(log n) amortized. The zig-zig case is what makes the analysis work: it not only moves the node up but also roughly halves the depth of the whole access path, an application of the potential method.

Access pattern strengths

python

# splay(x): while x is not root, apply zig / zig-zig / zig-zag
# properties that follow from the access lemma:
#   working-set: recently used keys are cheap to access
#   static-optimality: within a constant of the best static BST
#   (conjectured) dynamic optimality vs any BST algorithm

Trade-offs

Splay trees adapt to access patterns, making them excellent for skewed workloads and as the basis of link-cut trees for dynamic connectivity. The downsides: they modify the tree even on reads (bad for concurrent readers) and give amortized, not worst-case, guarantees, unlike red-black trees.