Splay Trees, in depth: zig-zig and zig-zag, top-down splaying, the access lemma, adaptive bounds and when not to use them

The idea: pay for restructuring on access

Balanced trees such as red-black trees guarantee O(log n) depth after every operation by maintaining an invariant. Splay trees make a different bet: do not keep the tree balanced, but make every access pay for restructuring along its own path, so that expensive accesses leave the tree better shaped for the future. Recently used keys end up near the root, which is why splay trees adapt to skewed and local workloads without being told what the workload is.

Every operation is built from one primitive, splay(tree, key), which brings the node with that key, or the last node visited while searching for it, to the root. Search, insert, delete, split and join are a splay plus a constant amount of pointer surgery.

Zig, zig-zig and zig-zag

Bottom-up splaying repeats one of three steps until x is the root. If x's parent p is the root, do a single rotation (zig). If x and p are both left children or both right children, rotate p over its parent g first and then x over p (zig-zig). If one is a left child and the other a right child, rotate x over p and then x over g (zig-zag).

The order inside zig-zig is the whole trick. The naive alternative, rotating x over its parent repeatedly, also moves x to the root, but on a path-shaped tree it leaves the rest of the path just as long as before, and a sequence of accesses can cost Theta(n) each forever. Rotating the grandparent first folds the path roughly in half, so a long path pays for its own shortening.

Top-down splaying in code

The top-down variant from Sleator and Tarjan's original paper does the same restructuring in a single pass from the root, splitting the tree into a left tree of smaller keys and a right tree of larger keys as it descends. It is iterative, so it cannot overflow the stack on a degenerate tree, and it needs no parent pointers.

class Node:
    __slots__ = ("key", "left", "right")
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None

def splay(t, key):
    """Return the new root: the node with key, or the last node on its search path."""
    if t is None:
        return None
    header = Node(None)          # header.right collects the left tree, header.left the right
    l = r = header
    while True:
        if key < t.key:
            if t.left is None:
                break
            if key < t.left.key:             # zig-zig: rotate right first
                y = t.left; t.left = y.right; y.right = t; t = y
                if t.left is None:
                    break
            r.left = t; r = t; t = t.left    # link t into the right tree
        elif key > t.key:
            if t.right is None:
                break
            if key > t.right.key:            # zig-zig: rotate left first
                y = t.right; t.right = y.left; y.left = t; t = y
                if t.right is None:
                    break
            l.right = t; l = t; t = t.right  # link t into the left tree
        else:
            break
    l.right, r.left = t.left, t.right        # reassemble
    t.left, t.right = header.right, header.left
    return t

def insert(t, key):
    if t is None:
        return Node(key)
    t = splay(t, key)
    if key == t.key:
        return t
    n = Node(key)
    if key < t.key:
        n.left, n.right, t.left = t.left, t, None
    else:
        n.right, n.left, t.right = t.right, t, None
    return n

def delete(t, key):
    if t is None:
        return None
    t = splay(t, key)
    if t.key != key:
        return t
    if t.left is None:
        return t.right
    x = splay(t.left, key)       # key exceeds every left key: brings the max to the root
    x.right = t.right
    return x

Notice that delete uses join: splaying the largest key of the left subtree to its root leaves that root with no right child, so the right subtree can be attached there. Split is the mirror: splay the key, then detach one child. Because every function returns the new root, callers must always store it; forgetting to is the most common bug.

Worked example: from a path to a tree

Insert 1, 2, 3, 4, 5, 6, 7 in ascending order. Each insert splays the previous maximum to the root and makes the new key the root with the old tree as its left child. The result is a path: 7 at the root, 6 as its left child, down to 1 at depth 6. Each insert was cheap, and the tree is as unbalanced as a tree can be.

Now search for 1. The splay walks all seven nodes, an O(n) operation, and the zig-zig steps fold the path as they go: 1 becomes the root, and the remaining nodes end up in a tree of roughly half the original depth. Searching for 2, then 3, keeps folding. This is amortisation made concrete: the cheap inserts built up potential in the form of a bad shape, and the expensive search spent it. Run the code above, print depths after each step and watch it happen; that exercise teaches more than the proof.

Why it is O(log n) amortised

Give each node x a size s(x), the number of nodes in its subtree, and a rank r(x) = log2 s(x). The potential of the tree is the sum of all ranks. A path of n nodes has potential about log2 n!, which is Theta(n log n); a balanced tree has potential Theta(n). Amortised cost is actual rotations plus the change in potential.

The access lemma says the amortised cost of splaying x in a tree with root t is at most 3(r(t) - r(x)) + 1. It is proved step by step: each zig-zig or zig-zag step costs at most 3 times the rank increase of x during that step, and the single zig at the end adds at most 1. The sum telescopes. Since r(t) = log2 n and r(x) is at least 0, an access is amortised O(log n). Over m operations, total actual cost is at most the amortised total plus the initial potential minus the final potential, which gives O((m + n) log n).

The lemma works for any positive weights, not just 1 per node, and choosing weights cleverly is how the stronger theorems below are proved without the tree ever knowing the weights.

Better than log n on structured sequences

Several results show splay trees doing better than O(log n) on structured sequences, without any tuning:

• Static optimality. If key i is accessed q_i times out of m, the total cost is O(m + sum of q_i log(m / q_i)), matching the best fixed tree for those frequencies up to a constant.
• Working set. Accessing a key costs amortised O(log(w + 1)), where w is the number of distinct keys accessed since the last access to that key. Hot keys are cheap.
• Sequential access. Accessing all n keys in sorted order costs O(n) in total, proved by Tarjan in 1985.
• Dynamic finger. Accessing a key near the previous one, by rank distance d, costs amortised O(log(d + 1)), proved by Cole.

The dynamic optimality conjecture, stated by Sleator and Tarjan in 1985, says splay trees are within a constant factor of the best possible binary search tree algorithm on every access sequence. It remains open; do not cite it as a theorem.

Augmenting: sizes, ranks and sequences

Splay trees take augmentation as easily as any BST, because every structural change is a rotation and a rotation only changes the two nodes it moves. Store a subtree size in each node and recompute it bottom-up after each rotation, child before parent, and you get rank queries and k-th smallest in amortised O(log n). In the top-down splay the nodes linked into the left and right trees have stale sizes until reassembly, so the simplest correct approach is a bottom-up splay with parent pointers, or a recursive descent that fixes sizes on the way back up for moderate depths.

Drop the keys entirely and navigate by size instead, and the tree represents a sequence: position k is found by comparing k with the left subtree's size. Splaying position i to the root and position j to the root's right child isolates the range between them as a single subtree, which you can sum, assign or reverse lazily with a flag pushed down before each rotation. On a Node extended with size and rev slots:

def size(n):
    return n.size if n else 0

def pull(n):                     # call after any rotation, on the lower node first
    n.size = 1 + size(n.left) + size(n.right)

def push(n):                     # call before descending through n
    if n.rev:
        n.left, n.right = n.right, n.left
        for ch in (n.left, n.right):
            if ch:
                ch.rev = not ch.rev
        n.rev = False

Missing a single push before a rotation is the classic bug: the tree stays a valid shape and silently returns the wrong order.

Where splay trees are used

The most important modern use is as the auxiliary tree inside link-cut trees, where splaying a node to the top of its preferred path is exactly the operation needed, and the amortised analysis composes cleanly; see link-cut trees. Splay trees keyed implicitly by position, carrying subtree sizes and lazy flags, also give sequences with split, concatenate and reverse in amortised O(log n), a common competitive-programming tool and an alternative to the implicit treap.

In systems, GNU libiberty ships a general splay tree used inside the GCC toolchain, and FreeBSD has used splay trees for virtual memory map entries, where lookups cluster around recently faulted regions. The common thread is a single-threaded structure with strong access locality.

Failure modes

• Reads write. Every lookup rotates nodes, so concurrent readers need exclusive locks and every read dirties cache lines. Under multi-threaded read-heavy load, a splay tree is often slower than a balanced tree with shared locks.
• Latency spikes. A single operation can cost O(n). If you have per-request latency bounds, such as an interrupt handler or a real-time loop, amortised guarantees are the wrong kind.
• Recursive bottom-up code on a path. A recursive splay on the ascending-insert path above overflows the stack for large n. Use top-down or an explicit loop.
• Forgetting the returned root. Calling splay(t, k) and continuing to use the old t corrupts the caller's view of the tree.
• Iterators invalidated by lookups. An in-order iteration that performs searches while walking sees the tree restructure underneath it.
• Adversarial uniform access. Uniform random lookups gain nothing from adaptivity and pay rotation costs on every access.

Trade-offs

What to do next

1. Type in the top-down splay, insert and delete above, and test them against a sorted list with random operations.
2. Reproduce the worked example: insert 1 to 1,000 in order, then search 1, 2, 3 and print the tree height after each search.
3. Measure: run a Zipf-distributed lookup workload against your splay tree and a red-black tree and compare total rotations and time.
4. Add subtree sizes to support rank and k-th element queries, updating them in each rotation.
5. Read Sleator and Tarjan's 1985 paper for the access lemma proof, then implement a link-cut tree on top of your splay.