Disjoint-set data structure: Difference between revisions

Revision as of 03:42, 19 November 2005

Revision as of 04:18, 24 December 2005

Line 18:

== Disjoint-set forests ==

InWe anow turn to disjoint-set forestforests, a data structure where each set is represented by a [[tree data structure]] where each node holds a [[reference]] to its parent node. TheDisjoint-set forests were first described by Bernard A. Galler and Michael J. Fisher in 1964,{{ref|GallerFisher}} although their precise analysis took years.

In a disjoint-set forest, 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:

'''function''' MakeSet(x)

Line 100 ⟶ 102:

[[Category:Data structures]]

[[Category:Algorithms]]

== Notes ==

Line 107 ⟶ 108:

== References ==

* {{note|GallerFisher}}Bernard A. Galler and Michael J. Fisher. An improved equivalence algorithm. Communications of the ACM, Volume 7, Issue 5 (May 1964), pages 301-303. The paper originating disjoint-set forests. [http://portal.acm.org/citation.cfm?doid=364099.364331 ACM Digital Library]

* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Chapter 21: Data structures for Disjoint Sets, pp.498–524.

* Zvi Galil and Giuseppe F. Italiano. Data structures and algorithms for disjoint set union problems",

ACM Computing Surveys, Volume 23, Issue 3 (September 1991), pages 319-344. [http://portal.acm.org/citation.cfm?id=116878 ACM Digital Library]