Semicolony home
Search guides and simulators ⌘K
II · Trees, with shape

Treap

BST and heap, secretly the same tree.

1989 · Aragon & Seidel
The story

A treap (tree + heap) gives every node a random priority. The keys form a binary search tree; the priorities form a heap. Because priorities are random, the resulting tree shape mimics a random BST: depth O(log n) with high probability. Aragon and Seidel proved this; the construction is shockingly compact.

How it works

Insert: BST-insert by key, then rotate up while the priority is greater than the parent's. Delete: rotate down to a leaf, then remove. Split and merge by key fall out cleanly. The structure shines for "give me the order statistics of [a, b)" workloads.

Where it lives

Competitive programming (where the simplicity wins over AVL/RB). Some functional language libraries. Used as the underlying ordered map in some persistent data-structure libraries.

The key insight

Worst-case O(n) (if the random source is unlucky). The expected O(log n) bound holds across all inputs but the bound is over the random priority choice, not the input distribution.

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. Splay tree No metadata, and surprising amortised guarantees.
Across the cabinet
IV t-digest Quantiles, fairly accurate, fully streaming. 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.
← All data structures

Published