Splay Tree

A splay tree is a self-adjusting Binary Search Tree introduced by Daniel Sleator and Robert Tarjan in their 1985 Journal of the ACM paper “Self-Adjusting Binary Search Trees” (a 1983 STOC version preceded it). Splay trees have no balance information — no heights, no colors, no priorities — and yet achieve O(log n) amortized time per operation through a single, simple discipline: every accessed node is rotated all the way to the root via a sequence of double rotations called splay steps (zig, zig-zig, zig-zag). Recently accessed elements end up near the root; cold elements drift toward the leaves. This self-organizing behavior gives splay trees several remarkable properties — the balance theorem (any sequence of operations is O(log n) amortized per op), the static optimality theorem (matches the cost of any fixed BST that knew the access frequencies in advance, up to a constant), the working set theorem (recently used elements are cheap to re-access), and the deeply unsolved dynamic optimality conjecture (splay trees are within a constant of the optimal online BST). They are not balanced in the worst-case-per-op sense (a single operation can be O(n)) but are O(log n) averaged over m ≥ n operations. Production-relevant uses include caches (where access locality is high), LRU-like data structures, the GCC/libiberty splay-tree.h generic splay tree used throughout the GNU toolchain (e.g. for symbol and address lookups in the linker and debugger), and link-cut trees (the splay tree is their internal representation). The amortized analysis itself, via the potential method, is one of the canonical examples in algorithms textbooks — every CS undergraduate sees the access lemma proof at some point.

Uncertain

Verify: claims that the Linux kernel uses splay trees in its I/O scheduler or vmalloc allocator. Reason: a 2026 search indicates the Linux anticipatory/deadline/CFQ I/O schedulers and the vmalloc area tracking actually use red-black trees (rbtree), not splay trees — the earlier version of this note asserted splay-tree usage, which appears to be a common myth. To resolve: grep the kernel source (block/, mm/vmalloc.c) for the structures in question. The GCC/libiberty splay tree and the Boehm-Demers-Weiser GC’s use of splay trees are better attested but were not pinned to source here.

1. Intuition — A Tree That Learns Its Workload

Most balanced BSTs (AVL Tree, Red-Black Tree) treat every key as a first-class citizen: the structure is the same shape regardless of which keys are accessed. This is wasteful when access patterns are skewed — and access patterns in real workloads are almost always skewed. The 80/20 rule is an empirical regularity in caching, file access, web requests, command histories, and pretty much every other domain where data structures get hammered. A balanced BST keeps a rare key at the same depth as a popular key, paying log n for both.

Splay trees exploit this skew with a simple, unconditional rule: after every access (search, insert, or delete), splay the accessed node to the root. Splaying is a sequence of double rotations chosen so that, on average over the operations, the depth of frequently accessed elements stays small. Cold elements live deep in the tree; hot elements live near the root. Without explicitly tracking access counts, the tree’s shape adapts to the access pattern — a property called self-adjustment.

The accumulated effect over many operations is the amortized O(log n) bound. Any individual operation can be O(n) (if the accessed key is at the bottom of a long chain), but each such expensive operation flattens the tree, so subsequent operations are cheaper. The bookkeeping technique used to prove this — the potential method — distributes the cost of expensive operations across the cheap ones in a way that makes the per-operation amortized cost O(log n).

The real-world analogy: imagine a card index where every card you pull out gets put on top of the pile. The cards you use most often gravitate to the top; cards you never touch sink to the bottom. Looking up a popular card is fast (it is near the top); looking up an obscure card is slow (you dig deep), but pulling that card to the top means next time it is fast — and this is exactly the policy that, in expectation over many lookups, gets you O(log n) cost. The splay tree is the binary-tree implementation of this card-index policy.

The 1985 paper is one of the most influential in data-structures research. Beyond the splay tree itself, Sleator and Tarjan formalized the use of the potential method for amortized analysis (their Theorem 1 is the canonical “amortized cost = actual cost + change in potential” formula), introduced the working-set theorem as a sharp characterization of locality benefit, and formulated the dynamic optimality conjecture which remains open more than 40 years later: are splay trees within a constant factor of the optimal online BST?

2. The Splay Operation — Three Cases

Splaying a node x means moving it to the root via rotations. The naive approach — rotate x up to the root one parent at a time using simple rotations — does not give the amortized bound (Sleator and Tarjan show such “rotation to root” can have Ω(n²) cost for some sequences). The correct splay procedure looks at two levels at a time and uses three cases.

Let x be the node being splayed; p = x.parent; g = p.parent.

2.1 Zig (single rotation, only at the root)

If p is the root (i.e., g is null), do a single rotation to make x the root. This case applies at most once per splay — at the very end if the splay path has odd length.

Before:        After zig:
    p              x
   / \            / \
  x  T3   →      T1  p
 / \                / \
T1 T2              T2 T3

2.2 Zig-Zig (same direction, double rotation, parent first)

If p and x are both left children (or both right children — symmetric), rotate p first, then x. The “parent before child” order is critical: it is the difference between achieving O(log n) amortized and getting O(n) per operation.

Before zig-zig (x is p's left child, p is g's left child):
        g
       / \
      p  T4
     / \
    x  T3
   / \
  T1 T2

After rotation at g (right rotation):
        p
       / \
      x   g
     / \ / \
    T1 T2 T3 T4

After rotation at p (right rotation):
        x
       / \
      T1  p
         / \
        T2  g
           / \
          T3 T4

Equivalent for “right child of right child”: double left rotation, parent first.

2.3 Zig-Zag (opposite directions, double rotation, child first)

If x and p are on opposite sides (e.g., x is right child of p, p is left child of g), rotate x up first (twice).

Before zig-zag (x is p's right child, p is g's left child):
        g
       / \
      p  T4
     / \
    T1  x
       / \
      T2  T3

After left rotation at p:
        g
       / \
      x   T4
     / \
    p  T3
   / \
  T1 T2

After right rotation at g:
        x
       / \
      p   g
     / \ / \
    T1 T2 T3 T4

The combined zig-zag is a single double-rotation that brings x up two levels symmetrically.

2.4 Splay procedure

Splay(x):
    while x is not the root:
        p := x.parent
        g := p.parent
        if g is null:
            zig(x)              # case 1
        elif x and p are both left children or both right children:
            zig_zig(g, p, x)    # case 2 — rotate g first, then p
        else:
            zig_zag(g, p, x)    # case 3 — two rotations, opposite-side

Each iteration of the loop reduces x’s depth by 2 (zig-zig and zig-zag) or 1 (zig). When the loop terminates, x is the root.

2.5 Why the order matters in zig-zig

The non-obvious choice in the splay design is the rotation order in zig-zig. Rotating x up to p first (the “rotate child first” approach, which would give a left-leaning result) gives a tree whose shape depends linearly on the path length — leading to the Ω(n²) worst case mentioned in §1. Rotating p first creates a more balanced shape: the new subtree has x’s original subtrees T1, T2 at the top, and the deeper subtrees T3, T4 are pushed down by one level — which means the next operation’s path is roughly half-balanced, ensuring the amortized bound. This subtle ordering is the heart of why splay trees work; Sleator and Tarjan’s contribution was both finding the right rotation order and proving that it gives O(log n) amortized.

3. Tiny Worked Example — Splaying After Each Access

Start with a fully left-leaning chain — the worst-case BST shape, where every node except the bottom one has only a left child:

        50
       /
      40
     /
    30
   /
  20
 /
10

Here 50 is at depth 0 and 10 at depth 4. A search for 10 follows the leftmost path — O(n) work. After the search, we splay 10 to the root. (The mirror-image right-leaning chain works identically with left/right rotations swapped.)

3.1 Splay step 1 — zig-zig at 10

Here x = 10, parent p = 20, grandparent g = 30. Both x → p and p → g are left-child relationships, so this is a zig-zig step: rotate g first, then p.

After rotating g = 30 right (about its left child 20):

        50
       /
      40
     /
    20
   / \
  10  30

After rotating p = 20 right (about its left child 10):

        50
       /
      40
     /
    10
      \
      20
        \
        30

Now x = 10 is at depth 2 (was depth 4). Continue.

3.2 Splay step 2 — zig-zig at 10

x = 10, p = 40, g = 50. Both are left children. Apply zig-zig.

After rotating g = 50 right (about its left child 40):

   40
  /  \
 10  50
   \
   20
     \
     30

After rotating p = 40 right (about its left child 10):

   10
     \
     40
    /  \
   20  50
     \
     30

Now x = 10 is at the root. Splay complete.

3.3 Observe the structural change

Before splaying: chain of depth 4 (5 nodes in a vertical line). After splaying: tree of depth 3 with branching — 10 at top, 40 as right child, 20 and 50 as 40’s children, 30 as 20’s right child.

The chain has been flattened: any subsequent search for the original keys finds them at most 3 levels deep (vs 4 before). The single expensive splay operation (O(n) work) restructured the tree so that future operations are cheaper. This is the amortization in action: pay a lot once, save a lot many times.

The asymptotic effect of splaying after every access is that the amortized cost becomes O(log n) per operation, even though individual operations can be O(n).

4. Algorithm — Search, Insert, Delete (All Splay-Then-Modify)

Every operation in a splay tree consists of: (1) a standard BST traversal to find the relevant node, and (2) a splay of that node (or a near-by node, in delete) to the root.

4.1 Search

SplaySearch(T, k):
    node := T.root
    last := node
    while node is not null and node.key != k:
        last := node
        if k < node.key:
            node = node.left
        else:
            node = node.right
    target := node if node is not null else last  # if k not found, splay the last visited
    Splay(target)
    return target.key == k

Splay even on a failed search — the last visited node is splayed to the root. This is what makes the working set theorem work for misses too.

4.2 Insert

SplayInsert(T, k):
    if T is empty:
        T.root := new Node(k)
        return
    # Standard BST descent
    node := T.root
    parent := null
    while node is not null:
        parent := node
        if k < node.key: node := node.left
        elif k > node.key: node := node.right
        else: Splay(node); return    # duplicate — splay existing node, no insert
    new_node := new Node(k, parent)
    if k < parent.key: parent.left := new_node
    else: parent.right := new_node
    Splay(new_node)

4.3 Delete (split via splay)

A common delete recipe: splay the node to be deleted to the root, then “snip” by joining its left and right subtrees.

SplayDelete(T, k):
    if not SplaySearch(T, k):
        return    # k not in tree
    # k is now at the root.
    L := T.root.left
    R := T.root.right
    if L is null:
        T.root := R
    else:
        # Splay the maximum of L to L's root (so it has no right child).
        # Then attach R as L's right subtree.
        T.root := L
        Splay(MaxNode(L))     # now L's root has no right child
        T.root.right := R

Splaying the maximum of L to the root makes its right subtree empty (because the max has no right child by BST property). Then R slots in as that right subtree. Total: 2 splays + a constant-amount of pointer surgery.

4.4 Split and Join

The split-merge interface (sometimes called split and join in splay-tree literature):

• Split(T, k) returns (L, R) where L has all keys ≤ k, R all keys > k. Implementation: search for k, splay it to the root; the root’s left subtree (plus the root) is L, the root’s right subtree is R.
• Join(L, R) (assuming all keys in L < all keys in R): splay MaxNode(L) to the root of L; attach R as its right child.

Both operations are O(log n) amortized.

5. Python Implementation

from typing import Optional
 
class SplayNode:
    __slots__ = ("key", "left", "right", "parent")
    def __init__(self, key, parent=None):
        self.key = key
        self.left: Optional[SplayNode] = None
        self.right: Optional[SplayNode] = None
        self.parent: Optional[SplayNode] = parent
 
class SplayTree:
    def __init__(self):
        self.root: Optional[SplayNode] = None
 
    # -------- Rotations (with parent maintenance) --------
    def _rotate_right(self, y: SplayNode) -> None:
        x = y.left
        assert x is not None
        y.left = x.right
        if x.right is not None:
            x.right.parent = y
        x.parent = y.parent
        if y.parent is None:
            self.root = x
        elif y is y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x
        x.right = y
        y.parent = x
 
    def _rotate_left(self, x: SplayNode) -> None:
        y = x.right
        assert y is not None
        x.right = y.left
        if y.left is not None:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y
 
    # -------- Splay operation --------
    def _splay(self, x: SplayNode) -> None:
        while x.parent is not None:
            p = x.parent
            g = p.parent
            if g is None:
                # zig
                if x is p.left:
                    self._rotate_right(p)
                else:
                    self._rotate_left(p)
            elif x is p.left and p is g.left:
                # zig-zig (both left): rotate grandparent first, then parent
                self._rotate_right(g)
                self._rotate_right(p)
            elif x is p.right and p is g.right:
                # zig-zig (both right)
                self._rotate_left(g)
                self._rotate_left(p)
            elif x is p.left and p is g.right:
                # zig-zag: rotate parent first (toward x's side), then grandparent
                self._rotate_right(p)
                self._rotate_left(g)
            else:
                self._rotate_left(p)
                self._rotate_right(g)
 
    # -------- Search (with splay) --------
    def search(self, k) -> bool:
        node = self.root
        last = node
        while node is not None and node.key != k:
            last = node
            node = node.left if k < node.key else node.right
        target = node if node is not None else last
        if target is not None:
            self._splay(target)
        return self.root is not None and self.root.key == k
 
    # -------- Insert --------
    def insert(self, k) -> None:
        if self.root is None:
            self.root = SplayNode(k)
            return
        node = self.root
        parent = None
        while node is not None:
            parent = node
            if k < node.key: node = node.left
            elif k > node.key: node = node.right
            else: self._splay(node); return  # duplicate
        new_node = SplayNode(k, parent=parent)
        if k < parent.key:
            parent.left = new_node
        else:
            parent.right = new_node
        self._splay(new_node)
 
    # -------- Delete --------
    def _max_node(self, node: SplayNode) -> SplayNode:
        while node.right is not None:
            node = node.right
        return node
 
    def delete(self, k) -> bool:
        if not self.search(k):
            return False
        # k is now at the root.
        root = self.root
        assert root is not None
        L = root.left
        R = root.right
        if L is not None: L.parent = None
        if R is not None: R.parent = None
        if L is None:
            self.root = R
        else:
            self.root = L
            max_L = self._max_node(L)
            self._splay(max_L)
            self.root.right = R
            if R is not None:
                R.parent = self.root
        return True
 
    # -------- In-order (sanity check) --------
    def in_order(self, node: Optional[SplayNode] = None) -> list:
        if node is None:
            node = self.root
        if node is None:
            return []
        return self.in_order(node.left) + [node.key] + self.in_order(node.right)
 
 
# Demo
st = SplayTree()
for k in [50, 40, 30, 20, 10]:
    st.insert(k)
# Search for 10 — should bring it to the root.
assert st.search(10) is True
assert st.root is not None and st.root.key == 10
# Tree is no longer a chain — 10's splay flattened it.
assert st.in_order() == [10, 20, 30, 40, 50]
# Search for non-existent — splays the closest visited node.
assert st.search(99) is False
# Delete and re-validate.
assert st.delete(30) is True
assert st.in_order() == [10, 20, 40, 50]

Three implementation notes:

1. Parent pointers are required. Splaying needs to walk up from x to the root, examining grandparents at each step. Without parent pointers, you would need to store the path during the search. Iterative implementations always use parent pointers.

2. Rotations must update both child and parent pointers, including the parent’s parent’s pointer to the new subtree root. Forgetting any one of these creates dangling pointers, and the splay-up loop walks into them and crashes.

3. The zig-zig case rotates grandparent before parent, not the other way around. This is the single most important splay-tree implementation detail — the order is what makes the amortized bound work. Reversing the order is a famous “looks like an optimization” bug that gives O(n) per op on adversarial inputs.

6. Complexity — The Amortized Analysis

6.1 Per-operation amortized costs

Operation	Worst case	Amortized
Search	O(n)	O(log n)
Insert	O(n)	O(log n)
Delete	O(n)	O(log n)
Split	O(n)	O(log n)
Join	O(n)	O(log n)

Amortized over any sequence of m ≥ n operations starting from any initial tree.

6.2 The Access Lemma — proof sketch

Access lemma (Sleator-Tarjan 1985, Lemma 1). Let T be a splay tree with root t. Assign each node x a fixed positive weight w(x) (the weights are parameters of the analysis, not of the algorithm). Define the size s(x) of a node as the total weight of all items in x’s subtree (x included), and the rank r(x) = log₂(s(x)) — the paper uses binary logarithms throughout. Define the potential of the tree Φ(T) = Σ_x r(x), the sum of all node ranks.

The amortized time to splay node x to the root is at most

3(r(t) − r(x)) + 1 = O(log(s(t)/s(x))),

where r(t) is the rank of the root before the splay (per the paper’s Lemma 1, quoted exactly). The “amortized time” here counts the number of rotations (or 1 if no rotation happens), under the convention amortized = actual + ΔΦ.

For uniform weights w(x) = 1 and a tree of n nodes, s(t) = n so r(t) = log₂ n, while s(x) ≥ 1 so r(x) ≥ 0. The bound becomes 3 log₂ n + 1 = O(log n).

Sketch of the proof. Walk the splay one step at a time and bound each step’s amortized cost; the steps telescope. Let r, r' be the ranks just before and just after a step. The paper shows:

• Zig (Case 1, one rotation): amortized cost ≤ 1 + 3(r'(x) − r(x)).
• Zig-zig (Case 2, two rotations): amortized cost ≤ 3(r'(x) − r(x)). The crux is the claim 2r'(x) − r(x) − r'(z) ≥ 2, where z is the original grandparent. This follows from the concavity of log: for a, b > 0, log a + log b subject to a + b ≤ c is maximized when a = b, giving log a + log b ≤ 2 log(c/2) = 2 log c − 2. Applying this to a = s(x) (size after) and b = s'(z) (size of z after), whose sum is at most s'(x) (size of x after), yields r(x) + r'(z) − 2r'(x) ≤ −2, i.e. the desired inequality. The 2 here exactly cancels the actual cost (two rotations) so the step’s amortized cost collapses to 3(r'(x) − r(x)).
• Zig-zag (Case 3, two rotations): amortized cost ≤ 2(r'(x) − r(x)) ≤ 3(r'(x) − r(x)), by the analogous concavity argument.

Summing over all steps, the 3(r'(x) − r(x)) terms telescope (each step’s r'(x) is the next step’s r(x)) to 3(r(t) − r(x)), where r(t) is the root rank at the end (the root is now x, but its size equals the old root’s size, so r(t) is unchanged). The lone +1 is the residual from the single zig step, if the path length is odd. Full proof in Sleator-Tarjan 1985 §2 (Lemma 1) or Tarjan’s textbook Data Structures and Network Algorithms Ch. 4. Note: the continuous-log version above is tighter by a factor of two than the original conference paper’s discrete-rank analysis — a refinement Sleator and Tarjan credit to Huddleston.

6.3 Implications — the four headline theorems

The access lemma is a single technical statement. From it, four “named theorems” follow as corollaries by choosing the weight function w cleverly (these are Theorems 1–4 in the paper, and the paper combines them into a single Theorem 5, the Unified Theorem). Throughout, m is the number of accesses and n the number of items:

(A) Balance theorem (Theorem 1). Set w(i) = 1/n for every item. Then W = Σ w = 1, the amortized cost of any access is ≤ 3 log n + 1, and the net potential drop over the whole sequence is at most n log n. So total access time is O((m + n) log n) — splay is, on a long sequence, as efficient as any uniformly balanced tree.

(B) Static optimality theorem (Theorem 2). Let q(i) be the number of times item i is accessed (so Σ q(i) = m), and assume every item is accessed at least once. Set w(i) = q(i)/m. The paper’s exact bound is

total access time = O(m + Σᵢ q(i) log(m / q(i))).

By a standard information-theory result, any fixed BST has total cost Ω(Σ q(i) log(m/q(i))) for those frequencies, so splay trees match the best static frequency-aware tree (including the optimum BST) to within a constant — without ever being told the frequencies. The summation Σ q(i) log(m/q(i)) is m times the empirical entropy of the access distribution.

(C) Working set theorem (Theorem 4). This one changes the weights as the accesses occur rather than fixing them. Number the accesses 1..m; for access j, let t(j) be the number of distinct items accessed since item i_j was last accessed (or since the start, if this is its first access). The paper assigns the weights 1, 1/4, 1/9, …, 1/n² (i.e. 1/k²) to items by recency rank — the most-recently-touched item gets weight 1, the next 1/4, and so on — and reassigns them after each access so the just-accessed item moves back to weight 1. Because W = Σ 1/k² = O(1) and the just-accessed item carries weight 1/(t(j)+1)², the amortized cost of access j is O(log(t(j)+1)). Total:

O(n log n + m + Σⱼ log(t(j) + 1)).

So re-accessing an item you touched recently (small working set since) is cheap — O(log 5) if only 5 distinct items intervened — regardless of n. This formalizes temporal locality.

The paper also proves a static finger theorem (Theorem 3): for any fixed item f, total cost is O(n log n + m + Σⱼ log(|iⱼ − f| + 1)), i.e. accesses near a fixed “finger” position are cheap. All four (Balance, Static Optimality, Static Finger, Working Set) are folded into the single Unified Theorem (Theorem 5) by summing the weights; splay trees enjoy all of them simultaneously, automatically, at the cost of one constant factor.

(D) Sequential access theorem — a separate, harder result. Accessing the n items in sorted order from any initial splay tree takes O(n) total — O(1) amortized per access. This is not a corollary of the access lemma above; the natural geometric-weight argument does not yield it. It is proved by a different, more intricate combinatorial argument in a separate paper: Tarjan, “Sequential access in splay trees takes linear time,” Combinatorica 5(4):367–378, 1985 (generalizing an unpublished result of Wegman). The dynamic-optimality conjecture would imply it as a trivial special case, but the conjecture is open, so the sequential-access theorem stands on its own footing.

Why these are corollaries of one lemma

The access lemma holds for any positive weight assignment. The art is in choosing weights so that (i) each access becomes cheap under those weights and (ii) the total potential drop across the whole sequence is bounded. Different weight choices surface different structural properties of the access sequence — uniformity, frequency-skew, recency, locality — which is why one inequality yields a whole family of optimality results.

6.4 The dynamic optimality conjecture

The deepest open question in self-adjusting BSTs.

Conjecture (Sleator-Tarjan 1985, §7): Splay trees are within a constant factor of the optimal BST algorithm for any access sequence — i.e., they are O(1)-competitive against the best possible BST (even one tailored offline to the exact sequence). The paper states it as: splay trees are “as efficient on any sufficiently long sequence of accesses as any form of dynamically updated binary search tree, even one tailored to the exact access sequence.”

Status as of 2026: still open — it remains a headline open problem in data structures, and is precisely the special case for which the sequential access theorem (proved separately) holds. The relevant landmarks:

• Tango trees (Demaine, Harmon, Iacono, Patrascu, “Dynamic Optimality—Almost,” FOCS 2004 / SIAM J. Comput. 2007): a competing online BST that is provably O(log log n)-competitive against the optimal offline BST — the first sub-O(log n) competitive ratio for any online BST. Splay trees have not been shown to be O(log log n)-competitive, nor have they been shown not to be O(1)-competitive.
• The best known competitive ratio for any specific online BST (and a barrier any candidate must beat) is the near-optimal bound 2^{α(n)(1+o(1))} of Chalermsook, Pettie, and Yingchareonthawornchai (SODA 2024), where α is the inverse-Ackermann function — astronomically slow-growing, but still not the constant the conjecture demands.

So splay trees might be O(1)-competitive (no counterexample is known), but proving it has resisted four decades of effort.

6.5 Space

Each node stores key, left/right children, and a parent pointer. No balance information. Total O(n).

7. Variants and Use Cases

7.1 Top-down splay (instead of bottom-up)

The splay procedure in §2 is “bottom-up”: find x, then splay it up. Top-down splay integrates the splay step into the descent itself: as you walk down looking for x, you simultaneously rebuild the tree’s spine to position x at the root by the time you find it. Constant-factor faster than bottom-up; harder to implement; preferred in performance-critical code (Sleator’s reference C implementation uses top-down).

7.2 Splay tree of intervals

Augment each node with an interval and propagate min/max upward. Used in computational geometry (sweepline algorithms) for O(log n) interval insertion/deletion and overlap queries.

7.3 Link-cut trees

Splay trees are the underlying data structure for link-cut trees (Sleator-Tarjan 1983), which support dynamic-tree operations: link two trees, cut an edge, find path-aggregations — each in O(log n) amortized. Used in network flow algorithms and dynamic graph connectivity.

7.4 Splay tree as a cache replacement structure

A splay tree’s self-adjustment makes it a natural cache: hot keys stay near the root, cold keys sink. The “least recently used” keys are at the deepest leaves and can be pruned cheaply. Some embedded systems use splay trees as their primary cache structure for this reason.

7.5 Comparison with other balanced BSTs

Property	Splay	AVL Tree	Red-Black Tree	Treap
Time guarantee	Amortized O(log n)	Worst-case O(log n)	Worst-case O(log n)	Expected O(log n)
Implementation lines	~120	~150	~250	~80
Per-node bookkeeping	None	Height (1–2 bytes)	Color (1 bit)	Priority (8 bytes)
Self-adjustment	Yes	No	No	No
Optimal under skew	Static + working set	No	No	No
Single op worst case	O(n)	O(log n)	O(log n)	O(n) (vanishing prob.)
Cache locality	Excellent (hot keys at top)	Good	Good	Mediocre (random shape)

Splay trees are the right choice when access patterns are skewed (cache-like workloads) and worst-case-per-op bounds are not required. They are the wrong choice when individual operations must complete within a bounded time (real-time systems) — a single access can be O(n).

8. Pitfalls

8.1 Reversing the zig-zig rotation order

The zig-zig case rotates g first, then p. Reversing this (rotating p first, then g) gives a correct BST but loses the amortized bound — adversarial sequences can make a “naive zig-zig” splay tree go quadratic. This bug is silent: the tree always returns correct answers; only the amortized analysis fails. The single most subtle correctness invariant in splay trees.

8.2 Forgetting to splay on misses

A failed search must still splay the last visited node to the root. Skipping this loses the working-set theorem (recently searched-for-but-missing keys must move toward the root for the locality benefit). Some textbooks mention this only in passing; verify your implementation.

8.3 Using splay in real-time / latency-bounded systems

A splay tree’s individual operation can be O(n). If your system needs to guarantee a bounded latency per op (real-time control, hard-deadline schedulers, latency-SLO databases), splay trees are inappropriate. Use AVL Tree or Red-Black Tree for worst-case bounds.

8.4 Concurrency

Splay trees are notoriously hard to make concurrent because every read modifies the tree. Two readers performing concurrent searches for different keys both want to splay their respective keys to the root simultaneously — this is a write-write conflict at the root. Production concurrent ordered maps almost universally use Skip Lists or Red-Black Trees with reader-writer locks instead.

8.5 Deep recursion

The splay loop is iterative, but the BST descent (search/insert) can be recursive in some implementations and Python’s default recursion limit can be hit on deep chains. After splaying flattens the tree, the depth shrinks; on the first operation against a deep adversarial tree, however, the descent can hit O(n) Python frames. Use iterative descent in production.

8.6 Treating splay as a worst-case O(log n) structure

Don’t quote “splay tree is O(log n)” without “amortized.” The amortization is the entire point — losing the qualifier is misleading and a common interview-evaluation point.

8.7 Bad behavior under sequential scans on initial unsplayed trees

The sequential-access theorem gives O(n) total cost for in-order traversal via splay accesses, but a single sequential access into a chain of n nodes is O(n) for that one access. The O(n) total is amortized over all n keys. If your workload mixes a single rare scan with many point operations, the scan’s individual cost can spike — even though the amortized cost stays small.

8.8 Persistent splay trees are awkward

Path-copying for persistence requires modifying every node on the access path plus every node touched by splay. Each operation modifies O(log n) amortized nodes, but the splay disturbance affects nodes that an immutable balanced BST would not. Persistent splay trees exist but are rarely the right tool; persistent Treaps or AVL trees are more straightforward.

9. Diagram — The Three Splay Cases

flowchart TD
    subgraph "Zig (root case)"
        Z1["p (root)"] --> Z2[x]
        Z1 --> Z3[T3]
        Z2 --> Z4[T1]
        Z2 --> Z5[T2]
    end

What this diagram shows. The “zig” case applies only when x’s parent is the root. A single rotation pivots x to the root: p becomes x’s right child (or left, in the symmetric case), T2 becomes p’s left child (or right), and T3 is unchanged. This is the same as a single rotation in an AVL Tree — its presence in the splay procedure is just to handle the odd-length-path case at the very top of the splay sequence. Zig is the only case that does a single rotation; zig-zig and zig-zag both do two.

flowchart TD
    subgraph "Zig-Zig (same direction): rotate grandparent first"
        G1[g] --> P1[p]
        G1 --> T4a[T4]
        P1 --> X1[x]
        P1 --> T3a[T3]
        X1 --> T1a[T1]
        X1 --> T2a[T2]
    end

What this diagram shows (zig-zig). Both x → p and p → g are left-child relationships (or both right-child — symmetric). The splay step rotates g first (right rotation, bringing p up over g), then p (right rotation, bringing x up over p). The end result places x at the top with T1 to its left and a subtree containing p (and its child g) to its right — an arrangement where T1, T2, T3, T4 are now distributed across two subtrees of x rather than chained vertically. The “rotate grandparent first” order is what gives the amortized-O(log n) analysis; rotating parent first would degrade to Ω(n) per op on adversarial sequences.

flowchart TD
    subgraph "Zig-Zag (opposite): rotate parent first"
        G2[g] --> P2[p]
        G2 --> T4b[T4]
        P2 --> T1b[T1]
        P2 --> X2[x]
        X2 --> T2b[T2]
        X2 --> T3b[T3]
    end

What this diagram shows (zig-zag). x is on the opposite side of p from how p sits relative to g (e.g., x is p’s right child, p is g’s left child). The splay step rotates p first (left rotation, bringing x up over p), then g (right rotation, bringing x up over g). The result places x at the top with p and g symmetrically as left and right children — the most balanced of the three cases. Both zig-zag rotations contribute to the amortization equally; the order is “rotate child up first, then the now-empty grandparent down.”

10. Common Interview Problems

Source	Problem	Splay-tree connection
LC 4 (medians)	Find median of two sorted arrays	Order-stat tree (any balanced BST works; splay is candidate)
Generic	”Implement a self-organizing list”	Splay tree (binary form of self-organizing list)
Network algorithms	Min-cost flow with dynamic trees	Link-cut trees (splay-based)
Graph algorithms	Dynamic graph connectivity	Link-cut trees (splay-based)
Cache design	LRU-like cache with logarithmic operations	Splay tree of (key, value) — recently accessed sticks to top
Computational geometry	Sweepline event queue with priority changes	Splay augmented with priority info
Interview / textbook	”Prove O(log n) amortized for splay”	Sleator-Tarjan access lemma

For coding interviews, splay trees are almost never the expected solution — they are too implementation-heavy and the amortized-only bound is rarely needed. Where they shine in interviews is theory: amortized analysis, the potential method, the working-set theorem. Knowing what splay trees provide (O(log n) amortized + working-set + sequential-access + static-optimality) at a conceptual level is enough.

11. Open Questions

• Dynamic optimality conjecture. Are splay trees O(1)-competitive against the optimal offline BST for any access sequence? Open since 1985; best general bound is 2^{α(n)(1+o(1))} (Chalermsook et al., SODA 2024).
• Sub-O(log n) self-adjusting trees. The Tango tree of Demaine et al. (2004) gives O(log log n) competitiveness with explicit augmentation. Can the same be achieved without explicit info, like splay trees?
• Practical performance crossover. When does the constant-factor cost of splay’s many rotations outweigh the locality benefit? Empirically, splay outperforms RB on workloads with skew above ~80/20, but the precise threshold depends on the language/cache architecture.

12. See Also

• Binary Search Tree — the unbalanced ancestor; splay = BST + self-adjust
• AVL Tree — strict-balance alternative with worst-case (not amortized) O(log n)
• Red-Black Tree — looser-balance worst-case O(log n), what production code usually picks
• Treap — randomized alternative with expected O(log n), simpler still
• Tree Traversals — in-order traversal of any splay tree is sorted
• Binary Tree
• Skip List — randomized alternative with friendlier concurrency
• Hash Table — alternative when ordering is not needed
• Big-O Notation
• SWE Interview Preparation MOC