Treap Operations - Split

Split divides a treap into two treaps: one with keys $< x$, one with keys $\geq x$.

function split(node, x)
    if node is null then
        return (null, null)

    if node.key < x then
        (left, right) := split(node.right, x)
        node.right := left
        return (node, right)
    else
        (left, right) := split(node.left, x)
        node.left := right
        return (left, node)

Time: $O(\log n)$ expected. The recursion follows a path from root to leaf, and expected path length is $O(\log n)$.