The Splay Tree

A splay tree is a binary search tree: every key in a node’s left subtree is smaller, and every key in its right subtree is larger. It stores no height, color, balance factor, or random priority. Search follows the same comparisons as in an ordinary binary search tree.

The difference appears after an access. Rotations move the accessed node to the root in a process called splaying. The tree’s shape therefore records its access history: recently used keys stay near the top, while less active keys may move deeper.

To find key 20, compare it with the root and descend left or right until reaching 20. Then splay that node to the root. The return value is the same as for an ordinary search; the rotations only change the paths used by later operations.

On an unsuccessful search, a common convention is to splay the last node visited. This brings the nearest boundary key to the root and can help a later search in the same region. An implementation should document this miss behavior because it changes the resulting shape.

The zig case applies when the accessed node x is a child of the root. If x is a left child, rotate right at its parent; if it is a right child, rotate left. The rotation makes x the new root.

Only one rotation is needed because no grandparent remains above x. The subtree between x and its former parent changes sides, preserving the binary-search-tree order.

The zig-zig case applies when x and its parent are both left children, or both right children. For a left-left path, first rotate right at the grandparent, then rotate right at the parent. The right-right case is the mirror image.

These two rotations move x upward by two levels and also shorten the path for nodes in the same direction. Splaying repeats the appropriate case until x reaches the root.

The zig-zag case applies when x is a right child of a left child, or a left child of a right child. Rotate once at the parent and once at the grandparent, in opposite directions.

After the two rotations, x replaces its grandparent at the top of the three-node region. Every key remains in the same in-order sequence—left subtree, node, then right subtree—even though all three ancestry relationships change.

Repeatedly rotating x one edge toward the root would also preserve search order, but that is the simpler move-to-root heuristic. Splaying treats the parent and grandparent together. In the zig-zig case, it rotates the parent first instead of rotating x twice.

This distinction spreads the restructuring across the access path. The paired steps are what support the access lemma used in the amortized analysis: expensive paths create enough structural improvement to pay for later operations.

Insert a new key as a leaf using ordinary binary-search-tree comparisons, then splay the new node to the root. The insertion path is immediately reorganized, so a newly inserted key is cheap to access again.

The original definition assumes distinct keys. A map implementation can instead update the value stored at an existing key and splay that existing node. The complete operation takes O(log n) amortized time, although one insertion can still traverse and rotate through a linear-height tree.

First search for the target and splay it to the root. Remove the root, leaving a smaller-key left tree and a larger-key right tree. If the left tree is nonempty, splay its maximum node to the top; that node has no right child, so the entire right tree can be attached there.

This is a join after one splay. Deletion takes O(log n) amortized time and preserves sorted order without storing balance metadata.

Split searches around a boundary key and splays the boundary node to the root. Detaching one root edge then produces two search trees, such as keys at most k and keys greater than k. The exact side used for an equal key is an API choice.

Join requires every key in the left input to be smaller than every key in the right input. Splay the maximum key of the left tree to its root, then attach the right tree as its right child. Both operations take amortized O(log n) time.

A splay tree is not height-balanced. One operation can follow a chain of n nodes and take linear time. The guarantee applies to a sequence: starting with an arbitrary n-node tree, m accesses take O((m + n) log n) total time.

Potential analysis assigns stored credit to the current shape. A long splay can be expensive immediately while reducing enough potential to make the average cost O(log n). This distinction matters when a system requires a strict latency bound for every request. Splay trees are also statically optimal within a constant factor; the stronger dynamic-optimality claim remains a conjecture, not a proven guarantee.

Let t be the number of distinct keys accessed since key x was last accessed. The working-set theorem bounds the amortized cost of returning to x by O(log(t + 1)), apart from the initial-tree term across the sequence.

A key revisited after only a few other distinct keys is therefore cheaper than a key that has been inactive for a long time. No frequency counter or recency list is stored; the rotations encode that locality in the tree itself.

Starting from any shape, accessing every key once in sorted order takes O(n) total time. Individual accesses can still have different costs, but the complete scan is linear.

This scanning theorem shows why the current height alone is an incomplete description of performance. A tree can look unbalanced at one moment and still process a structured sequence efficiently.

Splay trees need only key, value, and child pointers, and they adapt automatically when a small working set receives most accesses. They are useful when total sequence cost and access locality matter more than a fixed shape. For bounded integer keys, a van Emde Boas tree trades this comparison-based, amortized guarantee for O(log log U) worst-case operations and much greater universe-dependent space.

Every splaying lookup mutates the tree. Concurrent readers therefore need synchronization, and read-only snapshots cannot share a stable root without suppressing splaying. Pointer chasing weakens cache locality, and the linear-time worst case for one operation makes the structure unsuitable for hard per-operation latency guarantees.

V8’s profiling tools keep dynamic JIT code, static code, and loaded libraries in separate splay trees keyed by starting machine address. Looking up a sampled address then identifies the code entry that occupied that range. GCC’s C++ front end has also used a splay-tree map while copying default-argument expressions, matching compiler-generated temporary variables with their replacements.

Link-cut trees use splay trees to represent preferred paths in a changing forest. They support linking two trees, cutting an edge, and querying or updating a path; the original work applies these operations to network-flow, constrained spanning-tree, and network-simplex algorithms.

A splay tree is an ordinary binary search tree that rotates the accessed node to the root. Zig handles the final single edge; zig-zig and zig-zag process the remaining path two levels at a time.

The structure uses no explicit balance metadata and gives O(log n) amortized search, insertion, deletion, split, and join. It adapts to recent accesses and scans efficiently, but one operation can take linear time and even a lookup normally changes the tree.