3
$\begingroup$

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)?

4 Answers 4

5

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.

  • 0
    So the first child of node $0$ is node $0$?2012-10-03
  • 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.2012-10-03
  • 0
    @HagenvonEitzen: Good point. Yyou also need to make the children of node $n$ be $nN+1$ through $nN+N$.2012-10-03
  • 0
    @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 ?2012-10-03
  • 0
    @user15992: You missed multiplying the parent node by N before adding. If N=10, the children of node 2 would be 21 through 30. The children of node 3 would be 31 through 40, so there is no overlap. At the next layer, the children of 22 would be 221 through 230, the children of 23 would be 231 through 240.2012-10-03
  • 0
    Ok Ok nN it's n*N ... i throught nBaseN2012-10-03
  • 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 !2012-10-03
  • 0
    @user15992: But OP said each node has N children. This approach takes advantage of that. True, if the numbers of children vary, you will wind up wasting numbers and having longer identifiers than necessary. If you want a simple function (instead of a lookup table) going from child to parent you will need that anyway.2012-10-03
0

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.

0

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.

  • 0
    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.2012-10-03
0

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.

  • 0
    Is 10101 the first child of the first child of 1 or the 101st child of 1 or the first child of 101?2012-10-03
  • 0
    Thanks, I didn't think about that. The procedure needs to be modified then.2012-10-03
  • 0
    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.2012-10-03
  • 0
    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.2012-10-03