Disjoint Set DS -

Disjoint Set DS -

i have been studying disjoint set info structures.

i've query while using union rank & path compression together, if skip using union rank & assign precedence(parent) without ranks comparison(of ranks of roots/representative element) of 2 sets(trees) impact running time.

though weighted-union heuristic required while merging 2 sets,to append smaller set larger 1 create minimum updates possible point representative element.

union-by-rank(similar weighted-union) used while merging 2 sets.but if skip comparing ranks & randomly assign precedence, won't impact running time??then why utilize it..i unable see through ,please help me understand if i'm wrong.

//no comparing ranks

union(x,y)

x.parent=y;

genralized code

union(x,y){ if(x.rank>y.rank) y.parent=x; else x.parent=y; if(x.rank==y.rank) y.rank=y.rank+1; }

if consider n disjoint sigleton elements , apply union function on them in such way root of 1 set(i.e. of tree formed in representation of set) comes in union singleton element, in these union cases path compression has no effect , may end creating linked list.

in such worst cases, complexity of single find can θ(n), while union excluding find 2 sets still θ(1) when including union rank. so, worst case complexities of individual queries on set improved using union rank keeps θ(lgn).

if consider case after queries 1 or constant number of final sets union rank makes difference in overall complexity if path compression used.

disjoint-union