The idea: a search tree and a heap at the same time
A treap (tree + heap) is a binary search tree in which every node also gets a random number, its priority. The keys follow the BST order: everything in the left subtree is smaller, everything in the right subtree is larger. The priorities follow the heap order: a parent's priority is at least as high as its children's (a max-heap), so the highest priority is the root.
On the canvas each node shows its key on top and its priority below. A node's x position is its rank among the keys, so a rotation only moves nodes up and down. Priorities are 1 to 99 and kept distinct; "random" comes from a seeded generator (seed 1), so every run is the same.
Rotations keep the keys in order
A rotation swaps a node x with its parent p: x moves up, p moves down to x's other side, and the one subtree in between (B) changes parent. The in-order sequence A x B p C does not change, so the BST order still holds. That is why rotations are the tool for fixing the heap order.
Insert: a BST leaf, then rotate up
- Walk down by key as in a plain binary search tree and hang the new node as a leaf.
- Give it a random priority.
- While its priority is higher than its parent's, rotate it above the parent.
The new node stops as soon as its parent has a higher priority (Demo: insert 40 (priority 65), one rotation: 65 beats 37's 60 but not 25's 70). A very high priority climbs all the way to the root (Demo: insert 70 (priority 95), up to the root: three rotations).
Delete: rotate down, then cut the leaf
Find the node. While it has children, lift the child with the higher priority with a rotation: that child has to end up above its sibling anyway, so the heap order stays correct around it. The node sinks one level per rotation until it is a leaf, and then it is cut off (Demo: delete the root 50, rotate it down: four rotations, and 75 becomes the root).
Split and merge with a sentinel
split(k) cuts a treap into L (keys < k) and R (keys ≥ k). The trick: insert a sentinel with key k and priority ∞. It goes down as a leaf, then beats every priority and rotates up to the root. Now its left subtree is L and its right subtree is R; remove it (Demo: split at 45 with a sentinel).
merge(L, R), when every key of L is below every key of R, is the reverse: put a sentinel with priority −∞ on top, with L on its left and R on its right, rotate it down as in a delete, and cut it off (Demo: split at 45, then merge back: the merged treap is exactly the starting one). Both take time proportional to the depth, O(log n) expected. Many treap libraries write split and merge as short recursive functions instead, and build insert and delete from them: insert = split, then merge L, the new node and R.
Why the depth is O(log n)
For distinct priorities there is exactly one treap for a set of (key, priority) pairs: the highest priority must be the root, the keys smaller than it form the left subtree, and so on down. That tree is the same BST you would get by inserting the keys in order of decreasing priority. With random priorities that order is random, so the treap looks like a BST built from a random permutation: expected depth of a node about 2 ln n ≈ 1.39 log₂ n, whatever order the keys arrive in.
A plain BST fed sorted keys becomes a path of height n. A treap fed sorted keys stays shallow (Demo: sorted inserts 10 to 70, random priorities). An insert does on average fewer than 2 rotations, and a delete too.
Treap vs other balanced trees
| Treap | AVL / red-black | Skip list | |
|---|---|---|---|
| Bound | O(log n) expected | O(log n) worst case | O(log n) expected |
| Extra per node | one priority | height or colour | a tower of pointers |
| Rebalancing | rotations by priority, < 2 on average | rotations and recolouring by case | none, random heights |
| Split / merge | simple, O(log n) | possible but fiddly | simple |
Split and merge are why treaps are popular in practice: an implicit treap uses the subtree size instead of a stored key, so it can cut and join sequences by position (a rope), reverse ranges or answer range queries. See also splay trees, another self-adjusting BST built from rotations.
What the page leaves out
The page keeps at most 12 keys with integer priorities from 1 to 99 (real treaps use 32- or 64-bit random numbers, so ties practically never happen). It leaves out the recursive split and merge code, subtree sizes and implicit treaps, range queries and lazy updates, persistent treaps, union and intersection of two treaps, and the related Cartesian tree and zip tree.