partition implementation as follows proposition using sequence-based implementation of partitionin series of nmakesetunionandfind operations starting from an initially empty partitionthe amortized running time of each operation is (lognnote that in this sequence-based implementation of partitioneach find operation takes worst-case ( time it is the running time of the union operations that is the computational bottleneck in the next sectionwe describe tree-based implementation of partition that does not guarantee constant-time find operationsbut has amortized time much better than (lognper union operation tree-based partition implementation an alternative data structure uses collection of trees to store the elements in setswhere each tree is associated with different set (see figure in particularwe implement each tree with linked data structure whose nodes are themselves the set position objects we still view each position as being node having variableelementreferring to its element xand variablesetreferring to set containing xas before but now we also view each position as being of the "setdata type thusthe set reference of each position can point to positionwhich could even be itself moreoverwe implement this approach so that all the positions and their respective set references together define collection of trees we associate each tree with set for any position pif ' set reference points back to pthen is the root of its treeand the name of the set containing is " (that iswe will be using position names as set names in this caseotherwisethe set reference for points to ' parent in its tree in either casethe set containing is the one associated with the root of the tree containing figure tree-based implementation of partition consisting of three disjoint setsa , , , , , and , , , ,