Editing Disjoint-set data structure (section)

====Union by rank====

For union by rank, a node stores its {{em|rank}}, which is an upper bound for its height.  When a node is initialized, its rank is set to zero.  To merge trees with roots {{mvar|x}} and {{mvar|y}}, first compare their ranks.  If the ranks are different, then the larger rank tree becomes the parent, and the ranks of {{mvar|x}} and {{mvar|y}} do not change.  If the ranks are the same, then either one can become the parent, but the new parent's rank is incremented by one.  While the rank of a node is clearly related to its height, storing ranks is more efficient than storing heights.  The height of a node can change during a <code>Find</code> operation, so storing ranks avoids the extra effort of keeping the height correct.  In pseudocode, union by rank is:

 '''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, rename variables to ensure that''
     ''// x has rank at least as large as that of y''
     '''if''' ''x''.rank < ''y''.rank '''then'''
         (''x'', ''y'') := (''y'', ''x'')
     '''end if'''
 
     ''// Make x the new root''
     ''y''.parent := ''x''
     ''// If necessary, increment the rank of x''
     '''if''' ''x''.rank = ''y''.rank '''then'''
         ''x''.rank := ''x''.rank + 1
     '''end if'''
 '''end function'''

It can be shown that every node has rank <math>\lfloor \log n \rfloor</math> or less.<ref name="Cormen2009"/>  Consequently each rank can be stored in {{math|''O''(log log ''n'')}} bits and all the ranks can be stored in {{math|''O''(''n'' log log ''n'')}} bits. This makes the ranks an asymptotically negligible portion of the forest's size.

It is clear from the above implementations that the size and rank of a node do not matter unless a node is the root of a tree.  Once a node becomes a child, its size and rank are never accessed again.