CSE310 Lecture 13: Disjoint Set OperationsTopics of this lecturePowerPoint PresentationSlide 4Slide 5Slide 6Tree ViewArray Implementation of Disjoint SetsSlide 9Slide 10Slide 11Height of the treesSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Find with path compressionSlide [email protected] Lecture 13:CSE310 Lecture 13:Disjoint Set OperationsDisjoint Set OperationsGuoliang (Larry) XueComputer Science and EngineeringArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureDisjoint SetsOperations on Disjoint setsApplicationsTree Representation and Array ImplementationsUnion by RankFind with Path CompressionAmortized [email protected] Structure for Disjoint SetsA disjoint set data structure maintains a collection (set)S = {S1, S2, ... Sk}of disjoint dynamic (sub) sets.Each element x of a set is a pointer to an object, possibly with multiple fields.Representative of a set: We choose one element of a set to identify the set, e.g., we use the root of a tree to identify a tree, or the head element of a linked list to access the linked list.Operations on this data structureAn applicationImplementation using linked lists and rooted treesRunning [email protected] on Disjoint SetsMake-Set(x)creates a new set whose only member is x. Obviously, x is the representative.Union(x, y)replaces the two sets Sx and Sy that contain elements x and y by their union. Sets are assumed to be disjoint (no element overlap). The representative of Sx or Sy becomes the representative of the united set.Find-Set(x)returns the pointer to the representative of the (unique) set containing [email protected] Disjoint-Set via an ExampleAssume we have an undirected graph G = (V, E) consisting of a number of subgraphs that are not connected to each other.abcdgef hiHow do we store a graph in a computer? Standard methods.Adjacency matrix, e.g., a 9x9 matrixSet: G = {V, E}, V = {a, b, ..., i} E = {(a, b), (a, c), (b, c), (d, e), (d, g), (e, f), (e, g), (h, i)}We can use disjoint-set to determine whether a graph is connectedand whether two vertices are in the same connected component.[email protected] Finding Connected ComponentsConnected-Components(G)1. for each vertex v  V(G) do2. Make-Set(v)3. for each edge (u, v)  E(G) do4. if Find-Set(u)  Find-Set(v)5. then Union(u, v)edge processed collection of disjoint setsinitial sets {a} {b} {c} {d} {e} {f} {g} {h} {i}(a, b) {a b} {c} {d} {e} {f} {g} {h} {i}(a, c) {a b c} {d} {e} {f} {g} {h} {i}(b, c) Find-Set(b) = Find-Set(c)(d, e) {a b c} {d e} {f} {g} {h} {i}(d, g) {a b c} {d e g} {f} {h} {i}(e, f) {a b c} {d e g f} {h} {i}(e, g) Find-Set(e) = Find-Set(g)(h, i) {a b c} {d e g f} {h i}three disjoint setsn(n+1)n2Same-Components(u, v)1. if Find-Set(u) = Find-Set(v)2. then return TRUE3. else return [email protected] ViewTree ViewWe can use a forest to represent disjoint sets.The root is the representative.How to perform Make-Set?How to perform Find(x)?How to perform Union(x, y)?What are the time complexities?How do we represent the [email protected] Implementation of Disjoint SetsArray Implementation of Disjoint SetsWe use a linear array A with index from 1 to n to implement disjoint sets on the first n numbers.Make-Set(x) is accomplished byA[x] := 0; // x is the root, the rank of the tree at x is 0.A[x] > 0 indicates that x is not the root and that the parent of x is at location A[x].A[x] <= 0 indicates that x is the root and that the rank of the tree rooted at x is –A[x][email protected] Implementation of Disjoint SetsArray Implementation of Disjoint Sets0 0 0 0 0 0 0 0-1 1 -1 3 -1 5 -1 [email protected] Implementation of Disjoint SetsArray Implementation of Disjoint SetsLink(x, y) is accomplished byif –A[x] > -A[y] then // x has a higher rank than y•A[y] = x;else•if –A[x] = -A[y] then A[y] = A[y] – 1; // rank of y is incremented.•A[x] = y;If the two trees have the same rank, we choose y as the root and increment its rank.If the two trees have different ranks, we favor the tree with a higher [email protected] Implementation of Disjoint SetsArray Implementation of Disjoint SetsFind-Set1(x) is accomplished byif A[x] <=0 then•return x;else•return Find-Set1(A[x]);Union1(x, y) is accomplished byLink(Find-Set1(x), Find-Set1(y));[email protected] of the treesHeight of the treesTHEOREM: Let n be the number of nodes in a tree and let r be the rank of the tree. Assuming we are using union by rank, then n >= 2r.Proof. This is true when r=0 (n=1). When we are taking the union of two trees with different ranks, the number of nodes is increased but the rank stays the same. When we are taking the union of two trees with the same rank, the number of nodes in the new tree is at least 2*2r, but the new rank is [email protected]:abcdefUNION(a, b)UNION(c, e)abcedfUNION(b, f)ba fcedrank(a) = rank(b) = … = rank(e) = log 1 = 0rank(b) = rank(e) = log 2 = 1rank(b) = log 3 = 1ecdba fUNION(b, e)ecbafrank(e) = log 5 = 2UNION(a, d)[email protected]• m = total number of operations (MAKE-SET, UNION, & FIND) n = total number of MAKE-SET operations• Union by rank heuristic: worst case total running time (for all m operations) is (m log n). Why?It is not hard to see that the total running time is O(m log n). We just need to show that a tree representing a set with k elements has height (log k), since the maximum height of a tree is an upper bound on the running time of any of the three operations.How do we show that the height of a tree with k elements is (log k) [email protected] induction on number of elements in a tree.log k1log k2tree with k2 elementstree with k1 elementsyx- Base case: a tree with one element has height of log 1 = 0.- Resulting tree (after UNION operation) has k1 + k2 elements.- Height of resulting tree ismax { log k1, (log k2) + 1 } < log (k1 + k2)since we are using union by [email protected][y]tree with k2 elementstree with k1 elementsyxrank[x]Use induction on number of elements in a tree.- Base case: a tree with one element x has