A plain binary search tree can degrade to a O(n) chain if keys arrive in sorted order. Balanced trees like AVL and red-black fix this with intricate rebalancing rules. A treap takes a wonderfully lazy shortcut: give every node a random priority and require the tree to be a heap on those priorities as well as a BST on the keys (hence tree + heap = “treap”). Because the shape is now determined by the random priorities — not by the order keys were inserted — the tree is balanced in expectation, with height O(log n), using only simple rotations. Insert keys and watch random priorities rotate the tree into balance.
O(log n) expected height · BST on keys + max-heap on random priorities · rotations only
BST property
Keys obey binary-search order: left subtree < node < right subtree.
heap property
Priorities obey a max-heap: every node’s priority ≥ its children’s.
random priority
Each node gets a random priority on insertion — this decides the shape.
rotation
A local restructuring that fixes the heap property while preserving BST order.
treap.js — keys ordered, priorities heaped
Ready
Each node shows its key (top) and random priority (bottom). The tree is a BST on keys and a max-heap on priorities. Inserting a key places it by BST order, then rotates it up while its priority beats its parent’s. Insert to build.
0
nodes
0
height
–
last rotations
How it works
The trick is that a treap’s shape is uniquely determined by its set of (key, priority) pairs, regardless of insertion order — the BST-on-keys and heap-on-priorities constraints together leave exactly one valid tree. So if the priorities are random, the tree you get is the same as if you had inserted the keys in a random order, which is known to produce an expected height of O(log n). Insertion is simple: place the new key as a normal BST leaf, then, while it has a higher priority than its parent, rotate it upward — each rotation preserves the BST order but lifts the high-priority node toward the root, restoring the heap property. Deletion is the mirror: rotate the node down until it’s a leaf, then snip it.
1
Give each node a random priority
On insertion, assign the new key a random priority. The tree must satisfy BST order on keys and max-heap order on priorities simultaneously.
2
Insert as a BST leaf
Descend by key comparisons and attach the new node as a leaf, exactly as in an ordinary BST. This keeps the BST property but may violate the heap property.
3
Rotate up to fix the heap
While the new node’s priority exceeds its parent’s, rotate it up. Each rotation is a local restructuring that preserves BST order while moving the higher priority toward the root.
✓
Balanced in expectation
Because random priorities make the shape equivalent to random-order insertion, the expected height is O(log n). No AVL/red-black-style rules are needed — just rotations driven by priorities.
Height
O(log n) expected
Insert / delete
O(log n)
Rebalance
rotations only
Also called
randomized BST
The code
# treap insertion: BST on key, max-heap on random priorityimport random
def insert(t, key):
if t isNone: return Node(key, priority=random.random())
if key < t.key:
t.left = insert(t.left, key)
if t.left.priority > t.priority: # heap violated
t = rotate_right(t) # lift the child upelse:
t.right = insert(t.right, key)
if t.right.priority > t.priority:
t = rotate_left(t)
return t # rotations preserve BST order, fix the heap
Quick check
1. What two structures is a treap at the same time?
A treap is a "tree + heap": it maintains BST order on the keys and max-heap order on each node’s randomly assigned priority, both at once.
2. Why does a treap stay balanced without complex rebalancing rules?
The (key, priority) pairs determine a unique tree regardless of insertion order. Random priorities make that shape equivalent to random-order insertion, which has O(log n) expected height — no AVL/red-black rules needed.
3. How is the heap property restored after inserting a key?
The new node is placed as a BST leaf, then rotated upward as long as its priority beats its parent’s. Rotations are local restructurings that preserve BST order while lifting the higher priority toward the root.
FAQ
What is a treap?
A randomized balanced BST that is at once a binary search tree on its keys and a max-heap on a random priority per node. Since its shape comes from the random priorities, not insertion order, it has O(log n) expected height and supports insert/delete/search in O(log n) expected time with only simple rotations.
How does a treap compare to AVL and red-black trees?
AVL and red-black trees guarantee worst-case O(log n) height via strict rules (more complex code). A treap only guarantees O(log n) in expectation, but it’s far simpler and supports split/merge easily — a popular choice when simplicity and those operations matter more than a worst-case bound.
What are split and merge on a treap?
Split divides a treap into two by a key (smaller keys in one, rest in the other); merge combines two treaps (all keys in one < all in the other) into one. Both are O(log n), and they make implicit-key treaps behave like arrays with fast range insert/erase/reverse.
What happens if two nodes get the same priority?
Priority ties can blur the unique shape and slightly hurt balance, but with wide-range random priorities (32–64 bits) collisions are negligible; implementations either rely on that or break ties deterministically. In practice it’s a non-issue.
SOLVE IT YOURSELF
Solve it: balance a BST with random priorities
A treap is two structures in one node: a BST on the key, a heap on a random priority. Keep both invariants and the shape is whatever a random insertion order would have produced — balanced, with no balance factors or colours to track. Python or TypeScript.
YOUR TASK
Implement Treap with insert(key), search(key), delete(key), inorder() and height(). Priorities come from the supplied seeded generator. Duplicate inserts are ignored.
HINTS — 7 IDEAS
Insert like a plain BST first — walk down on key comparisons and hang the new node off a leaf.
That leaf placement can violate the heap: the new node may outrank its parent. Fix it by rotating it up, once per level, on the way back out of the recursion.
A right rotation at n makes n.left the new subtree root and n its right child. Keys stay ordered because you only ever move a subtree that was already on the correct side.
Delete is the mirror image: rotate the doomed node down, always promoting the higher-priority child, until it has at most one child — then splice it out.
Rotating toward the higher-priority child is what keeps the heap intact during deletion. Promoting the lower one would break it immediately.
The priorities are random, so the tree's shape is the shape of a random BST: expected height about 3·log₂ n, no rebalancing rules required.
Same seed means same tree every run — that is the only reason a randomized structure can be unit-tested at all.