Dynamic Set Forests are a collection of trees used to represent disjoint sets. Each tree represents a set, with the root node as the representative. This visualization demonstrates the union and find operations with both union by rank and path compression optimizations.
Select an operation and enter value(s) to see the explanation here.
| Operation | Without Optimizations | With Union by Rank & Path Compression |
|---|---|---|
| Make Set | O(1) | O(1) |
| Find | O(n) | O(α(n)) |
| Union | O(n) | O(α(n)) |
Note: α(n) is the inverse Ackermann function, which grows very slowly.