So I hope the pros and cons of this alternative approach to the union find
data structure are intuitively clear.
The win, the pro, comes in the union operation, which is now very simple.
Now you might be tempted to just say union takes constant time,
because all you do is update one pointer, It's actually not so simple, right?
Because remember you're given two objects, x and y, and
in general you're not linking x and y together.
They might be somewhere deep in a tree.
You're linking roots together.
So what is true is that the union operation reduces two
two indications of find.
You have to find x's root.
R sub 1, you have to y's root r sub 2,
and then you just do constant time linking either r1 to r 2 or vice versa.
Now the issue with this lazy union approach is that it's not at all obvious,
and in fact it's not going to be true, that find operation takes constant time.
Remember, previously when we actually did this hard work of updating all these
leader pointers every time we had a union it guaranteed that whenever there is
a find boom, we just look in the field, we return the leader pointer, we're done.
Here, parent pointers do not point directly to roots rather
you have to traverse in general a sequence of parent pointers from a given object x
to go all the way up to the root of the correspondence tree.