Find() operation for disjoint sets using "Path Halving"

Question

According to Disjoint-set_data_structure, In Union section, I have a problem understanding the implementation of Path Halving approach.

 function Find(x)
   while x.parent ≠ x
     x.parent := x.parent.parent
     x := x.parent
   return x

My first iteration looks like this :

After the first iteration, x.parent and x is pointing at same node(which should not happen).I need help with the correct flow and iteration of this function

I am confused with the 3rd and 4th lines of that function and also "Path halving makes every other node on the path point to its grandparent".

Any help will be appreciated, thanks!

Answer 1

The algorithm wokrs as follows: you start from a node x, make x point to its granparent, then move on to the granparent itself, you continue until you find the root because the parent of the root is the root itself.

Look at the picture, you are actually halving the set by transforming it into a binary tree (it's not a proper binary tree but it can represented as such).

Let's say we have a set like this:

8->7->6->5->4->3->2->1->0

where the arrow means the parent (e.g. 8->7 = the parent of 8 is 7)

Say we call Find(8)

first iteration:

x = 8
8.parent = 7

8.parent = 8.parent.parent = 7.parent = 6
x = 8.parent = 7.parent = 6

second iteration:

x = 6
6.parent = 5

6.parent = 6.parent.parent = 5.parent = 4
x = 6.parent = 5.parent = 4

and so on...