Disjoint Union / FindReadingEquivalence RelationsEquivalence ClassesDynamic Equivalence ProblemDisjoint Union - FindUnionFindAn ApplicationAn Application (ct’d)Slide 11Desired PropertiesA Cycle (we don’t want that)A Good SolutionGood Solution : A Hidden TreeNumber the CellsBasic AlgorithmExample StepExampleSlide 20Example at the EndUp-Tree for DU/FFind OperationUnion OperationSimple ImplementationSlide 26Slide 27A Bad CaseWeighted UnionExample AgainAnalysis of Weighted UnionSlide 32Worst Case for Weighted UnionExample of Worst Cast (cont’)Elegant Array ImplementationSlide 36Path CompressionSelf-Adjustment WorksPath Compression FindSlide 40Disjoint Union / Find with Weighted Union and PCAmortized ComplexityFind SolutionsDisjoint Union / FindCSE 373Data StructuresLecture 1712/26/03 Union/Find - Lecture 17 2Reading•Reading›Chapter 8 (you can skip Section 6)12/26/03 Union/Find - Lecture 17 3Equivalence Relations•A relation R is defined on set S if for every pair of elements a, b S, a R b is either true or false. •An equivalence relation is a relation R that satisfies the 3 properties:›Reflexive: a R a for all a S›Symmetric: a R b iff b R a; a, b S›Transitive: a R b and b R c implies a R cbac12/26/03 Union/Find - Lecture 17 4Equivalence Classes•Given an equivalence relation R, decide whether a pair of elements a, b S is such that a R b.•The equivalence class of an element a is the subset of S of all elements related to a. •Equivalence classes are disjoint sets3124 512/26/03 Union/Find - Lecture 17 5Dynamic Equivalence Problem•Starting with each element in a singleton set, and an equivalence relation, build the equivalence classes•Requires two operations:›Find the equivalence class (set) of a given element›Union of two sets•It is a dynamic (on-line) problem because the sets change during the operations and Find must be able to cope!12/26/03 Union/Find - Lecture 17 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}12/26/03 Union/Find - Lecture 17 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},12/26/03 Union/Find - Lecture 17 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) = 8›Find(9) = ?12/26/03 Union/Find - Lecture 17 9An Application•Build a random maze by erasing edges.12/26/03 Union/Find - Lecture 17 10An Application (ct’d)•Pick Start and EndStartEnd12/26/03 Union/Find - Lecture 17 11An Application (ct’d)•Repeatedly pick random edges to delete.StartEnd12/26/03 Union/Find - Lecture 17 12Desired 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.12/26/03 Union/Find - Lecture 17 13A Cycle (we don’t want that)StartEnd12/26/03 Union/Find - Lecture 17 14A Good SolutionStartEnd12/26/03 Union/Find - Lecture 17 15Good Solution : A Hidden TreeStartEnd12/26/03 Union/Find - Lecture 17 16Number the CellsStartEnd1 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.12/26/03 Union/Find - Lecture 17 17Basic Algorithm•S = set of sets of connected cells•E = set of edges•Maze = set of maze edges initially emptyWhile 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) //knock down the wall between the cells (cells in //the same set are connected) else add (x,y) to Maze //don’t remove because there is already // a path between x and yAll remaining members of E together with Maze form the maze12/26/03 Union/Find - Lecture 17 18Example StepStartEnd1 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)12/26/03 Union/Find - Lecture 17 19ExampleS{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)12/26/03 Union/Find - Lecture 17 20ExampleStartEnd1 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)12/26/03 Union/Find - Lecture 17 21Example at the EndStartEnd1 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}EMaze12/26/03 Union/Find - Lecture 17 22Up-Tree for DU/F1 2 3 4 5 6 7Initial state1234567IntermediatestateRoots are the names of each set.12/26/03 Union/Find - Lecture 17 23Find Operation•Find(x) follow x to the root and return the root (which is the name of the class).1234567Find(6) = 712/26/03 Union/Find - Lecture 17 24Union Operation•Union(i,j) - assuming i and j roots, point i to j.1234567Union(1,7)12/26/03 Union/Find - Lecture 17 25Simple Implementation•Array of indices (Up[i] is parent of i)12345670 1 0 7 7 5 01 2 3 4 5 6 7upUp [x] = 0 meansx is a root.12/26/03 Union/Find - Lecture 17 26UnionUnion(up[] : integer array, x,y : integer) : {//precondition: x and y are roots//Up[x] := y}Constant Time!12/26/03 Union/Find - Lecture 17 27Find•Design Find operator›Recursive version›Iterative versionFind(up[] : integer array, x : integer) : integer {//precondition: x is in the range 1 to size//???} UPxif up[x] = 0 then return xelse12/26/03 Union/Find - Lecture 17 28 A Bad Case1 2 3 n…12 3 nUnion(1,2)123 nUnion(2,3)Union(n-1,n)……123n::Find(1) n steps!!12/26/03 Union/Find - Lecture 17 29Weighted Union•Weighted Union (weight = number of nodes)›Always point the smaller tree to the root of the larger tree1234567W-Union(1,7)24112/26/03 Union/Find - Lecture 17 30Example Again1 2 3 n12 3 nUnion(1,2)123nUnion(2,3)Union(n-1,n)……::123 n…Find(1) constant time…12/26/03 Union/Find - Lecture 17 31Analysis of