Editing Disjoint-set data structure (section)

====Union by size====

In the case of union by size, a node stores its size, which is simply its number of descendants (including the node itself).  When the trees with roots {{mvar|x}} and {{mvar|y}} are merged, the node with more descendants becomes the parent.  If the two nodes have the same number of descendants, then either one can become the parent.  In both cases, the size of the new parent node is set to its new total number of descendants.

 '''function''' Union(''x'', ''y'') '''is'''
     ''// Replace nodes by roots''
     ''x'' := Find(''x'')
     ''y'' := Find(''y'')
 
     '''if''' ''x'' = ''y'' '''then'''
         '''return'''  ''// x and y are already in the same set''
     '''end if'''
 
     ''// If necessary, swap variables to ensure that''
     ''// x has at least as many descendants as y''
     '''if''' ''x''.size < ''y''.size '''then'''
         (''x'', ''y'') := (''y'', ''x'')
     '''end if'''
 
     ''// Make x the new root''
     ''y''.parent := ''x''
     ''// Update the size of x''
     ''x''.size := ''x''.size + ''y''.size
 '''end function'''

The number of bits necessary to store the size is clearly the number of bits necessary to store {{mvar|n}}.  This adds a constant factor to the forest's required storage.