Link Operation

Make u a child of v (u must be a root, u and v in different trees).

Simple version (u must be a root):

function link(u, v)
    access(u)
    access(v)
    // u has no ancestors (it's a root)
    // Make v the parent of u
    u.pathParent := v

Flexible version (any nodes):

function link(u, v)
    makeRoot(u)  // Reroot u's tree at u
    access(v)
    u.left := v
    v.parent := u

The makeRoot operation (covered next) lets us link any two nodes by first making u a root. Time: $O(\log n)$ amortized.