priority generation in treap data structure

Question

I'm studying the treap data structure. When inserting node, treap radomly generate node's priority. But what if 69 node's generated priority is 13 in the picture above?

Parent's priority must higher than child's priority. Do treap's binary tree attribute collide with heap attribute?

I want to know. Thanks.

Answer 1

Assuming you have treap from your picture without 69 node and want to add (69, 13) node:
1. Split existing treap to 2 treaps L and R by key 69 (here all old treap will be L)
2. Create treap M with single node (69, 13)
3. Merge M with L, then result with R
For this case node (69, 13) becomes a new root, and old treap will be it's left child.

Answer 2

If node 69 had priority 13, then it would be the root of the tree and node 31 would be its left child. The descendants of node 31 would be as in your diagram, except of course for node 69.

It's always possible to arrange a treap so that it respects both the heap and the binary search properties. In fact, in the absence of equal values or equal priorities, there is only one possible arrangement.

The random assignment of priorities makes it likely that the treap will be reasonably balanced. It might not be perfectly balanced, but on the positive side building the treap is fast and uncomplicated.