Editing Disjoint-set data structure (section)

=== Finding set representatives ===

The <code>Find</code> operation follows the chain of parent pointers from a specified query node {{mvar|x}} until it reaches a root element.  This root element represents the set to which {{mvar|x}} belongs and may be {{mvar|x}} itself.  <code>Find</code> returns the root element it reaches.

Performing a <code>Find</code> operation presents an important opportunity for improving the forest.  The time in a <code>Find</code> operation is spent chasing parent pointers, so a flatter tree leads to faster <code>Find</code> operations.  When a <code>Find</code> is executed, there is no faster way to reach the root than by following each parent pointer in succession.  However, the parent pointers visited during this search can be updated to point closer to the root.  Because every element visited on the way to a root is part of the same set, this does not change the sets stored in the forest.  But it makes future <code>Find</code> operations faster, not only for the nodes between the query node and the root, but also for their descendants.  This updating is an important part of the disjoint-set forest's amortized performance guarantee.

There are several algorithms for <code>Find</code> that achieve the asymptotically optimal time complexity.  One family of algorithms, known as '''path compression''', makes every node between the query node and the root point to the root.  Path compression can be implemented using a simple recursion as follows:

 '''function''' Find(''x'') '''is'''
     '''if''' ''x''.parent ≠ ''x'' '''then'''
         ''x''.parent := Find(''x''.parent)
         '''return''' ''x''.parent
     '''else'''
         '''return''' ''x''
     '''end if'''
 '''end function'''

This implementation makes two passes, one up the tree and one back down.  It requires enough scratch memory to store the path from the query node to the root (in the above pseudocode, the path is implicitly represented using the call stack).  This can be decreased to a constant amount of memory by performing both passes in the same direction.  The constant memory implementation walks from the query node to the root twice, once to find the root and once to update pointers:

 '''function''' Find(''x'') '''is'''
     ''root'' := ''x''
     '''while''' ''root''.parent ≠ ''root'' '''do'''
         ''root'' := ''root''.parent
     '''end while'''
 
     '''while''' ''x''.parent ≠ ''root'' '''do'''
         ''parent'' := ''x''.parent
         ''x''.parent := ''root''
         ''x'' := ''parent''
     '''end while'''
 
     '''return''' ''root''
 '''end function'''

[[Robert E. Tarjan|Tarjan]] and [[Jan van Leeuwen|Van Leeuwen]] also developed one-pass <code>Find</code> algorithms that retain the same worst-case complexity but are more efficient in practice.<ref name="Tarjan1984"/>  These are called path splitting and path halving.  Both of these update the parent pointers of nodes on the path between the query node and the root.  '''Path splitting''' replaces every parent pointer on that path by a pointer to the node's grandparent:

 '''function''' Find(''x'') '''is'''
     '''while''' ''x''.parent ≠ ''x'' '''do'''
         (''x'', ''x''.parent) := (''x''.parent, ''x''.parent.parent)
     '''end while'''
     '''return''' ''x''
 '''end function'''

'''Path halving''' works similarly but replaces only every other parent pointer:

 '''function''' Find(''x'') '''is'''
     '''while''' ''x''.parent ≠ ''x'' '''do'''
         ''x''.parent := ''x''.parent.parent
         ''x'' := ''x''.parent
     '''end while'''
     '''return''' ''x''
 '''end function'''