1
$\begingroup$

I just learned about using UF with union by rank and path compression. A path can be compressed via attaching a node to its root after Find is called on the node. If the goal here is to flatten the tree, why not just implement the tree such that each node is directly attached to its root (instead of its true parent)? That way, maximum compression would be achieved from the start. What is the con of this as long as union by rank is used along with it?

$\endgroup$

1 Answer 1

3
$\begingroup$

Because then a Union operation would be very slow: when you Union two trees, you would have to reparent all of the nodes in one of the trees.

$\endgroup$
3
  • $\begingroup$ Doesn't unioning by rank solve this though? Because you're only reparenting the smaller of the two, the total work should be less than without using rank. Although perhaps not asymptotically. $\endgroup$
    – marshacker
    Jan 12, 2020 at 23:21
  • 1
    $\begingroup$ Suppose you did as you proposed, and reparent everything to the root node. Exercise: Describe an algorithm to do it. Find a sequence of union operations that would give worst-case time, and find the amortised time per operation using this algorithm. If you get stuck, feel free to ask in this very question. You'll learn a lot doing this. $\endgroup$
    – Pseudonym
    Jan 12, 2020 at 23:44
  • $\begingroup$ Thanks for the advice. Does it end up being O(N) am. per operation? $\endgroup$
    – marshacker
    Jan 25, 2020 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.