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)