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
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
- x.parent = x
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
- If you’re at the root (if x.parent == x)
- Return root
- Otherwise, find root
- Run find on x.parent
- And return that
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
- For union of x and y
- Use Find to find root of x’s tree
- Use Find to find root of y’s treet
- Make rootX the parent of rootY
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
- For union of x and y
- Use Find to find root of x’s tree
- Use Find to find root of y’s tree
- Make root with larger rank parent of the other root
- If ranks are equal
- Arbitrarily choose which root to make parent
- And increment rank of that root
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
- If you’re at the root (if x.parent == x)
- Return root
- Otherwise, set x.parent => what root ends up being
- x.parent = find(x.parent)
- And then return x.parent (which is now the root)