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
    @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
    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