Search tools and guides ⌘K
II · Trees, with shape

Splay tree

No metadata — and surprising amortised guarantees.

1985 · Sleator & Tarjan
The story

A splay tree carries no balance metadata at all. Every operation rotates the accessed node to the root via a sequence of "splay" steps. Sleator and Tarjan proved that any sequence of m operations on a tree of size n takes O((m + n) log n): same amortised bound as red-black, with much simpler code.

How it works

Search, insert, and delete each splay the touched node to the root. The splay operation uses three rotation patterns (zig, zig-zig, zig-zag). Cache locality is excellent because frequently-accessed nodes drift toward the root, and the tree adapts to skewed access patterns automatically.

Where it lives

Compilers (symbol tables for variable lookups in long-lived sessions). Some kernel structures. Linux's VFS dentry cache uses a splay-tree-like adaptive structure.

The key insight

Worst-case single operation can be O(n). Don't use splay trees in latency-bounded contexts; use them when access patterns are skewed and amortised cost is what matters.

More in Trees, with shape
Binary search tree Sorted, but with shortcuts. AVL tree Always height-balanced, to within one. Red-black tree Almost balanced, much faster to maintain. B-tree / B+ tree The shape of a database index. Heap (binary heap) A priority queue you can grep. Skip list Probabilistic balance, beautifully. Trie (prefix tree) A tree you walk one character at a time. Segment tree Range queries in logarithmic time. Fenwick tree (BIT) Prefix sums, with constant tweaks. Treap BST and heap, secretly the same tree.
Across the cabinet
V Suffix array All suffixes, sorted. V Suffix tree Every substring, in linear space. V Rope A tree of small strings. V Piece table Edit a file without copying it. V Gap buffer A buffer with a hole at the cursor. VI Adjacency list Each node, its neighbours. VI Disjoint Set / Union-Find Track connected components, in a forest. VI Merkle tree Hash of hashes; tamper-evident.
← All data structures