The disjoint set class - Data Structures and Problem Solving Using Java - page 893

chapter 24

the disjoint
set class

I n this chapter we describe an efficient data structure for solving the
equivalence problem: the disjoint set class. This data structure is simple to
implement, with each routine requiring only a few lines of code. Its imple-
mentation is also extremely fast, requiring constant average time per opera-
tion. This data structure is also very interesting from a theoretical point of
view because its analysis is extremely difficult; the functional form of the
worst case is unlike any discussed so far in this text.
In this chapter, we show

Three simple applications of the disjoint set class

n

A way to implement the disjoint set class with minimal coding effort

n

A method for increasing the speed of the disjoint set class, using two
simple observations

n

An analysis of the running time of a fast implementation of the dis-
joint set class

n