top bottom figure recursive decompositioncase the bottom node new parents are the nodes themselves mwould no longer be the same fortunatelythere is simpler argumentsince each node on the bottom can have its parent set to itself only oncethe number of charges are limited by the number of nodes on the bottom whose parents are also in the bottom ( is excludedthere is one important detail that we must verify can we get in trouble on subsequent partial find given that our reformulation detaches the nodes between and from the path to ythe answer is no in the original partial findsuppose any of the nodes between and are involved in subsequent original partial find in that caseit will be with one of ' ancestorsand when that happensany of those nodes will be the topmost "bottom nodein our reformulation thus on the subsequent partial findthe original partial find' parent change will have corresponding one unit charge in our reformulation we can now proceed with the analysis let be the total number of original partial find operations let mt be the total number of partial find operations performed exclusively on the top halfand let mb be the total number of partial find operations performed exclusively on the bottom half let be the total number of nodes let nt be the total number of tophalf nodeslet nb be the total number of bottom-half nodesand let nnrb be the total number of non-root bottom nodes ( the number of bottom nodes whose parents are also bottom nodes prior to any partial findslemma mt mb proof in cases and each original partial find operation is replaced by partial find on the top halfand in case it is replaced by partial find on the bottom half thus each partial find is replaced by exactly one partial find operation on one of the halves our basic idea is that we are going to partition the nodes so that all nodes with rank or lower are in the bottomand the remaining nodes are in the top the choice of will be made later in the proof the next lemma shows that we can provide recursive formula