# Pseudo-Distances within a depth-determination problem

1. Nov 16, 2008

### Shaitan00

I was given the following problem description for a depth-determination problem, however I am completly unable to figure out how this "pseudo-distance" feature works, if anyone has any clues and can provide a uber-simple example it would be much appreciated - I just can't see how it works/applies.

[Problem]
In the depth-determination problem, we maintain a forest F = {Ti} of rooted trees. We use the disjoint-set forest S=Si, where each set Si (which is itself a tree) corresponds to a tree Ti in the forest F. The tree structure within a set Si, however, does not necessarily correspond to that of Ti. In fact, the implementation of Si does not record the exact parent-child relationships but nevertheless allows us to determine any node’s depth in Ti.

The key idea is to maintain each node v a ”pseudo-distance” d[v], which is defined so that the sum of the pseudo-distances along the path from v to the root of its set Si equals the depth of v in Ti. That is, if the path from v to its root in v0 , v1 , . . . , vk , where v0 = v and vk is Si’s root, then the depth of v in Ti is the sum of d[vj] where j=0 to j=k.

2. Nov 16, 2008

### mathmate

The definition of "pseudo-distance" seems to be recursive here. Could you check the wording of the question?

3. Nov 16, 2008

### Shaitan00

Very possible that is it recursive - because the wording is copy/paste from the problem statement - I just don't see how it works...

If Si is a subtree of Ti (but they don't necessarily have the same root) then how can d[v] in Si allow you to calculate the depth it Ti? Or am I looking at this completly wrong?

Thanks,

4. Nov 16, 2008

### mathmate

It is common to have a recursive algorithm. But a definition that is recursive would not help the cause of defining or explaining something.
For example:
"A rectangle is a rectangle that has opposite sides parallel and adjacent side perpendicular to each other."
is a faulty definition.

5. Nov 16, 2008

### Shaitan00

I see your point - but this is given in the textbook, not sure how else to interpret it...

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook