Splay Trees: The Self-Adjusting Binary Search Tree

What Makes a Splay Tree Self-Adjusting

A regular binary search tree is a passive structure: it stores values in order, but nothing about a lookup changes its shape. A splay tree is different because every single access, whether it is a search, an insertion, or a deletion, triggers a restructuring step called splaying. After the target node is located, the tree performs a sequence of rotations that walks that exact node up through its ancestors until it becomes the new root. This means the tree's shape is a living record of recent activity rather than a fixed arrangement chosen once at build time. No extra balance information, like the height or color labels used by other self-balancing trees, needs to be stored on each node. Instead, the structure itself does all the work through rotations applied during the walk back to the top. The rotations preserve the binary search tree ordering property at every step, so the tree remains fully valid and searchable throughout the process. The practical effect is that the tree constantly reshapes itself to favor whatever has been touched most recently, which turns out to be a remarkably good heuristic for real workloads where some data is accessed far more often than the rest. Splay trees were introduced by Daniel Sleator and Robert Tarjan, and their charm lies in this simplicity: a handful of rotation rules, applied consistently, produce a structure that adapts on its own without any separate rebalancing pass.

The Zig Case: A Single Rotation Near the Root

The simplest of the three splaying patterns is the zig case, and it only ever happens once per splay operation, right at the very end of the walk. It applies when the node being splayed has the root of the tree as its direct parent, meaning there is no grandparent to worry about. In this situation the tree performs a single rotation: if the node is a left child, the tree rotates right around the parent; if the node is a right child, it rotates left around the parent. This one move swaps the node and its parent, placing the node at the root while the old root slides down to become its child, and the subtree that used to hang between them is reattached in the correct spot to preserve ordering. Because a zig only occurs when the node is one step away from the root, it acts as the finishing touch of a longer splay sequence that may have already worked through several zig-zig or zig-zag steps deeper in the tree. Some splay operations consist of nothing but a single zig, which happens whenever the accessed node happened to be a direct child of the root to begin with. Even though it is the least dramatic of the three cases, the zig is essential for correctness, since without it a node one level below the root would have no way to complete its journey all the way to the top.

The Zig-Zig Case: Straight-Line Rotations

The zig-zig case handles the situation where a node and its parent lean the same direction, meaning both are left children of their respective parents, or both are right children. Rather than rotating the node directly around its parent first, zig-zig rotates the parent around the grandparent first, and only then rotates the node around its now-repositioned parent, with both rotations turning in the same direction. This order matters a great deal. Rotating the more distant pair before the closer pair is what gives splay trees their good long-term behavior, because it tends to roughly halve the depth of the nodes along the access path rather than simply shifting the problem down one level, which is what would happen if the rotations were done in the naive top-down order. Picture a long chain of left children stretching down the left side of the tree: a zig-zig splay works through that chain two levels at a time, each pair of rotations collapsing part of the chain and spreading the remaining nodes out into a shallower, bushier shape. This is the workhorse case for deeply nested nodes, since most real access paths are not a strict zig-zag alternation but contain runs of same-direction steps, and zig-zig is what keeps those runs from causing worst-case chains to persist across repeated operations.

The Zig-Zag Case: Opposite-Direction Rotations

The zig-zag case covers the other possibility, where the node and its parent lean in opposite directions, such as the node being a left child while its parent is a right child, or vice versa. Here the tree still performs two rotations, but they turn in different directions rather than the same one. The first rotation brings the node up around its immediate parent, and the second rotation then brings that same node up around the grandparent, effectively lifting the node two levels while the parent and grandparent become its two children, one on each side. Visually, this is similar to the double rotation used to fix an imbalance in an AVL tree, and it produces a similar flattening effect: instead of a bent, staircase-like path, the zig-zag straightens the local structure so the node's former parent and grandparent end up as siblings underneath it. Splaying a node typically involves working through a mixture of zig-zig and zig-zag pairs as the path zigzags or runs straight at different points, with a final zig applied only if one extra level remains once the node reaches the root's immediate child. Together, these two double-rotation cases are what let a single splay operation collapse an arbitrarily long access path down to the root in one pass.

Why This Gives Good Amortized Performance

A single splay operation on an unlucky, badly shaped tree can still walk down a long path before it finds its target, so any one access is not guaranteed to be fast. What makes splay trees valuable is not the speed of any individual operation but their behavior on average over many operations. Because every access moves the touched node to the root, a node that gets visited repeatedly becomes cheap to reach again almost immediately after its first, possibly expensive, visit. Sequences of operations that repeatedly touch the same small set of hot items get dramatically faster over time, since those items cluster near the top of the tree, while cold items are pushed toward the bottom where they rarely interfere. Mathematical analysis of splay trees shows that even though isolated operations can be costly, the total cost summed across any long sequence of operations stays proportional to what a well-balanced tree would achieve, so the expensive cases are effectively paid for by the many cheap ones that follow. This self-adjusting behavior is what makes splay trees genuinely useful outside the classroom. Certain cache implementations use splay-tree-like structures because recently and frequently used entries naturally rise to where they can be found fastest. Some network routers have used them to manage routing information where a subset of destinations dominates traffic. Data compression algorithms, including some adaptive coding schemes, also borrow the same idea, since they benefit from cheap repeated access to symbols that occur often in the input stream.

Frequently asked questions

Try it live

Everything above runs in your browser — open Splay Trees: The Self-Adjusting Binary Search Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.