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: amortized.