A treap of 24 keys, sorted insertion, seed 20260810

A treap of 24 keys, sorted insertion, seed 20260810

Horizontal position is the key; vertical position is the random priority the key was given on arrival, highest at the top. The search-tree property is that no edge crosses another; the heap property is that no edge goes upward. This tree is 8 deep against an ideal of 4, it took 20 rotations to build, and the insertion order was sorted — which for an ordinary binary search tree would be the difference between a tree and a list.

Drawn at 700 × 360, wide on the page. Everything above is what treap-shape returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

1 essay calls treap-shape. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.