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 work on the tree where each node has N children.

In my case each node has a unique identifier. i want to deduce an identifier of father node from the child identifier.

So, we can add an information on child identifier to deduce that for example: if the father's node is "123", the child node is "123.3" and then we deduce that the father of (123.3) is "123". but there is a problem where we have a large tree, then a node identifier can be "12.3.4.1.2.4.5...", not be a good solution.

What would be the best approach to generate a child identifier with a simple number and then deduce the father identifier (considering that it is unique in the entire tree)?

share|improve this question
add comment

4 Answers

If $N$ is given and fixed (or at least a maximum) throughout the tree, you can just write the numbers in base $N$, which is not too different from your example. The root is $0$, the children of node $n$ are $nN+0$ through $nN+n-1$. Then to find the father of a given node $k$, you take $\lfloor \frac kN \rfloor$. It saves all the periods, so the identifiers are shorter.

share|improve this answer
    
So the first child of node $0$ is node $0$? –  Marc van Leeuwen Oct 3 '12 at 14:30
1  
To avoid parent(0)=0, use $\lfloor \frac{k-1}N\rfloor$ as parent function. Then parent(0)=-1 is understood as NULL, whereas the $N$ nodes $1,\ldots, N$ have 0 as parent. –  Hagen von Eitzen Oct 3 '12 at 14:41
    
@HagenvonEitzen: Good point. Yyou also need to make the children of node $n$ be $nN+1$ through $nN+N$. –  Ross Millikan Oct 3 '12 at 15:55
    
@RossMillikan: I confess that i dont undertand good your method. So, if i take an example. We suppose that N= 10, i have a root with two child {Node(2), Node(3)}, the child with an identifier 2 has a three children. so i can create a children to with identifiers 3 (nN+1) throught 12 (nN+N). and in this case i have two nodes with the same identifier, one with identifier 3 a child of root and another with identifier 3 a child of Node(2). they are not unique in all tree ! no ? –  user15992 Oct 3 '12 at 18:16
1  
Usually the max number of children is hight, thus if I choose N hight, the identifier's lenght will grow very much at each level ! –  user15992 Oct 3 '12 at 18:34
show 3 more comments

You could just do a sequence of number of lenght $r$, where $r$ is the generation of children you are at and the digit at position $k\leq r$ refers to the ancestor of this childrend at generation $k$ . So your first generation children are labeled $1,2,3,4\ldots,N$, the second generation are $11,12,13,\ldots, 1N,21,22,\ldots, N1,N2,\ldots, NN$ and so on for the next generations.

share|improve this answer
    
And if this is an order-128 tree? This is a good answer for most of your simpler trees; binary, quaternary, etc. But, beyond order 9 this system won't produce a decimal number, beyond order 16 it becomes difficult to convert to decimal, and beyond order 36 it becomes difficult to even represent the value of a single "digit" as you have run out of numbers and Latin letters to use. –  KeithS Oct 3 '12 at 14:35
add comment

A very simple solution (it is easy to find a mathematical procedure for that, I just don't have time at the moment) would be to append a zero to the father's number, then append the child's number.

For example, if the father's number is 123, and the child's is 67, let the child be identified by 123067. If the child has again a child with number 3298, this grandchild can be identified by 12306703298. And so on.

share|improve this answer
    
Is 10101 the first child of the first child of 1 or the 101st child of 1 or the first child of 101? –  Hagen von Eitzen Oct 3 '12 at 14:36
    
Thanks, I didn't think about that. The procedure needs to be modified then. –  Martin Oct 3 '12 at 14:38
    
You could use zero-padding similarly to this, but the padding would have to produce a fixed-length string of digits; it's much the same idea as my answer. –  KeithS Oct 3 '12 at 14:39
    
It would be nice to have an algorithm that is independent of $N$, much like adding periods as mentioned by OP. So an alternative could be: (1) convert the number to binary (2) concatenate a "2", symbolizing a switch of generation (3) concatenate the number of the child, converted to binary (4) etc. –  Martin Oct 3 '12 at 14:46
add comment

First, calculate $ceil(log_2(N))$. This number will be the number of bits required to store any number from 0 to N.

Then, simply concatenate, either by prepending or appending, each child's numeric index to the parent's identifier using N bits, and then turn the entire byte series into a decimal number. The root node should be node 1 of the first generation, so when the node identifier is 1 you know you're at the base of the tree.

Appending would make it easier to determine the parent (bit-shift N bits to the right), but would make it more difficult to perform certain other tasks. Prepending would make it trivial to determine the root or any sub-branch containing a particular child (rightmost N bits of child identifier), but finding the immediate parent of the child becomes harder. Depends on how you want to traverse the tree. Either way, each number produced at every level of the tree should be unique because at any generation, the unique identifier is produced as a function of that unique "branch" of the tree, and no other branch can produce exactly the same values for all bits of the identifier.

share|improve this answer
add comment

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.