Questions tagged [disjoint-sets]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
60 views

Difficulty in few steps in proof of “Amortized cost of $\text{Find-Set}$ operation is $\Theta(\alpha(n))$”assuming union by rank, path compression

I was reading the section of data structures for disjoint sets from the text Introduction to Algorithms by Cormen et. al .I faced difficulty in understanding few steps in the proof of the lemma as ...
2
votes
1answer
49 views

Runtime difference bewteen Union by Rank and Union by Size for union-find

I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)? Intuitively,...
1
vote
0answers
58 views

Amortized analysis for disjoint sets' find-set(x) function (from CLRS)

I start off by apologizing for the fact that I don't really know how to use latex/markdown. My question, however, is directly from the Introduction To Algorithms book by Cormen et al. The topic ...
0
votes
0answers
22 views

Benefits of linked lists over forests for disjoint sets

CLRS discusses two specific data structures for disjoint sets: Single linked lists, where each set is represented by a single linked list, and each node has two pointers, one to the list head and ...