← Back to the red black trees page
Treap (Tree + Heap)
Each node gets a random priority; BST order by key, heap order by priority. Randomness does the balancing with no case analysis.
What to know
- Equivalent to a BST built by inserting keys in random order — expected height O(log n).
- split(key) and merge(a, b) make ordered-set union/insertion elegant.
- Far simpler to code correctly under pressure than red-black deletion.
In the wild: Competitive programming workhorse, versioned buffers, randomized indexes.
Algorithms to reach for
Split / merge
O(log n) expectedCompose all ordered-set ops from two primitives
Implicit treap
O(log n) expectedArray with O(log n) insert/delete/reverse anywhere