the disjoint sets class partial path compression algorithm is our standard sequence of union-by-rank and find with path compression operations we design an algorithm that will perform the exact same sequence of path compression operations as algorithm in algorithm bwe perform all the unions prior to any find then each find operation in algorithm is replaced by partial find operation in algorithm partial find operation specifies the search item and the node up to which the path compression is performed the node that will be used is the node that would have been the root at the time the matching find was performed in algorithm figure shows that algorithm and algorithm will get equivalent trees (forestsat the endand it is easy to see that the exact same amount of parent changes are performed by algorithm ' findscompared to algorithm ' partial finds but algorithm should be simpler to analyzesince we have removed the mixing of unions and finds from the equation the basic quantity to analyze is the number of parent changes that can occur in any sequence of partial findssince all but the top two nodes in any find with path compression will obtain new parents recursive decomposition what we would like to do next is to divide each tree into two halvesa top half and bottom half we would then like to ensure that the number of partial find operations in the top half plus the number of partial find operations in the bottom half is exactly the same as the total number of partial find operations we would then like to write formula for the total path compression cost in the tree in terms of the path compression cost in the top half plus the path compression cost in the bottom half without specifying how we decide which nodes are in the top halfand which nodes are in the bottom halfwe can look at figures and to see how most of what we want to do can work immediately in figure the partial find resides entirely in the bottom half thus one partial find in the bottom half corresponds to one original partial findand the charges can be recursively assigned to the bottom half find (cg union (bfg union (bfa partial find (cba figure sequences of union and find operations replaced with equivalent cost of union and partial find operations