Splay Trees

Ten keys and one deep node

Insert the keys 50, 20, 70, 10, 40, 30, 45, 25, 35, 22 into a plain binary search tree, in that order and with no rebalancing. Every key in a node's left subtree is smaller than the node's key, and every key in its right subtree is larger. A search walks down from the root, going left or right at each node.

Suppose a workload asks for 22 over and over. The tree answers each time by visiting the same six nodes, and it learns nothing from having been asked. A balanced tree (AVL, red-black) would put every key within about ${\log }_{2}n$ of the root, but only by storing balance information in every node and rebalancing on every update. And it too pays about ${\log }_{2}n$ for a key it returned a moment ago.

This module is about a tree that stores nothing but keys and pointers, rearranges itself on every access, and still guarantees $O(\log n)$ per operation. The guarantee is amortized: it holds for the total of any sequence of operations, not for each one.

import math, sys
sys.setrecursionlimit(10_000)

# A tree is None or a tuple (key, left, right). This lesson's own helpers,
# written as recursions on tuples; the lab builds nodes with parent pointers.
def insert(t, k):
    if t is None:
        return (k, None, None)
    key, left, right = t
    return (key, insert(left, k), right) if k < key else (key, left, insert(right, k))

def build(keys):
    t = None
    for k in keys:
        t = insert(t, k)
    return t

def preorder(t):
    return [] if t is None else [t[0]] + preorder(t[1]) + preorder(t[2])

def size(t):
    return 0 if t is None else 1 + size(t[1]) + size(t[2])

def depth(t, k):
    """Depth of the last node a search for k visits."""
    d = 0
    while True:
        nxt = t[1] if k < t[0] else t[2]
        if k == t[0] or nxt is None:
            return d
        t, d = nxt, d + 1

T = build([50, 20, 70, 10, 40, 30, 45, 25, 35, 22])
assert preorder(T) == [50, 20, 10, 40, 30, 25, 22, 35, 45, 70]
assert depth(T, 22) == 5 and depth(T, 35) == 4

Three obvious trees, and where each wastes work

A plain search tree is fast on random insertions and hopeless on sorted ones. Insert $0,1,\dots ,n-1$ in increasing order and every key hangs to the right of the one before: a path. Building it costs $0+1+\dots +(n-1)=n(n-1)/2$ comparisons, and every later search for a small key walks the whole path.

A balanced tree keeps every search at $O(\log n)$ in the worst case. It pays for that with a balance field in every node, rotations on updates, and roughly ${\log }_{2}n$ comparisons for every access, even when the same few keys are asked for all day.

Move to root is the obvious self-adjusting idea: after finding $x$, rotate it up one level at a time until it is the root. Repeated requests for 22 then cost one comparison. But it can leave the tree as deep as it found it. Take the path built by inserting $0,\dots ,999$, with key 999 at the root and 0 at the bottom, and access $0,1,2,\dots ,999$ three times over. Moving each key to the root costs 1,501,497 rotations in total, about $n/2$ per access. The splay tree of this module, on the same accesses, makes 13,122.

The waste in the first two is that nothing learned from an access is kept. The waste in move to root is subtler: it keeps the accessed key, but it does not shorten the path it came along.

The model: rotations

We work in the binary-search-tree model. Memory holds nodes with a key, a left and a right child pointer and a parent pointer. An access starts at the root and follows child pointers, comparing keys. The tree can be changed only by rotations.

A rotation of $x$ with its parent $p$ moves $x$ up one level. If $x$ is $p$'s left child, $x$'s right subtree becomes $p$'s left subtree and $p$ becomes $x$'s right child. The mirror case is symmetric. A rotation rewrites $O(1)$ pointers.

The cost of an access is the number of rotations it makes. That is fair: the splay tree always rotates the last node its search visited all the way to the root, so an access that visits $d+1$ nodes makes exactly $d$ rotations. Comparisons and rotations differ by one per access.

Splaying: rotations in pairs

To splay $x$ is to bring it to the root by repeating one of three steps. Let $p$ be $x$'s parent and $g$ its grandparent.

• zig: $p$ is the root. Rotate $x$. (This can happen only once, as the last step.)
• zig-zig: $x$ and $p$ are both left children, or both right children. Rotate $p$ first, then $x$.
• zig-zag: one is a left child and the other a right child. Rotate $x$ twice.

Every operation ends with a splay of the last node it touched. A search splays the node it found or, on a miss, the last node it visited. An insert splays the new leaf. A split at key $k$ splays the last node on $k$'s search path, after which the root's left or right pointer separates the keys $\le k$ from those $>k$. A join of $L$ and $R$, where every key of $L$ is smaller than every key of $R$, splays the largest key of $L$ to its root, which then has no right child, and hangs $R$ there. A delete splays the key and joins the root's two subtrees.

Move to root would rotate $x$ twice instead. It also ends with $x$ on top, but as $x(A,g(p(B,C),D))$: $p$ stays below $g$, two levels under $x$. The nodes that were on the search path rise by only one level each, so a long path stays long. Rotating $p$ first roughly halves the depth of every node on the path. That one-word difference is the whole algorithm.

Splaying 22

Here is 22 splayed in $T$. Its parent is 25 and its grandparent 30, both left links: a zig-zig. Then 22's parent is 40 (22 is its left child) and its grandparent is 20 (40 is its right child): a zig-zag. Finally its parent is the root 50: a zig. That is $2+2+1=5$ rotations, one per edge of the original path.

The lesson checks the trace with its own splay, a recursion on tuples. It pairs steps from the bottom, as the definition does: when $x$ is at odd depth, the single zig happens at the top.

def splay(t, k, steps=None, d=None):
    """Splay the last node a search for k visits (at depth d); return the new tree."""
    d = depth(t, k) if d is None else d
    if d == 0:
        return t
    key, left, right = t
    go_left = k < key
    c = left if go_left else right
    if d % 2 == 1:                                    # zig at the root, last
        ck, cl, cr = splay(c, k, steps, d - 1)
        if steps is not None:
            steps.append(("zig", key, None))
        return (ck, cl, (key, cr, right)) if go_left else (ck, (key, left, cl), cr)
    ck, cl, cr = c
    below_left = k < ck
    xk, xl, xr = splay(cl if below_left else cr, k, steps, d - 2)
    if go_left == below_left:
        if steps is not None:
            steps.append(("zig-zig", ck, key))
        if go_left:
            return (xk, xl, (ck, xr, (key, cr, right)))
        return (xk, (ck, (key, left, cl), xl), xr)
    if steps is not None:
        steps.append(("zig-zag", ck, key))
    if go_left:
        return (xk, (ck, cl, xl), (key, xr, right))
    return (xk, (key, left, xl), (ck, xr, cr))

steps = []
T22 = splay(T, 22, steps)
assert steps == [("zig-zig", 25, 30), ("zig-zag", 40, 20), ("zig", 50, None)]
assert preorder(T22) == [22, 20, 10, 50, 40, 25, 30, 35, 45, 70]
assert depth(T22, 35) == 5

steps = []
T35 = splay(T22, 35, steps)
assert steps == [("zig-zig", 30, 25), ("zig-zig", 40, 50), ("zig", 22, None)]
assert preorder(T35) == [35, 22, 20, 10, 30, 25, 40, 50, 45, 70]

A potential for search trees

The amortized argument uses module 07's potential method: assign each tree a number $\Phi$, define an operation's amortized cost as its actual cost plus $\Delta \Phi$, and add up. The sum telescopes, so over any sequence of operations

$$\text{total actual}=\text{total amortized}+{\Phi }_{\text{start}}-{\Phi }_{\text{end}}.$$

For search trees, let $s(v)$ be the number of nodes in $v$'s subtree ($v$ included), let the rank of $v$ be $r(v)={\log }_{2}s(v)$, and let

$$\Phi (T)=\sum _{v\in T}r(v)=\sum _{v\in T}{\log }_{2}s(v).$$

A leaf has rank 0 and the root has rank ${\log }_{2}n$. A long path has large potential: its subtree sizes are $1,2,\dots ,n$, so $\Phi ={\log }_{2}n!$, about $n{\log }_{2}n$. A balanced tree has $\Phi =O(n)$. That is the right shape for an amortized argument: a deep tree has saved up potential, and a splay that shortens a long path releases it to pay for the rotations.

On $T$, $\Phi$ goes from 11.907 to 13.492 after the zig-zig, down to 12.229 after the zig-zag, and to 12.036 after the zig. Each step's amortized cost (rotations plus $\Delta \Phi$) is within the bound the next section proves for it.

def phi(t):
    return 0.0 if t is None else math.log2(size(t)) + phi(t[1]) + phi(t[2])

def rank(t, k):
    while t[0] != k:
        t = t[1] if k < t[0] else t[2]
    return math.log2(size(t))

after = [build([50, 20, 10, 40, 22, 25, 30, 35, 45, 70]),     # after the zig-zig
         build([50, 22, 20, 10, 40, 25, 30, 35, 45, 70]),     # after the zig-zag
         T22]                                                 # after the zig
trees, cost = [T] + after, [2, 2, 1]
assert [round(phi(t), 3) for t in trees] == [11.907, 13.492, 12.229, 12.036]
for i, c in enumerate(cost):
    amortized = c + phi(trees[i + 1]) - phi(trees[i])
    bound = 3 * (rank(trees[i + 1], 22) - rank(trees[i], 22)) + (1 if c == 1 else 0)
    assert amortized <= bound + 1e-9
whole = 5 + phi(T22) - phi(T)
assert round(whole, 2) == 5.13 and whole <= 3 * math.log2(10) + 1   # 10.97

The Access Lemma

Write $r$ and $s$ for ranks and sizes before a step and $r^{\prime }$, $s^{\prime }$ after it. A step changes the subtrees of $x$, $p$ and (in a double step) $g$ only, so only those ranks change.

One fact about logarithms. If $a,b>0$ and $a+b\le c$, then ${\log }_{2}a+{\log }_{2}b\le 2{\log }_{2}c-2$. Indeed $ab\le {\left(\frac{a+b}{2}\right)}^2\le \frac{c^2}{4}$ by the inequality of arithmetic and geometric means; take ${\log }_2$ of both ends.

zig-zig, in full. The actual cost is 2. The change in potential is

$$\Delta \Phi =r^{\prime }(x)+r^{\prime }(p)+r^{\prime }(g)-r(x)-r(p)-r(g).$$

After the step, $x$'s subtree holds exactly the nodes $g$'s subtree held before, so $r^{\prime }(x)=r(g)$ and those two terms cancel. Before the step $x$ was below $p$, so $r(p)\ge r(x)$; after it $p$ is below $x$, so $r^{\prime }(p)\le r^{\prime }(x)$. Hence

$$\Delta \Phi \le r^{\prime }(x)+r^{\prime }(g)-2r(x).$$

Now the step that must not be skipped. After rotating $p$ first and then $x$, $g$'s new subtree is $g$ with $C$ and $D$, while $x$'s old subtree was $x$ with $A$ and $B$. The two are disjoint, and both lie inside $x$'s new subtree, which also contains $p$. So $s(x)+s^{\prime }(g)\le s^{\prime }(x)$, and the fact about logarithms gives $r(x)+r^{\prime }(g)\le 2r^{\prime }(x)-2$, that is, $r^{\prime }(g)\le 2r^{\prime }(x)-r(x)-2$. Substituting,

$$2+\Delta \Phi \le 2+r^{\prime }(x)+(2r^{\prime }(x)-r(x)-2)-2r(x)=3(r^{\prime }(x)-r(x)).$$

The $-2$ from the logarithm fact pays for the two rotations. Without the disjointness, there is no $-2$, and that is exactly where move to root fails: rotating $x$ twice leaves $g$'s new subtree overlapping $x$'s old one.

zig-zag, in brief. Again $r^{\prime }(x)=r(g)$ and $r(p)\ge r(x)$, so $\Delta \Phi \le r^{\prime }(p)+r^{\prime }(g)-2r(x)$. After the step $p$ and $g$ are the two children of $x$ with disjoint subtrees, so $s^{\prime }(p)+s^{\prime }(g)\le s^{\prime }(x)$ and $r^{\prime }(p)+r^{\prime }(g)\le 2r^{\prime }(x)-2$. That gives $2+\Delta \Phi \le 2(r^{\prime }(x)-r(x))\le 3(r^{\prime }(x)-r(x))$.

zig, in brief. The cost is 1, and only $x$ and $p$ change: $r^{\prime }(p)\le r(p)$, so $1+\Delta \Phi \le 1+r^{\prime }(x)-r(x)\le 1+3(r^{\prime }(x)-r(x))$.

Adding up. Each step's bound is 3 times the rise in $x$'s rank, so the bounds telescope: their sum is $3$ times ($x$'s final rank minus its first rank). At the end $x$ is the root of the same set of nodes, so its final rank is $r(t)$. At most one step is a zig, which adds the $+1$.

From one splay to a sequence

Balance Theorem. Start from any binary search tree $T_0$ with $n$ nodes and perform $m$ accesses, each splaying the last node its search visits. Then the total number of rotations is at most

$$m(3{\log }_{2}n+1)+\Phi (T_0)-\Phi (T_m)\le m(3{\log }_{2}n+1)+{\log }_{2}n!.$$

Proof. Sum the Access Lemma over the accesses and use the telescoping identity. Every rank is at least 0, so $\Phi (T_m)\ge 0$. For the other end, the $j$-th largest subtree in any tree has at most $n-j+1$ nodes (the $j-1$ nodes with larger or equal subtrees are not below it), so $\Phi (T_0)\le {\log }_{2}n!\le n{\log }_{2}n$, with equality for a path. $◻$

Do not drop the $\Phi (T_0)$ term. It is what lets a single access be expensive. On the path built by inserting $0,\dots ,999$, the very first access, to key 0, makes 999 rotations. The lemma charges it at most $3{\log }_{2}1000+1\approx 30.9$; the rest is paid out of the path's potential, ${\log }_{2}1000!\approx 8529$. Once $m\ge n$, the initial term adds at most ${\log }_{2}n$ per access, and the bound is amortized $O(\log n)$ per access.

def path(n):                      # what inserting 0..n-1 with splaying builds
    t = None
    for k in range(n):
        t = (k, t, None)
    return t

P = path(1000)
assert depth(P, 0) == 999                          # 999 rotations to splay 0
assert round(phi(P)) == round(math.lgamma(1001) / math.log(2)) == 8529

def move_to_root(t, k, count, d=None):
    """Rotate the last node on k's path up one level at a time."""
    d = depth(t, k) if d is None else d
    if d == 0:
        return t
    key, left, right = t
    count[0] += 1                                     # the rotation at this level
    if k < key:
        ck, cl, cr = move_to_root(left, k, count, d - 1)
        return (ck, cl, (key, cr, right))
    ck, cl, cr = move_to_root(right, k, count, d - 1)
    return (ck, (key, left, cl), cr)

def three_passes(rule):
    t, rotations = path(1000), 0
    for _ in range(3):
        for k in range(1000):
            if rule == "splay":
                rotations += depth(t, k)
                t = splay(t, k)
            else:
                count = [0]
                t = move_to_root(t, k, count)
                rotations += count[0]
    return rotations

assert three_passes("splay") == 13_122
assert three_passes("move to root") == 1_501_497

Other operations. Insert, delete, split and join are also amortized $O(\log n)$, with $n$ the largest size the tree reaches. Sketch: attaching a new leaf raises the ranks of its ancestors, but for consecutive ancestors $v$ below $u$ the new size of $v$ is at most the old size of $u$, so the increases telescope to at most ${\log }_2(n+1)$, and the splay that follows obeys the lemma. Removing the root or cutting a pointer only lowers ranks, and hanging $R$ under the root of $L$ raises one rank by at most ${\log }_{2}n$. Starting from an empty tree, ${\Phi }_0=0$ and there is no initial term at all.

Worst case versus amortized. One operation can cost $\Theta (n)$, as the 999-rotation access shows. The guarantee is for every sequence, divided by its length. It involves no probability and no assumption about the input: an adversary who knows the code gets the same bound. A system with a deadline on each operation (an interrupt handler, a real-time controller) needs a worst-case structure such as a red-black tree instead.

Lower bound. In any binary search tree fewer than $2^d$ nodes have depth below $d$, so fewer than a quarter of the $n$ keys are within depth ${\log }_{2}n-2$ of the root, whatever shape the tree has. A uniformly random access therefore visits more than ${\log }_{2}n-2$ nodes with probability at least $3/4$, and $\Omega (\log n)$ per access in expectation is unavoidable on such sequences. The splay tree's bound is optimal up to its constant.

Beyond $O(\log n)$

The Access Lemma holds with any positive weights in place of 1 in the sizes, and choosing the weights cleverly proves much more. These results are stated here, not proved:

• Static optimality (Sleator and Tarjan, 1985). If key $i$ is accessed $q_i\ge 1$ times, $m$ times in all, the total cost is $O(m+{\sum }_i{q}_i{\log }_2(m/q_i))$. That is within a constant factor of the best fixed search tree for those counts, and the splay tree never learns the counts.
• Working set (same paper). An access to $x$ costs amortized $O(\log (t+1))$, where $t$ is the number of distinct keys accessed since the previous access to $x$ (plus an $O(n\log n)$ start-up term for the whole sequence). Recently used keys are cheap.
• Sequential access (Tarjan, 1985). Accessing all $n$ keys in increasing order costs $O(n)$ in total, whatever the starting tree. The 13,122 rotations above are that theorem at work.
• Dynamic optimality is a conjecture, open since 1985: that splay trees are within a constant factor of every binary-search-tree algorithm, even one that knows the whole access sequence in advance and rotates freely. Nobody has proved it or refuted it, for splay trees or for any other tree.

Measure the claim

Rotations per access, on trees built by inserting a shuffled $0,\dots ,n-1$ (the sequential rows by inserting in increasing order, which builds a path), followed by $4n$ accesses (seed 451, computed in the course's verification script):

On uniform keys the cost is about $1.2{\log }_{2}n$, well under the Access Lemma's $3{\log }_{2}n+1$ (these are measurements on these inputs, not a sharper theorem). The hot-key row stays flat as $n$ grows sixteen-fold, as the working-set theorem predicts for a working set of 16, and the sequential row stays flat as the sequential-access theorem predicts. A balanced tree would pay about ${\log }_{2}n$ comparisons in all three rows.

In real software

Splay trees are used where lookups are local and a simple structure is worth more than a per-operation guarantee. GCC's support library, libiberty (splay-tree.c), provides a splay tree that the compiler uses, for example, to map the variables of each OpenMP construct while it gimplifies the code (gimplify.cc). FreeBSD's sys/tree.h offers SPLAY_* macros that splay top-down, beside its rank-balanced trees; its own comment warns that every lookup causes memory writes. That is the price of self-adjustment: a read rewrites pointers, which costs cache traffic and needs a lock where a balanced tree could let many readers in at once.

A problem that looks different

A text editor holds a document of a million characters. Users cut a range of text and paste it somewhere else, hundreds of times a second, and the cursor mostly moves around one area of the document. Characters have no keys: position 400,000 names a different character after every paste. Can anything from this module keep each edit cheap? (Not solved here; the lab's last problem is a different one.)

Practise

In the lab you write a rotation and the potential and watch $\Phi$ after every rotation you make, predict and then trace the splay steps on a tree of your own, build a full splay tree with search, insert, delete, split and join, measure rotations per access for three workloads with your own experiments, and finish with a problem that doesn't say what it is.

Recap

• You can now: splay by hand with zig, zig-zig and zig-zag steps; implement every search-tree operation as a descent followed by a splay; prove the Access Lemma's zig-zig case from the rank potential; and state the Balance Theorem with its initial-potential term.
• Invariant: rotations keep the in-order sequence, and $\Phi ={\sum }_v{\log }_{2}s(v)$ pays for long paths: a splay of $x$ costs amortized at most $3(r(\text{root})-r(x))+1$ rotations.
• Complexity achieved: any $m$ accesses from an $n$-node tree cost at most $m(3{\log }_{2}n+1)+{\log }_{2}n!$ rotations, amortized $O(\log n)$ per operation with no balance field, against $\Theta (n)$ per operation for a plain tree on sorted input and $\Theta (n)$ per access for move to root on sequential access. A single operation can still cost $\Theta (n)$.
• Failure mode: rotating $x$ twice in the zig-zig case (move to root), or skipping the splay after an unsuccessful search, which leaves the long descent unpaid.
• In real software: GCC's libiberty splay-tree.c (used for OpenMP variable maps) and FreeBSD's sys/tree.h SPLAY_* macros.
• Retrieval: module 07's doubling array has amortized cost at most 3 per append. What role does its potential $\Phi =2·\text{size}-\text{cap}$ play that ${\sum }_v{\log }_{2}s(v)$ plays here, and why must both be compared with their starting value?

Check yourself

1. Why does the zig-zig step rotate the parent before $x$, and at which line of the proof does that order matter?
2. Drop the splay after an unsuccessful search, keeping it after successful ones. Give a sequence of operations on which the total cost is no longer $O((m+n)\log n)$.
3. For a controller with a deadline on every operation, and for a symbol table where 16 names receive most lookups, would you choose a red-black tree or a splay tree? Defend each choice with the kind of bound each tree gives.

Topic list modeled on the public schedule of CMU 15-451/651 Algorithm Design and Analysis (Fall 2025). All lecture text, proofs, examples, code, and exercises are original to SciMigo; no CMU course materials are reproduced. This course is independent and not affiliated with or endorsed by Carnegie Mellon University.