Nothing special here. It’s just a blog post for summarising my algorithm learning course.

Weighted Quick Union

  • Use Quick Union but avoid tall tree, to avoid traversing through very long path
  • Use an extra array to track the size of each tree (stored in the root node)
  • Link the smaller tree to the root of the larger tree
  • The size of the new tree is the total size of both tree

Method Complexity  
isConnected(p, q) O(lgN) Depth of any node x is at most lgN
union(p, q) O(lgN)  

lg = base-2 logarithm

Quick Union with Path Compression

  • Use Quick Union but try to flatten the tree
  • Every time we compute the root of one item (by traversing through the path to the root), set that item to point directly to the root.
  • Next time when we call the function to find the root of that same item, we don’t have to traverse through the full path again

For path compression, if the root is called many times enough, the complexity will become O(1) when the tree become flatten.