Splaying: Amortized Restructuring Without Stored Balance

Every scheme so far stores something per node to describe its shape: a height, a factor, a colour, a weight, a priority. A splay tree stores nothing. Its only operation is to move an accessed node to the root by a sequence of rotations, and its balance comes entirely from the pattern of accesses rather than from any invariant on the tree. A single access can cost Θ(n), and a sequence of m accesses on a tree of n nodes costs O((m + n) log n) in total, by a potential-function argument over the tree’s shape.

The structure is the cleanest demonstration that amortized bounds are statements about sequences. It is also the one balanced tree whose performance depends on the workload rather than only on the key set, which is why it appears in memory caches and compression contexts and rarely in general-purpose ordered maps.

The splay step and why it is not just rotate-to-root

The naive version of this idea is to rotate an accessed node up one level at a time until it reaches the root. That is called “move-to-root” and it does not have the desired bound: a sequence of accesses to nodes in increasing key order can cost Θ(n) per access in a way that rotating-to-root does not amortize away. The fix is to rotate in pairs, choosing the pair based on the relationship between the node, its parent, and its grandparent.

Three cases exist, and their names are standard.

A zig step applies when the accessed node x has no grandparent. One rotation about the parent suffices, and this is the last step of every splay.

A zig-zig step applies when x and its parent are both left children, or both right children. The parent is rotated above the grandparent, then x is rotated above the parent, so both rotations turn the same way and x rises two levels. The order matters: with x and its parent both left children, rotating x first would instead produce the zig-zag configuration, and the amortized argument depends on the same-direction pairing.

A zig-zag step applies when x is a left child and its parent is a right child, or the reverse. Two rotations in opposite directions are performed, both of them at x: first x rotates above its parent, then above the former grandparent. This is the double rotation already familiar from AVL repair, and it is the one case where the two steps are applied to the same node.

The distinction between zig-zig and zig-zag is the whole content of the algorithm, and it is easy to get wrong: an implementation that rotates about the parent first in both cases is doing move-to-root in pairs and does not achieve the bound.

/* Splay x to the root of the tree whose root is *rootp.
   Requires parent pointers, which splay trees normally maintain. */
void splay(node **rootp, node *x) {
    while (x->parent != NULL) {
        node *p = x->parent, *g = p->parent;
        if (g == NULL) {
            rotate(rootp, x);                 /* zig */
        } else if ((x == p->left) == (p == g->left)) {
            rotate(rootp, p);                 /* zig-zig: grandparent first */
            rotate(rootp, x);
        } else {
            rotate(rootp, x);                 /* zig-zag: parent first */
            rotate(rootp, x);
        }
    }
}

The parent pointers are what make the implementation practical; without them, each step would need to locate the grandparent by searching from the root, which would destroy the bound. The pointers add one word per node, so a splay tree’s metadata is not zero in practice — it is one pointer, which is more than a red-black tree’s one bit. What the structure avoids is any field that must be maintained during rotations; the parent pointer is mechanical bookkeeping, not balance information.

The potential function

The amortized argument uses the potential

$$\Phi(T) = \sum_{x \in T} \log_2 \big(\mathrm{size}(x)\big)$$

where size(x) is the number of nodes in the subtree rooted at x. The potential is largest for bushy trees and smallest for chains, which is the right direction: a chain is the state from which a splay does the most work, and the potential should be low there so that the amortized cost of the expensive operation is charged to the potential increase it produces.

The analysis shows that a splay step at a node of subtree size s has amortized cost at most 3(log₂ s' − log₂ s) + O(1), where s' is the subtree size after the step. Summing over the steps of a single splay telescopes, because each step’s s' is the next step’s s, giving an amortized cost of O(log n) per access. The 3 is the constant that comes from the zig-zig case, where the potential increase is bounded by three times the logarithm ratio; the zig-zag case gives a smaller constant and the zig case gives one.

The telescoping is the reason the bound is per-access rather than per-step. The potential is defined over the whole tree, and the intermediate shapes during a splay are not the shapes the caller observes. Only the beginning and end of the operation matter, and the sum over steps depends only on those endpoints.

Insertion and deletion are expressed as splays. To insert a key, splay the last node visited by the unsuccessful search, then attach the new key as the new root with the old root as one child and the appropriate subtree as the other. To delete, splay the key to the root, then join its two subtrees by splaying the maximum of the left subtree and attaching the right subtree to it. Both operations are O(log n) amortized, and both produce trees whose shape is determined entirely by the access history.

The working-set and dynamic-finger properties

The amortized bound is not the interesting part of the splay tree’s analysis. Two stronger properties follow from the same potential function, and they are what make the structure useful in specific contexts.

The working-set property bounds the cost of a sequence of accesses in terms of how recently each key was accessed. If t distinct keys have been accessed since the last access to key x, the amortized cost of accessing x is O(log t). A workload that repeatedly touches a small set of keys pays logarithmic cost in the size of that set, not in the size of the whole tree. This is the property that makes splay trees competitive with caches in some settings: the structure adapts to the access distribution without being told what it is.

The dynamic-finger property bounds the cost of a sequence of accesses in terms of the distances between consecutive accessed keys in key order. A scan through a contiguous range of keys costs O(log n) for the first access and O(1) amortized for each subsequent key in the range, because each access is close to the previous one and the rotations are correspondingly cheap. A red-black tree costs O(log n) per access for the same scan. This is the property that makes splay trees attractive for sequential workloads, and it is the one that a naive implementation loses if the zig-zig case is coded incorrectly.

Both properties are proved by the same potential function with a different accounting, and both are statements about sequences of accesses rather than about any single access. Neither holds for a single operation, and neither survives an adversary that interleaves accesses to widely separated keys.

What breaks: the read path mutates

A splay tree modifies the tree on every lookup, including lookups that find nothing. A failed search splays the last node visited, which restructures the tree. This is the property that disqualifies the structure from most concurrent settings: a reader cannot be a pure observer, so any protocol that allows concurrent readers must either serialize reads or accept that reads conflict with each other.

The standard mitigations are all expensive relative to a red-black tree’s read path. One is to take an exclusive lock for every access, which serializes the whole structure. Another is to copy the path to the root on each access, which is O(log n) allocation per read and defeats the amortized argument. A third is to batch accesses and splay only periodically, which preserves the shape adaptation approximately but gives up the per-access bound. None of these is attractive, and the practical consequence is that splay trees are used in single-threaded contexts.

The second failure mode is that the amortized bound assumes the potential is never reset. Any operation that discards the tree — clearing it, serializing it, rebuilding it from a sorted array — throws away accumulated potential and the bound restarts. This is not a defect, but it means that a workload which periodically rebuilds the structure gets no benefit from the adaptation, and the rebuild itself costs O(n).

The third is the interaction with node addresses. A splay tree that stores nodes in a contiguous array and splays by index rather than by pointer can avoid the parent pointer entirely, since the index arithmetic gives the parent. That variant is used in some compression and text-index implementations, where the tree is rebuilt frequently and the array layout matters more than the pointer indirection. The trade is that insertion and deletion in the middle of the array cost O(n), so the variant only makes sense for static key sets with dynamic access patterns.

Where it belongs relative to the rest of the family

Splay trees are the limiting case of the trade this cluster describes. They minimize stored metadata and maximize adaptation, at the cost of a worst-case bound that is linear and a read path that mutates. AVL and red-black trees fix the shape deterministically and pay metadata; treaps randomize the shape and pay a priority; weight-balanced trees count and pay an integer. Each choice is a different answer to the question of what the structure should know about itself.

The comparison that matters in practice is with the structures that are cheap to read. For a workload that reads far more than it writes, a red-black tree’s deterministic bound and read-only lookup path dominate, as the height argument in red-black colouring as a height proxy makes precise. For a workload with strong locality — a small hot set, or long sequential scans — the splay tree’s working-set and finger properties can beat a red-black tree by a factor that grows with the locality, and that is the regime where the structure is chosen deliberately rather than by default.