tree-based partition implementation an alternative data structure for representing partition uses collection of trees to store the elementswhere each tree is associated with different group (see figure in particularwe implement each tree with linked data structure whose nodes are themselves the group position objects we view each position as being node having an instance variableelementreferring to its element xand an instance variableparentreferring to its parent node by conventionif is the root of its treewe set ' parent reference to itself figure tree-based implementation of partition consisting of three groupsa { } { }and { with this partition data structureoperation find(pis performed by walking up from position to the root of its treewhich takes (ntime in the worst case operation union(pqcan be implemented by making one of the trees subtree of the other this can be done by first locating the two rootsand then in ( additional time by setting the parent reference of one root to point to the other root see figure for an example of both operations ( (bfigure tree-based implementation of partition(aoperation union(pq)(boperation find( )where denotes the position object for element