Introduction to algorithms 6.046J/18,401J/SMA5503 Lecture 20 Prof erik demaine
Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 20 Prof. Erik Demaine
Disjoint-set data structure (Union-Find) Problem: Maintain a dynamic collection of pairwise-disjoint sets= {S1, S2, .. S } Each set S; has one element distinguished as the representative element, rep[]. Must support 3 operations: MAKE-SET(x): adds new set {x} to S with rep[{x}]= for any x S; for all). UNION(x, y): replaces sets S, with y in for any x, y in distinct sets,. FIND-SET(x): returns representative rep[Sx. of set S, containing element x. 2001 by Erik D. Demaine Introduction to Algorithms Day33L20.2
© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.2 Disjoint-set data structure (Union-Find) Problem: Maintain a dynamic collection of pairwise-disjoint sets S = { S 1, S2, …, Sr }. Each set Si has one element distinguished as the representative element, rep [ Si ]. Must support 3 operations: • MAKE-SET (x ): adds new set { x } to S with rep[{ x}] = x (for any x ∉ Si for all i). • UNION (x, y ): replaces sets Sx, Sy with Sx ∪ Sy in S for any x, y in distinct sets Sx, Sy . • FIND-SET (x ): returns representative rep [ Sx ] of set Sx containing element x
Simple linked -list solution Store each set s; = 2…2k}asan( unordered doubly linked list. Define representative element reps,i to be the front of the list,x x十 re MAKE-SET(x) initializes x as a lone node. -o() FIND-SET(x) walks left in the list containing x until it reaches the front of the list ⊙(n) UNION(, y) concatenates the lists containing x and y, leaving rep. as FIND-setx -(n) c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.3
© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.3 Simple linked-list solution Store each set Si = {x1, x2, …, xk} as an (unordered) doubly linked list. Define representative element rep[Si] to be the front of the list, x1. Si : x … 1 x2 xk rep[Si] • MAKE-SET(x) initializes x as a lone node. • FIND-SET(x) walks left in the list containing x until it reaches the front of the list. • UNION(x, y) concatenates the lists containing x and y, leaving rep. as FIND-SET[x]. – Θ(1) – Θ(n) – Θ(n)
Simple balanced -tree solution Store each set si=(x1, x2,.,xk as a balanced tree (ignoring keys). Define representative element replsii to be the root of the tree MAKE-SET(x) initializes x S={x12x2,x32x42x5} as a lone node. -O(1) rep[Six FIND-SET() walks up the tree containing x until it reaches the root. -o(g n UNION(, y) concatenates the trees containing x and changing rep o(g n) c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.4
© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.4 Simple balanced-tree solution Store each set Si = {x1, x2, …, xk} as a balanced tree (ignoring keys). Define representative element rep[Si] to be the root of the tree. x1 x4 x3 x2 x5 • MAKE-SET(x) initializes x as a lone node. • FIND-SET(x) walks up the tree containing x until it reaches the root. • UNION(x, y) concatenates the trees containing x and y, changing rep. Si = {x1, x2, x3, x4, x5} rep[Si] – Θ(1) – Θ(lg n) – Θ(lg n)
Plan of attack We will build a simple disjoint-union data structure that, in an amortized sense performs significantly better than o(g n) per op, even better than o(glg n),o( Glg n), etc, but not quite O(1) To reach this goal, we will introduce two key tricks Each trick converts a trivial o(n) solution into a simple o(g n) amortized solution. Together, the two tricks yield a much better solution First trick arises in an augmented linked list Second trick arises in a tree structure c 2001 by erik D. Demaine Introduction to Agorithms Day33L20.5
© 2001 by Erik D. Demaine Introduction to Algorithms Day 33 L20.5 Plan of attack We will build a simple disjoint-union data structure that, in an amortized sense, performs significantly better than Θ(lg n) per op., even better than Θ(lg lg n), Θ(lg lg lg n), etc., but not quite Θ(1). To reach this goal, we will introduce two key tricks. Each trick converts a trivial Θ(n) solution into a simple Θ(lg n) amortized solution. Together, the two tricks yield a much better solution. First trick arises in an augmented linked list. Second trick arises in a tree structure