Content deleted Content added
Added applications and some more skeleton |
Added linked list approach |
||
Line 4:
The other important operation, '''Make-Set''', which makes a singleton set containing only a given element, is generally trivial. With these three operations, many practical partitioning problems can be solved (see the ''Applications'' section).
While we could represent the sets themselves as objects and have the operations operate on these sets, the more common approach is to choose an element from each set as a ''representative''; then, '''Find''' returns the representative of the set that the given element is in, and '''Union''' takes the representatives of two given sets.
== Linked lists ==
Perhaps the simplest approach to creating a disjoint-set data structure is to create a [[linked list]] for each group. We choose the element at the head of the list as the representative.
'''Make-Set''' is obvious, creating a list of one element. '''Union''' simply appends the two lists, a constant-time operation. Unfortunately, it seems that '''Find''' requires [[Big-O notation|O]](n) or linear time with this approach.
We can avoid this by including in each linked list node a pointer to the head of the list; then '''Find''' takes constant time. However, we've now ruined the time of '''Union''', which has to go through the elements of the list being appended to make them point to the head of the new combined list. We can ameliorate this by always appending the smaller list to the longer, or by adapting '''Find''' so that it will follow chains of ''head of list'' pointers and only modifying the first node's pointer, but none of these approaches achieve the most effective balance. We choose instead to start over with a different data structure.
== Disjoint-set forests ==
Line 28 ⟶ 38:
== References ==
* Chapter 21, ''Introduction to Algorithms'', 2nd ed. Cormen, Leiserson, Rivest, Stein. ISBN 0262032937.
| |||