figure large disjoint set tree (numbers below nodes are rankswe begin by establishing two lemmas concerning the properties of the ranks figure gives visual picture of both lemmas lemma when executing sequence of union instructionsa node of rank must have at least one child of rank proof by induction the basis is clearly true when node grows from rank to rank rit obtains child of rank by the inductive hypothesisit already has children of ranks thus establishing the lemma the next lemma seems somewhat obvious but is used implicitly in the analysis lemma at any point in the union/find algorithmthe ranks of the nodes on path from the leaf to root increase monotonically proof the lemma is obvious if there is no path compression ifafter path compressionsome node is descendant of wthen clearly must have been descendant of when only unions were considered hence the rank of is less than the rank of suppose we have two algorithmsa and algorithm works and computes all the answers correctlybut algorithm does not compute correctlyor even produce useful answers supposehoweverthat every step in algorithm can be mapped to an equivalent step in algorithm then it is easy to see that the running time for algorithm describes the running time for algorithm exactly we can use this idea to analyze the running time of the disjoint sets data structure we will describe an algorithm bwhose running time is exactly the same as the disjoint sets structureand then algorithm cwhose running time is exactly the same as algorithm thus any bound for algorithm will be bound for the disjoint sets data structure