the disjoint sets class figure result of an arbitrary union figure worst-case tree for the size of its tree thusinitially the array representation of the tree is all - when union is performedcheck the sizesthe new size is the sum of the old thusunion-by-size is not at all difficult to implement and requires no extra space it is also faston average for virtually all reasonable modelsit has been shown that sequence of operations requires (maverage time if union-by-size is used this is because when random unions are performedgenerally very small (usually one-elementsets are merged with large sets throughout the algorithm an alternative implementationwhich also guarantees that all the trees will have depth at most (log )is union-by-height we keep track of the heightinstead of the sizeof each tree and perform unions by making the shallow tree subtree of the deeper tree this is an easy algorithmsince the height of tree increases only when two equally deep trees are joined (and then the height goes up by onethusunion-by-height is trivial modification of union-by-size since heights of zero would not be negativewe actually store the negative of heightminus an additional initiallyall entries are - figure shows forest and its implicit representation for both union-by-size and union-by-height the code in figure implements union-by-height