1

Regarding disjoint-set data structures, what is the point of doing union by rank? I get the purpose of "weighted union" when implementing the data structures as linked lists (less objects to update per union).

However, when union by rank is related to tree implementation. Here, you update the parents of roots when uniting two trees. So if x and y were trees and you called union(x,y), the parent of the root of the tree containing x would be linked to the root of the tree containing y. This takes constant time - so what is there to optimize? Like why would union by rank give any better results if you only have to update a pointer?

  • "This takes constant time" - no it doesn't. You have to find the roots first, and that can take a while if you're not using union by rank to manage tree depth. – user2357112 Mar 06 '20 at 23:51
  • But isn't that what path compression is for? That you make the parent of each node point directly to the root? Then from thereon, it would take constant time –  Mar 06 '20 at 23:56
  • Or wait - so is union by rank made for the FIND-SET operation to be more optimized and not the UNION operation? –  Mar 06 '20 at 23:57
  • Path compression helps, but not as much as path compression and union by rank combined. (Also, the roots don't stay constant, because union operations change the roots.) – user2357112 Mar 07 '20 at 00:05
  • @user2357112supportsMonica thanks! So just to be clear: union by rank is really an optimization for FIND-SET operations and not the UNION operations themselves? –  Mar 07 '20 at 00:34

0 Answers0