84 Smart Union Algorithms 4 Union-by-Size - Always change the smaller tree s[ Root]=- size;/*initialized to be-1*/ (Lemma] Let T be a tree created by union-by-size with N nodes. then height)t回(N+1 for the worst case Proof: By induction.(Eaca ergava. have its set name changed at most times Time complexity of N (on aroM Find operations is now O(N+Mlog2 n). B Union-by-Height - Always change the shallow tree§4 Smart Union Algorithms ❖ Union-by-Size -- Always change the smaller tree S [ Root ] = – size; /* initialized to be –1 */ Now T = O( N ) for the worst case example I gave. 1 2  N 【Lemma】Let T be a tree created by union-by-size with N nodes, then height(T)  log2 N +1 Proof: By induction. (Each element can have its set name changed at most log2 N times.) Time complexity of N Union and M Find operations is now O( N + M log2 N ). ❖ Union-by-Height -- Always change the shallow tree