Disjoint SetsDisjoint SetsEquivalence RelationEquivalence ClassDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsDisjoint SetsExampleExample (cont.)ImplementationImplementationImplementationImplementationAnalysisSmart UnionSmart Union ExampleSmart Union by HeightSmart Union by Height ExampleSmart Union by Height ImplementationPath CompressionPath Compression ExamplePath Compression ImplementationPath Compression with Smart UnionAnalysis of Union-by-Rank and Path CompressionAckermann’s FunctionInverse of Ackermann’s FunctionAnalysis of Union-by-Rank and Path CompressionApplication: Maze GenerationMaze Generation ExampleMaze Generation ExampleMaze Generation ExampleMaze Generation ExampleMore ApplicationsSummary111111Disjoint SetsCptS 223 – Advanced Data StructuresLarry HolderSchool of Electrical Engineering and Computer ScienceWashington State UniversityDisjoint Sets Data structure for problems requiring equivalence relations I.e., Are two elements in the same equivalence class Applications Reachability of components in a graph Disjoint sets provide a simple, fast solution Simple: array-based implementation Fast: O(1) per operation average case Analysis is challenging2Equivalence Relation Relation R on set S maps pairs of elements of S to true or false For all a,b ∈ S, (a R b) Æ {true,false} Equivalence relation is a relation R such that the following hold R is reflexive: (a R a) for all a ∈ S R is symmetric: (a R b) ⇔ (b R a) R is transitive: (a R b) and (b R c) Æ (a R c) Example: Equality over integers3Equivalence Class Given set S and equivalence relation R Find the subsets Siof S such that For all a,b ∈ Si: (a R b) For all a ∈ Si, b ∈ Sj, i ≠ j: not (a R b) These Siare the equivalence classes of S for relation R The Siare “disjoint sets” Example: S = {1,2,3,4,3,3,2,1,3}, R is =4Disjoint Sets Main operation Determine if a and b are in the same equivalence class Approach Put each element of S in a disjoint set of its own If a and b are related, then union the sets containing a and b5Disjoint Sets Example S = {1a, 2a, 3a, 4a, 3b, 3c, 2b, 1b, 3d} DS = { {1a}, {2a}, {3a}, {4a}, {3b}, {3c}, {2b}, {1b}, {3d} } 3aR 3b?, 3cR 3d? DS = { {1a}, {2a}, {3a,3b}, {4a}, {3c,3d}, {2b}, {1b} } 3aR 3c? DS = { {1a}, {2a}, {3a,3b,3c,3d}, {4a}, {2b}, {1b} }6Disjoint Sets Operations Find(a) Returns a representative of the equivalence class containing a Union(Si,Sj) Creates a new set Sk= SiU Sj Associates single representative to all elements of Sk Assume each element can be associated with a unique integer 0 to N-17Disjoint Sets Solution #1 Maintain an array of size N containing the representative of each element Find is a O(1) lookup Union(a,b) Assuming a in class i and b in class j Scan array, changing all i’s to j’s O(N) per union (how many unions?) Okay if Ω(N2) find operations O(1) per union/find operation8Disjoint Sets Solution #2a Maintain a linked list for each equivalence class Increases time to find an element Decreases time for unions by not having to search all N elements Just the two lists where the elements are found And then concatenate lists: O(size of larger list) Still, Θ(N2) performance in worst case9Disjoint Sets Solution #2b Maintain a linked list for each equivalence class Also maintain size of each class (list) Union always concatenates the smaller to the larger class (list) Thus, N-1 unions cost O(N log N) (why?) Any sequence of M finds and N-1 unions takes time O(M + N log N)10Disjoint Sets Performance Can ensure O(1) worst-case time for find operation Or, can ensure O(1) worst-case time for union operation But not both Solution #3 Fast unions, slow finds But, achieves O(M+N) time for any sequence of M finds and N-1 unions11Disjoint Sets Solution 3 Represent each set as a tree Tree’s root is the representative element for the set Disjoint sets are a forest of trees Find(a) returns root element of tree containing a Union(a,b) points root node of tree containing b to root node of tree containing a Implemented as array s, where s[i] = index of parent node in tree (or -1 if root)12Example13Initial disjoint sets of 8 elements (really an array of size 8 of all -1s):After union(4,5):Example (cont.)14After union(6,7):After union(4,6):Implementation15Implementation16Implementation17Implementation18Analysis Find(x) Proportional to depth of tree containing x Deepest tree? Worst-case running time O(N) M consecutive find operations O(MN) worst case Average case analysis What is the average case? Unions can still cost O(N2) But we can do better…19Smart Union Union by size Link smaller tree to larger tree Maximum node depth is (log2N) (why?) Find(x) running time? Sequence of M operations requires O(M) time Random unions tend to merge large sets with small sets Thus, only increase depth of smaller set Implementation Use (- size) instead of -1 for root entries20Smart Union Example21Union(3,4)Smart-Union(3,4)-1 -1 -1 4 -5 4 4 60 1 2 3 4 5 6 7Smart Union by Height Keep track of height of each tree, rather than size Union: Link smaller-height tree to larger-height tree Height only increases when two equal-height trees joined Still O(log N) maximum depth Still O(M) time for M operations Implementation Store (negative of height) minus 122Smart Union by HeightExample23-1 -1 -1 4 -3 4 4 60 1 2 3 4 5 6 7Smart Union by Height Implementation24Path Compression Smart union achieves O(M) time for M operations (average case) But still O(M log N) in the worst case Path compression All nodes accessed during a Find(x) are linked directly to the root Path compression without smart union still O(M log N) worst case25Path Compression Example26After Find(14):Path Compression Implementation27Path Compression withSmart Union Path compression works as is with union-by-size (tree sizes don’t change) Path compression with union-by-height requires re-computation of heights Solution: Don’t recompute heights Heights become (possibly over) estimates of true height Also called “ranks” and this solution is called “union-by-rank” Ranks are modified far less than sizes, so slightly faster in
View Full Document