Randomized Data Structures: Skip Lists, Treaps, Randomized BSTs
What This Concept Is
Randomized structures use internal choices to influence shape. A treap combines BST order on keys with heap order on independently sampled priorities. For distinct keys and priorities the two orderings determine a unique Cartesian-tree shape. Balanced behavior is expected over priorities, not guaranteed by the mere presence of a random-number generator.
Why It Matters Here
This complements the skip-list lesson with explicit two-order invariants and a careful adversary model. Randomness does not remove invariants or the need to test unfavorable shapes.
Concrete Examples
Take keys 1,2,3 and min-priorities 40,10,30. The minimum priority makes key 2 the root, with 1 and 3 as children. If instead priorities increase with the keys, the min-heap root is 1 and the tree is a right chain. Such a shape is possible under random sampling, even though independent continuous priorities give logarithmic expected search/update paths for fixed inputs.
split(T,k) can separate keys below k from keys at least k under a stated
convention. merge(A,B) requires every A key below every B key; it is not
a general union operation for overlapping key ranges. Copying only a search
path can combine this idea with persistence, but then shared nodes must remain immutable.
Finite priorities can tie; define an additional unique tie-breaker and analyze how sampling differs from the ideal distinct-priority model. A fixed seed supports reproducing a counterexample. It does not prove independence, resistance to an adaptive adversary, or a high-probability theorem.
Common Confusion / Misconceptions
Expected cost and high-probability bounds are different statements. A random insertion order for a plain BST is an input-distribution assumption, not an internal-randomization guarantee for sorted input. Deterministic balanced trees can support split/join too; treaps do not own those abstract operations.
How To Use It
State key/priority tie policies, RNG scope, independence assumptions and allowed adversary behavior. Test deterministic supplied-priority chains and mixed operations against an ordered oracle. Measure multiple independent seeds with operation counts and distributions. Keep treap/skip-list coding as bounded depth after the complete AVL map.
Check Yourself
What two invariants define a treap? Why does merge require separated key ranges? What does a reproducible seed establish and what does it not establish?
Mini Drill or Application
For keys 1,2,3 and min-priorities 10,20,30, draw the tree. Feedback: chain 1->2->3. Explain why a valid treap can still have linear height on one realization.
Read This Only If Stuck
Open Data Structures provides author-maintained randomized-tree material; use Skiena for comparisons of ordered operations.