I have been trying to learn more about amortized analysis. Recently I came across the Disjoint Sets or Union-Find structures. I am using union by rank and path comparison. The potential of such data structures is  sum of $\phi(x)$ for all nodes  where$$\phi(x) = \begin{cases}0,  & \text{if }\mathrm{rank}(x)=0 \\\alpha(n)*\mathrm{rank}(x), & \text{if $x$ is the root} \\(\alpha(n) - \mathrm{level}(x))\mathrm{rank}(x) - \mathrm{index}(x), & \text{otherwise.}\end{cases} $$I could somehow successfully analyze the above potential function (trust me, it was really really hard for a beginner like me, but I somehow managed to do it). But I am getting stuck in the middle of my analysis when I change the definition of $\phi(x) $ to a simple $\mathrm{height}(x)$. It would be great if someone could help me learn more about this potential function and guide me how I could analyze the data structure when I change my potential function..P.S : I tried reading documents online about the union-find(disjoint-sets) data structure. But as i read more about the data structure, my analysis is becoming more and more confusing. So if you could point me in the right direction, it would be great. Also, this is my first post here, so if I am in the wrong group and I need to ask the question else where, please let me know the right group where I can post this question.
Analysis of Union-Find(Disjoint Sets)
algorithm analysis;data structures;runtime analysis;amortized analysis;union find