Posted by hussein on July 25, 1999 at 19:39:26:
In Reply to: HW 9, path compression? posted by Jason Burkert on July 25, 1999 at 17:17:00:
: I'm working on HW9, and I followed the process shown on p.174 and got a tree and an array, but I realized that doesn't include any "path compression". On p.176 the figure shows an example of path compression used on a single equivalence. My question is this: Is the path compression applied in every equivalence, and if so, don't you simply end up with a tree with a depth of 2 with a root and 15 children? Or is path compression applied only at the end, after all the equivalences are processed?
not quite ... the path compression only applies during the FIND operation and not during UNION ... carefully read the definition of path compression on p175 ...
also, path compression is ONLY applied between the root and the node whose root is sought ...
---
hussein