Disjoint-set data structure: Difference between revisions

Revision as of 17:16, 6 December 2004

Revision as of 17:08, 16 June 2005

Line 20:

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 attaching one to the root of the other. One way of implementing these might be:

{{wikicode}}

'''function''' MakeSet(x)

x.parent := '''null'''