CSE 326: Data Structures Disjoint Union/FindEquivalence RelationsA new questionEquivalence ClassesDetermining equivalence classesBuilding Equivalence ClassesDisjoint Union - FindUnionFindExampleCute ApplicationSlide 12Slide 13Desired PropertiesA CycleA Good SolutionA Hidden TreeNumber the CellsBasic AlgorithmExample StepSlide 21Slide 22Example at the EndImplementing the DS ADTSlide 25Up-Tree for DU/FFind OperationUnion OperationSimple ImplementationSlide 30ExerciseA Bad CaseNow this doesn’t look good Weighted UnionExample AgainAnalysis of Weighted UnionSlide 37Worst Case for Weighted UnionExample of Worst Cast (cont’)Elegant Array ImplementationSlide 41Path CompressionSelf-Adjustment WorksDraw the result of Find(e):Path Compression FindInterlude: A Really Slow FunctionA More Comprehensible Slow FunctionDisjoint Union / Find with Weighted Union and PCAmortized ComplexityFind SolutionsCSE 326: Data StructuresDisjoint Union/FindEquivalence RelationsRelation R :•For every pair of elements (a, b) in a set S, a R b is either true or false.•If a R b is true, then a is related to b.An equivalence relation satisfies:1. (Reflexive) a R a2. (Symmetric) a R b iff b R a3. (Transitive) a R b and b R c implies a R c2A new question•Which of these things are similar?{ grapes, blackberries, plums, apples, oranges, peaches, raspberries, lemons }•If limes are added to this fruit salad, and are similar to oranges, then are they similar to grapes?•How do you answer these questions efficiently?3Equivalence Classes•Given a set of things…{ grapes, blackberries, plums, apples, oranges, peaches, raspberries, lemons, bananas }•…define the equivalence relationAll citrus fruit is related, all berries, all stone fruits, and THAT’S IT.•…partition them into related subsets { grapes }, { blackberries, raspberries }, { oranges, lemons }, { plums, peaches }, { apples }, { bananas }Everything in an equivalence class is related to each other.4Determining equivalence classes•Idea: give every equivalence class a name–{ oranges, limes, lemons } = “like-ORANGES”–{ peaches, plums } = “like-PEACHES”–Etc.•To answer if two fruits are related:–FIND the name of one fruit’s e.c.–FIND the name of the other fruit’s e.c.–Are they the same name?5Building Equivalence Classes•Start with disjoint, singleton sets:–{ apples }, { bananas }, { peaches }, …•As you gain information about the relation, UNION sets that are now related:–{ peaches, plums }, { apples }, { bananas }, …•E.g. if peaches R limes, then we get–{ peaches, plums, limes, oranges, lemons }6Disjoint Union - Find•Maintain a set of pairwise disjoint sets.–{3,5,7} , {4,2,8}, {9}, {1,6}•Each set has a unique name, one of its members–{3,5,7} , {4,2,8}, {9}, {1,6}7Union•Union(x,y) – take the union of two sets named x and y–{3,5,7} , {4,2,8}, {9}, {1,6}–Union(5,1) {3,5,7,1,6}, {4,2,8}, {9}, 8Find•Find(x) – return the name of the set containing x.–{3,5,7,1,6}, {4,2,8}, {9}, –Find(1) = 5–Find(4) = 89Example10S{1,2,7,8,9,13,19}{3}{4}{5}{6}{10}{11,17}{12}{14,20,26,27}{15,16,21}..{22,23,24,29,39,32 33,34,35,36}Find(8) = 7Find(14) = 20S{1,2,7,8,9,13,19,14,20 26,27}{3}{4}{5}{6}{10}{11,17}{12}{15,16,21}..{22,23,24,29,39,32 33,34,35,36}Union(7,20)Cute Application•Build a random maze by erasing edges.11Cute Application•Pick Start and End12StartEndCute Application•Repeatedly pick random edges to delete.13StartEndDesired Properties•None of the boundary is deleted•Every cell is reachable from every other cell.•There are no cycles – no cell can reach itself by a path unless it retraces some part of the path.14A Cycle15StartEndA Good Solution16StartEndA Hidden Tree17StartEndNumber the Cells18StartEnd1 2 3 4 5 67 8 9 10 11 1213 14 15 16 17 1819 20 21 22 23 2425 26 27 28 29 3031 32 33 34 35 36We have disjoint sets S ={ {1}, {2}, {3}, {4},… {36} } each cell is unto itself.We have all possible edges E ={ (1,2), (1,7), (2,8), (2,3), … } 60 edges total.Basic Algorithm•S = set of sets of connected cells•E = set of edges•Maze = set of maze edges initially empty19While there is more than one set in S pick a random edge (x,y) and remove from E u := Find(x); v := Find(y); if u  v then Union(u,v) else add (x,y) to MazeAll remaining members of E together with Maze form the mazeExample Step20StartEnd1 2 3 4 5 67 8 9 10 11 1213 14 15 16 17 1819 20 21 22 23 2425 26 27 28 29 3031 32 33 34 35 36S{1,2,7,8,9,13,19}{3}{4}{5}{6}{10}{11,17}{12}{14,20,26,27}{15,16,21}..{22,23,24,29,30,32 33,34,35,36}Pick (8,14)Example21S{1,2,7,8,9,13,19}{3}{4}{5}{6}{10}{11,17}{12}{14,20,26,27}{15,16,21}..{22,23,24,29,39,32 33,34,35,36}Find(8) = 7Find(14) = 20S{1,2,7,8,9,13,19,14,20 26,27}{3}{4}{5}{6}{10}{11,17}{12}{15,16,21}..{22,23,24,29,39,32 33,34,35,36}Union(7,20)Example22StartEnd1 2 3 4 5 67 8 9 10 11 1213 14 15 16 17 1819 20 21 22 23 2425 26 27 28 29 3031 32 33 34 35 36S{1,2,7,8,9,13,19 14,20,26,27}{3}{4}{5}{6}{10}{11,17}{12}{15,16,21}..{22,23,24,29,39,32 33,34,35,36}Pick (19,20)Example at the End23StartEnd1 2 3 4 5 67 8 9 10 11 1213 14 15 16 17 1819 20 21 22 23 2425 26 27 28 29 3031 32 33 34 35 36S{1,2,3,4,5,6,7,… 36}EMazeImplementing the DS ADT•n elements, Total Cost of: m finds,  n-1 unions•Target complexity: O(m+n) i.e. O(1) amortized•O(1) worst-case for find as well as union would be great, but…Known result: find and union cannot both be done in worst-case O(1) time24Implementing the DS ADT•Observation: trees let us find many elements given one root…•Idea: if we reverse the pointers (make them point up from child to parent), we can find a single root from many elements…•Idea: Use one tree for each equivalence class. The name of the class is the tree root.25Up-Tree for DU/F261 2 3 4 5 6 7Initial state1234567IntermediatestateRoots are the names of each set.Find Operation•Find(x) follow x to the root and return the root271234567Find(6) = 7Union Operation•Union(i,j) - assuming i and j roots, point i to j.281234567Union(1,7)Simple Implementation•Array of indices2912345670 1 0 7 7 5 01 2 3 4 5 6 7upUp[x] = 0 meansx is a root.Union30Union(up[] : integer array, x,y : integer) : {//precondition: x and y are roots//Up[x] := y}Constant Time!Exercise•Design Find operator–Recursive version–Iterative version31Find(up[] : integer array, x : integer) : integer {//precondition: x is in the range 1 to size//???}A Bad