of coursethe implication of this model is that there is only chance that the next union will involve the large tree another model might say that all unions between any two elements in different trees are equally likelyso larger tree is more likely to be involved in the chance that the large next union than smaller tree in the example abovethere is an tree is involved in the next unionsince (ignoring symmetriesthere are ways in which to merge two elements in { }and ways to merge an element in { with an element in { there are still more models and no general agreement on which is the best the average running time depends on the model( )( log )and (mnbounds have actually been shown for three different modelsalthough the latter bound is thought to be more realistic quadratic running time for sequence of operations is generally unacceptable fortunatelythere are several ways of easily ensuring that this running time does not occur smart union algorithms the unions above were performed rather arbitrarilyby making the second tree subtree of the first simple improvement is always to make the smaller tree subtree of the largerbreaking ties by any methodwe call this approach union-by-size the three unions in the preceding example were all tiesand so we can consider that they were performed by size if the next operation were union( , )then the forest in figure would form had the size heuristic not been useda deeper tree would have been formed (fig we can prove that if unions are done by sizethe depth of any node is never more than log to see thisnote that node is initially at depth when its depth increases as result of unionit is placed in tree that is at least twice as large as before thusits depth can be increased at most log times (we used this argument in the quick-find algorithm at the end of section this implies that the running time for find operation is (log )and sequence of operations takes ( log nthe tree in figure shows the worst tree possible after unions and is obtained if all unions are between equal-sized trees (the worst-case trees are binomial treesdiscussed in to implement this strategywe need to keep track of the size of each tree since we are really just using an arraywe can have the array entry of each root contain the negative of figure result of union-by-size