A treap assigns each key a random priority and keeps a heap order on priorities. Derive its expected depth, explain why no rebalancing rules are needed, and compare it with a skip list on memory and on worst case behaviour.

A treap assigns each key a random priority and keeps a heap order on priorities. Derive its expected depth, explain why no rebalancing rules are needed, and compare it with a skip list on memory and on worst case behaviour.

Approach: A treap on random priorities has exactly the shape of a binary search tree built by inserting the keys in priority order, so reuse the random binary search tree depth calculation.

Expected depth 2 ln n, about 1.39 log_2 n. The shape of a treap depends only on the relative order of the random priorities, and it is identical to the binary search tree obtained by inserting keys in decreasing priority order, so it is a randomised binary search tree over a uniformly random insertion order. Key j is an ancestor of key i exactly when j has the highest priority among the keys between them inclusive, which has probability 1/(|i - j| + 1), and summing that over j gives the expected depth 2 ln n plus O(1). The randomness comes from the priorities and never from the input, so an adversary who chooses the keys cannot force a bad tree and no rebalancing rules are needed. Insertion places the node as a leaf and rotates it up while its priority beats its parent, which is O(1) expected rotations. A skip list gives the same expected O(log n) with simpler code and easier concurrent updates, at roughly two pointers per node against three fields for a treap, and both share the same worst case of Theta(n), which is exponentially unlikely rather than adversarially reachable.

Follow-up: How would you split and join a treap at a key in expected O(log n) and what does that give you that a red-black tree does not?

Key concepts: random priority, expected depth, randomised binary search tree, skip list.