function insert(node: Node | null, key: number): Node { if (node === null) return { key, priority: Math.random(), left: null, right: null }; if (key < node.key) {node.left = insert(node.left, key);
if (node.left.priority > node.priority) return rotateRight(node);
} else {node.right = insert(node.right, key);
if (node.right.priority > node.priority) return rotateLeft(node);
}
return node;
}
The treap is empty: 24 with random priority 45 becomes the root.
Understanding Treap
The idea
A treap gives every node a key and a random priority and keeps two rules at once: the keys form a binary search tree and the priorities form a max-heap. Together they pin the shape down completely: the treap is exactly the BST you would get by inserting the keys in decreasing priority order.
Since the priorities are random, that insertion order is random, and a random-order BST has expected height O(log n) whatever order the keys really arrived in. Insertion is a BST insert followed by rotations up while the new node's priority beats its parent's, with no heights or colours to maintain.
The four stages
Complexity
Versus its siblings
Pseudocode
INSERT(node, key)
if node is null: return a new node with key and a random priority
insert into the left or right subtree by key, as in a BST
if that child's priority is now larger than node's: rotate it up (right rotation for the left child, left for the right)
return the root of this subtree
When to use
Pitfalls
History
Cecilia Aragon and Raimund Seidel introduced treaps in 1989 as randomized search trees, with the observation that a random priority is all the balance information a tree needs. Jean Vuillemin's Cartesian trees from 1980 are the same structure with priorities given by position rather than chance.