Union Find Flashcards

1
Q

Union Find

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Union Find

Make Set

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Union Find

Find

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Union Find

Union

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Union Find

Union By Rank

A

* 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Union Find

Path Compression

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly