Assume from now on that all the keys and priorities are distinct
Under this assumption, can prove by induction that the structure of a
treap is completely determined by the search keys and priorities of its
nodes.
Since it’s a heap, the node v with highest priority must be the root.
Since it’s also a binary search tree, any node u with key (u) < key(v )
must be in the left subtree, and any node w with key(w ) > key (v)
must be in the right subtree.
Finally, since the subtrees are treaps hemselves, by induction, their
structures are completely determined.
The base case is the trivial empty treap (or size 1 or 2 or 3. . . ).
Design of Algorithms. . . Part 3 2021/22 4 / 20
