FindRoot Operation

Find the root of the tree containing v:

function findRoot(v)
    access(v)
    // Root is leftmost node in auxiliary tree
    while v.left is not null
        v := v.left
    splay(v)
    return v

After access(v), the path from v to root is in one auxiliary tree. The root is the leftmost node (shallowest depth).

Time: $O(\log n)$ amortized.

This replaces Union-Find's find operation but with more power.