Reference no: EM131667267

Question: Write a program to determine the effects of path compression and the various union strategies. Your program should process a long sequence of equivalence operations, using all the strategies discussed (including path halving, introduced in Exercise).

Exercise: Suppose that you implement partial path compression on find(i) by changing the parent of every other node on the path from i to the root to its grandparent (where doing so makes sense). This process is called path halving. Prove that, if path halving is performed on the finds and either union heuristic is used, the worst-case running time is still O(M log*N).