Union Find

Question 1

Union Find

Answer 1

• Also known as disjoint set
• Data structure that keeps track of elements organized into non-overlapping subsets (disjoint sets)
• Three operations
  
  • Find
  • Make-set
  • Union
• Three Implementations
  
  • Naive
  • Union by Rank
    
    • Uses a different version of union
  • Path Compression
    
    • Uses a different version of find
• Can be implemented with nodes and pointers (like a tree), or dictionary (or parent and rank)
• Union by Rank and Path Compression are usually used at the same time
• Data structure is particularly useful for Kruskal’s algorithm

Question 2

Union Find

Make Set

Answer 2

• A basic operation of union find
• Creates a set with one element
• Operation makes the element its own parent
• Element becomes the root of a new tree

Steps

1. x.parent = x

Question 3

Union Find

Find

Answer 3

• Basic operaiton of union find
• Identifies the set that an item x belongs to
• Basically, recursively searches for root of tree containing x
• Recall that, in general, we use one element from the set to represent that set

Steps

1. If you’re at the root (if x.parent == x)
2. Return root
3. Otherwise, find root
4. Run find on x.parent
5. And return that

Question 4

Union Find

Union

Answer 4

• A basic operation of union find
• Combines two sets within data structure together
• Basic verison of union can cause tree to be unbalanced

Steps

1. For union of x and y
2. Use Find to find root of x’s tree
3. Use Find to find root of y’s treet
4. Make rootX the parent of rootY

Question 5

Union Find

Union By Rank

Answer 5

* Modification of union operation of union find

• Choose the new representative to be the rep of the larger set
• Requires you to keep track of rank in make-set operation
• Rank is essentially height of tree

Steps

1. For union of x and y
2. Use Find to find root of x’s tree
3. Use Find to find root of y’s tree
4. Make root with larger rank parent of the other root
5. If ranks are equal
6. Arbitrarily choose which root to make parent
7. And increment rank of that root

Question 6

Union Find

Path Compression

Answer 6

• Implementation of Union Find that uses a modified Find operation
• Normal find operation simply returns root of x’s tree
• Variation of find returns root of x’s tree, and updates each node in recursive chain to point directly to root

Steps

1. If you’re at the root (if x.parent == x)
2. Return root
3. Otherwise, set x.parent => what root ends up being
4. x.parent = find(x.parent)
5. And then return x.parent (which is now the root)