Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm sorry if this is the wrong one, was unsure if this was computer science, programming, or mathematics related. I'm going with mathematics because it is semi-graph theory related.

I have a tree with n-child nodes attached to each parent, and I know the indices of each node. Would the appropriate way to determine the parent be

floor((i-1)/n)?

Where i is the index of the new node being added, one to handle the offset of starting at 0 as the root, and n being the number of children allowed per parent.

I know that this holds true for n=2, and from testing it works for n=3, and n=4, but I would like to make absolute certain that it is correct.

share|improve this question
    
yeah (i-1)/n, lemme fix that –  CBredlow Dec 20 '13 at 19:28

2 Answers 2

up vote 1 down vote accepted

Yes, assuming that the tree's root is numbered zero and children are numbered sequentially by levels. Then, the children of node $x$ have numbers $$nx+1, nx+2, nx+3, \ldots, nx+n$$ and, in the other direction, parent of node $x$ has number $$\mathrm{floor}\left(\frac{x-1}{n}\right)$$

share|improve this answer

Something like that is going to work. Whether subtracting one before dividing is exactly the right thing to do, and which rounding to use, depends on whether your indices are 0-based or 1-based and so forth.

It's probably not worth it to try to figure out the right thing to do from first principles -- just guessing and then verifying that your formula gives the right result for the first few layers for $n=2$ up to $4$ should give you a very high certainty that there aren't any fencepost errors hiding anywhere.

share|improve this answer
    
Sorry, this is assuming indices are 0-based. And for n=4, I picked a few random numbers, like 97, 256, and 1000 to see if it worked. I would've went higher, but I had a hard time drawing the tree to that level. –  CBredlow Dec 20 '13 at 19:38
    
@CBredlow: I would suggest checking all nodes in the first two or three levels of the tree. If it works for all those, there won't be any differences higher up. –  Henning Makholm Dec 20 '13 at 19:41

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.