§ Disjoint set union
§ intuition for correctness of rank
:
Assume that we had to re-point pointers of all our children to the
new root when we decide to make another node the root. That is,
we would have:
void mkroot(int newroot, int prevroot) {
for (int child : children[prevroot] {
parent[child] = newroot;
}
parent[prevroot] = newroot];
children[prevroot] = {}; // this has no children anymore
}
- In this setting, we ought to make the smaller subtree the
prevroot
and the larger subtree the newroot
: It is better to loop over fewer children.
- When we perform the
rank
based union, we are using the same heuristic , even though we don't actually loop over all our children.