Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #728

Re: Is it possible to determine an n-ary tree nodes depth given its index?

Show all headers | View raw

kym@kymhorsell.com wrote:
) [Seems my post was killed somewhere, so trying again].
) Douglas <douglas.hanley@gmail.com> wrote:
)> I have a full n-ary tree with N nodes.  The top node is indexed 0 with
)> all other nodes indexed incrementally from left to right as we decend
)> the tree.  The last node has index N-1.  For example, a 15 node binary
)> tree would be indexed as follows:
)> 
)> 0
)> 1,2
)> 3,4,5,6
)> 7,8,9,10,11,12,13,14
) ...
)
) Why not use the usual notation of 2*n for left node of n and
) 2*n+1 for right node of n (assuming root is node 0).

Because he was asking for N-ary trees in general, not binary trees
specifically.  He just gave a binary tree as an example.

The 2*n+1, 2*n+2 way he used *can* be generalized to N-ary.
3-ary tree example: 3*n+1, 3*n+2, 3*n+3

0
1,2,3
4,5,6,7,8,9,10,11,12
13,14,15,16,...,38,39
40,41,...,119,120
121,122,...,162,163

However, a simple lg3(x+1) won't cut it in this case.
It looks like lg3(x*2+1) will work.

Now, for the general case.  The number of the leftmost node
on level X of an N-ary tree will be ((N*N+1)*N+1)... (X times),
which in closed form is (N^X-1)/(N-1), so to get the level
in the general case, the formula is logN(x*(N-1)+1).

HTH, HAND.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Is it possible to determine an n-ary tree nodes depth given its index? Douglas <douglas.hanley@gmail.com> - 2011-08-01 02:34 -0700
  Re: Is it possible to determine an n-ary tree nodes depth given its index? kym@kymhorsell.com - 2011-08-01 09:47 +0000
    Re: Is it possible to determine an n-ary tree nodes depth given its index? Willem <willem@toad.stack.nl> - 2011-08-01 11:26 +0000

csiph-web