How to prove the complexity of DSU that merges by size is O(logN)?

Revision en1, by xzyxzy, 2019-09-07 07:58:16

Just like this:

int find(int x)
{
  if(f[x]==x) return x;
  return find(f[x]);
}
void merge(int x,int y)
{
  x=find(x);y=find(y);
  if(size[x]<size[y]) swap(x,y);
  f[y]=x;size[x]+=size[y];
}

I've knew that the complexity of merging by MAX-depth is $$$O(logN)$$$. But I can't figure out the proof that the complexity of merging by size is $$$O(logN)$$$. Can anyone help?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English xzyxzy 2019-09-07 07:58:16 459 Initial revision (published)