Persistent Treap Operations

Split by key (create new nodes for the split path):

function split(root, key)
    if root is null then
        return (null, null)

    newRoot := copy(root)
    if key < root.key then
        (left, right) := split(root.left, key)
        newRoot.left := right
        return (left, newRoot)
    else
        (left, right) := split(root.right, key)
        newRoot.right := left
        return (newRoot, right)

Merge (also creates new nodes):

function merge(left, right)
    if left is null then return right
    if right is null then return left

    if left.priority > right.priority then
        newNode := copy(left)
        newNode.right := merge(left.right, right)
        return newNode
    else
        newNode := copy(right)
        newNode.left := merge(left, right.left)
        return newNode

Time: $O(\log n)$. Space: $O(\log n)$ new nodes per operation.