Splay Tree
AVL and red-black trees store balance information and repair the shape after every change. A splay tree stores nothing and repairs the shape by using it: every access finishes by rotating the accessed node to the root, two levels at a time, zig-zig when node and parent lean the same way, zig-zag when they lean opposite ways. That halves the depth of everything on the path, so a bad shape fixes itself as it is used. No single access is guaranteed fast, but any sequence of m accesses costs O(m log n) in total, and keys used recently sit near the top, which makes a splay tree a search tree and a cache at once.
Access 70 in this splay tree, a plain binary search tree of 7 nodes, height 7, with no balance information stored anywhere. A normal search finds it; then the node is splayed: rotated up two levels at a time until it is the root. The tree is reshaped by every access, and that reshaping is what keeps it fast on average.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.
70 is a right child of 60, which is a right child of 50. Which splay step?
Answer: Zig-zig: same side as the parent, rotate the grandparent then the parent. No grandparent means zig; same side means zig-zig, rotating the grandparent first; opposite sides means zig-zag, rotating x twice.
70 is a right child of 40, which is a right child of 30. Which splay step?
Answer: Zig-zig: same side as the parent, rotate the grandparent then the parent. No grandparent means zig; same side means zig-zig, rotating the grandparent first; opposite sides means zig-zag, rotating x twice.
70 is a right child of 20, which is a right child of 10. Which splay step?
Answer: Zig-zig: same side as the parent, rotate the grandparent then the parent. No grandparent means zig; same side means zig-zig, rotating the grandparent first; opposite sides means zig-zag, rotating x twice.
How it runs, step by step
Access 70 in this splay tree, a plain binary search tree of 7 nodes, height 7, with no balance information stored anywhere. A normal search finds it; then the node is splayed: rotated up two levels at a time until it is the root. The tree is reshaped by every access, and that reshaping is what keeps it fast on average.
Access 70 in a splay tree of 7 nodes.
Search finds 70 at depth 6, along 10, 20, 30, 40, 50, 60, 70. Now splay it to the root.
Found 70 at depth 6.
70 is the right child of 60, which is the right child of 50: the same side. Zig-zig: rotate 60 over 50 first, then 70 over 60.
Zig-zig at 70.
70 is now at depth 4; two rotations moved it up two levels, and the nodes it passed dropped closer to the middle of the tree. Zig-zig rotating the grandparent first is what makes the difference from naive rotate-to-root: it halves the depth of the whole path instead of leaving it long.
70 at depth 4.
70 is the right child of 40, which is the right child of 30: the same side. Zig-zig: rotate 40 over 30 first, then 70 over 40.
Zig-zig at 70.
70 is now at depth 2; two rotations moved it up two levels, and the nodes it passed dropped closer to the middle of the tree. Zig-zig rotating the grandparent first is what makes the difference from naive rotate-to-root: it halves the depth of the whole path instead of leaving it long.
70 at depth 2.
70 is the right child of 20, which is the right child of 10: the same side. Zig-zig: rotate 20 over 10 first, then 70 over 20.
Zig-zig at 70.
70 is now at depth 0, the root. Zig-zig rotating the grandparent first is what makes the difference from naive rotate-to-root: it halves the depth of the whole path instead of leaving it long.
70 at depth 0.
70 sits at the root after 6 rotations; the height went from 7 to 5. No single access is guaranteed to be fast, but the potential argument shows any m accesses cost O(m log n) in total, and keys used recently stay near the top: a splay tree is a search tree and a cache at once, with a node that stores nothing but its key.
70 is the root; height 5.
Remember
- Every access ends by splaying the node to the root; even a miss splays the last node reached.
- Zig-zig rotates the grandparent first, zig-zag rotates the node twice; that choice halves the path depth.
- No balance information, no worst-case guarantee per access, O(log n) amortized over any sequence.
Topics covered
Where this is used
CompilersThe OpenMP offload memory map in GCC
libgomp, the runtime behind #pragma omp target, gives every device a splay tree that maps host address ranges to device addresses: the key is the pair host_start and host_end, so a lookup is really an interval query. An offload loop maps the same few arrays on every iteration, so those keys stay splayed near the root and the repeated lookups finish in a comparison or two. GCC's copy of the structure stores the mapping data directly inside the node, with no colour or height field to keep up to date.
NetworkingSquid dstdomain ACL matching
Squid keeps the domain list of a dstdomain ACL as a Splay of strings and matches every request against it with a comparator that understands subdomain wildcards. Proxy traffic is heavily skewed - a handful of domains account for most requests - so those entries float to the top and the usual check costs a couple of comparisons however long the list is, without anyone having to say in advance which domains are hot.
Operating systemsWindows kernel generic tables
The Rtl generic table routines that file system drivers use for per-file bookkeeping are splay trees by default, and each element is one allocation that holds the tree links and a list entry in front of a copy of the caller's data. Driver lookups repeat heavily, since the same files are opened again and again, so splaying keeps the working set shallow with no balance metadata to store. Microsoft's own documentation warns that some operation orders leave the tree near a straight line and offers an AVL implementation of the identical API behind RTL_USE_AVL_TABLES.
AlgorithmsLink-cut trees
A link-cut tree represents a changing forest as a set of paths, each path held in a splay tree ordered by depth, and the expose operation that answers a query is a sequence of splays that relinks those paths. Amortization is doing the real work here: single splays can be long, but the restructuring they leave behind pays for the next ones, which is how dynamic connectivity and the Sleator-Tarjan max-flow implementations get O(log n) per update. A tree with a fixed balance rule cannot be cut and joined this cheaply.
Why it works this way
Why rotate two levels at a time instead of just walking the node up?
Rotating the node with its parent over and over also lands it at the root, and it is the obvious implementation, but that version - move to root - has no amortized bound: run it on a tree that is already a long path and the path comes back nearly as long, so accesses keep costing O(n). The zig-zig case rotates the grandparent first, which folds the path in half instead of merely re-hanging it, and every node that was on the path ends up at roughly half its old depth.
A lookup is a write
Every access rewrites pointers, so there is no read-only path through a splay tree: two threads cannot search it at the same time without an exclusive lock, and a find cannot be const in the ordinary sense. Squid's SplayNode declares its left and right pointers mutable for exactly this reason, and the Windows generic table API ships a separate enumerate-without-splaying routine so that walking a table does not reshape it. On a read-mostly structure shared between cores, the dirtied cache lines can cost more than the shorter paths win, which is when a red-black tree or a skip list is the better answer.
Amortized means one access really can cost O(n)
Insert 1, 2, 3 up to n in order: each insert splays the new largest key to the root, so the tree ends as one long left-leaning chain, and a search for 1 touches every node. That is not a hole in the analysis - that one slow search halves the depth of everything it passed, so the cost is repaid by the accesses that follow - but it does mean a splay tree cannot sit in a path with a per-operation latency budget, and that keys arriving in an order someone else controls are a real risk.
Delete needs a join, not a rotation
No rotation removes a node, so deletion is two moves: splay the key to the root and drop it, which leaves a left subtree and a right subtree with no parent, then splay the largest key of the left subtree to its own root. That node cannot have a right child, since nothing in the left subtree is larger than it, so the right subtree hangs straight off the empty slot. The case worth writing a test for is an empty left subtree, where the right subtree simply becomes the whole tree.
Read more
- Splay treeWikipedia
- Self-adjusting binary search treesSleator and Tarjan, JACM 1985 · cs.cmu.edu
- Top-down splay trees in C, the version used in practiceSleator, CMU · link.cs.cmu.edu
- Splay tree visualisedUSF
- splay-tree.h, the offload memory map in libgompGCC · github.com