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