Disjoint-set data structure: Difference between revisions

Revision as of 20:06, 4 October 2004

Revision as of 20:17, 4 October 2004

Line 18:

== Disjoint-set forests ==

In a disjoint-set forest, each set is represented by a [[tree data structure]] where each node holds a [[reference]] to its parent node. The representative of each set is the root of that set's tree. '''Find''' simply follows parent nodes until it reaches the root. '''Union''' combines two trees into one by making the root ofattaching one of them the child ofto the root of the other. One way of implementing these might be:

{{wikicode}}