Treap
A randomised BST: every node gets a random priority alongside its key. Keeping the tree heap-ordered by priority (via rotations) makes it balanced in expectation, without any deterministic rebalancing rules.
A treap node stores both a key and a randomly assigned priority. The tree must satisfy two invariants simultaneously: BST order on the keys, and max-heap order on the priorities (every parent's priority ≥ its children's). These two orderings together pin down a unique tree shape for any given key/priority set.
Insertion is a normal BST insert followed by rotations that bubble the new node up until its priority satisfies the heap property — exactly the rotation mechanics of an AVL tree, but triggered by random priorities instead of a computed balance factor.
Because priorities are random, the resulting tree shape is equivalent in distribution to a random BST — expected O(log n) height with high probability, and none of the fixed rotation-case logic that AVL/red-black trees need. The simplicity is the appeal: balance "for free" from randomness, at the cost of a (very small) probability of an unlucky, unbalanced draw.
Operations
| Operation | Complexity |
|---|---|
| search | O(log n) expected |
| insert (+ priority rotations) | O(log n) expected |
| delete | O(log n) expected |
| split / merge (by key) | O(log n) expected |
Where it's used
Randomised balanced-tree implementations where simplicity matters, ordered-set operations needing fast split/merge (competitive programming, functional data structures).