Treap Insert and Delete

Insert and delete are built from split and merge:

Insert key k:

(left, right) := split(root, k)
newNode := createNode(k, randomPriority())
root := merge(merge(left, newNode), right)

Delete key k:

(left, mid) := split(root, k)
(toDelete, right) := split(mid, k + 1)
root := merge(left, right)

Both operations are $O(\log n)$ expected. The simplicity of split/merge makes treaps easy to implement correctly.