click below
click below
Normal Size Small Size show me how
Union-Find Algorithm
Data Structures
Question | Answer |
---|---|
What operations are there for disjoint subsets? (UF algs) | Find, connected, create unions |
Signature of operation find: | subset find(element x) |
Signature of operation connected: | boolean connected(element x, element y) |
Signature of operation create union: | void union(element x, element y) |
How do we represent sets for UF algs: | Array of ints, where K is an element, and a[k] is what it points to. |
In large sets, traditional UF operations take how much time (worst case)? | O(n) |
How do we reduce the time it takes in larger sets? | Make each element we pass in find operation point to the "root" |