Random BST: Treap

• Each entry (key-value pair) is assigned a random priority.
• The BST ordering property is based on keys.
• The priorities are used to create a (min or max) heap, though just the partialy ordered tree property, not the complete tree property.

Insertion

• Generate random priority for the entry (key-value pair).
• Insert the entry as you would in BST (based on the "key" and ignoring priorities)
• If priorities (inserted node and its parent) are not in the desired order (based on whether we maintain a max- or min-heap), rotate node up and parent down (instead of swim-up).
• Repeat the last step until inserted node and parent priorities are in the desired order or the new node becomes the root.

Removal

• Find the target following a "lookup" in BST (on keys, ignoring priorities).
• Change the priority of the entry to be removed to a value that results in the entry sinking. For example, if the priorities are non-negative, set the target's priority to $-1$.
• Rotate down the target until it cannot sink any further (it becomes a leaf), then remove it.