the disjoint sets class in figure the partial find resides entirely in the top half thus one partial find in the top half corresponds to one original partial findand the charges can be recursively assigned to the top half howeverwe run into lots of trouble when we reach figure here is in the bottom halfand is in the top half the path compression would require that all nodes from to ' child acquire as its parent for nodes in the top halfthat is no problembut for nodes in the bottom half this is deal breakerany recursive charges to the bottom have to keep everything in the bottom so as figure showswe can perform the path compression on the topbut while some nodes in the bottom will need new parentsit is not clear what to dobecause the new parents for those bottom nodes cannot be top nodesand the new parents cannot be other bottom nodes the only option is to make loop where these nodesparents are themselves and make sure these parent changes are correctly charged in our accounting although this is new algorithm because it can no longer be used to generate an identical treewe don' need identical treeswe only need to be sure that each original partial find can be mapped into new partial find operation and that the charges are identical figure shows what the new tree will look likeand so the big remaining issue is the accounting looking at figure we see that the path compression charges from to can be split into three parts firstthere is the path compression from (the first top node on the upward pathto clearly those charges are already accounted for recursively then there is the charge from the topmost-bottom node to but that is only one unitand there can be at most one of those per partial find operation in factwe can do little betterthere can be at most one of those per partial find operation on the top half but how do we account for the parent changes on the path from to wone idea would be to argue that those changes would be exactly the same cost as if there were partial find from to but there is big problem with that argumentit converts an original partial find into partial find on the top plus partial find on the bottomwhich means the number of operationsy top bottom figure recursive decompositioncase path compression can be performed on the top nodesbut the bottom nodes must get new parentsthe parents cannot be top parentsand they cannot be other bottom nodes