Editing Disjoint-set data structure (section)

=== Making new sets ===

The <code>MakeSet</code> operation adds a new element into a new set containing only the new element, and the new set is added to the data structure.  If the data structure is instead viewed as a partition of a set, then the <code>MakeSet</code> operation enlarges the set by adding the new element, and it extends the existing partition by putting the new element into a new subset containing only the new element.

In a disjoint-set forest, <code>MakeSet</code> initializes the node's parent pointer and the node's size or rank.  If a root is represented by a node that points to itself, then adding an element can be described using the following pseudocode:

 '''function''' MakeSet(''x'') '''is'''
     '''if''' ''x'' is not already in the forest '''then'''
         ''x''.parent := ''x''
         ''x''.size := 1     ''// if nodes store size''
         ''x''.rank := 0     ''// if nodes store rank''
     '''end if'''
 '''end function'''

This operation has linear time complexity.  In particular, initializing a
disjoint-set forest with {{mvar|n}} nodes requires {{math|''O''(''n'')}}
time.

Lack of a parent assigned to the node implies that the node is not present in the forest.

In practice, <code>MakeSet</code> must be preceded by an operation that allocates memory to hold {{math|x}}.  As long as memory allocation is an amortized constant-time operation, as it is for a good [[dynamic array]] implementation, it does not change the asymptotic performance of the random-set forest.