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

Groups > comp.programming > #725 > unrolled thread

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

Back to article view | Back to comp.programming

Contents

  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

#725 — Is it possible to determine an n-ary tree nodes depth given its index?

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

So, my question is, for any full n-ary tree with total nodes N, given
an arbitrary node index based on this structure, can I determine the
nodes depth in the tree?  I don't want to have to create a tree
structure and traverse it to determine its depth as the tree may
potentially be huge.  I am hoping to model this structure on the fly
with the availability of an analytical formula, but I am not convinved
it is possible?

Thanks,

Douglas.

[toc] | [next] | [standalone]

#726

[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).

Then lg n gives depth.

-- 
[Some n00b can't tell the diff between HTML and binary:]
Why have you posted binaries to a text-only newsgroup, fuck wit?
-- Gillard Lies <oyrooloutacarbontax@gmail.com>, 18 Feb 2011 22:57 -0800 (PST)
I'll concede that my use of "binary" was obscure... incorrect if it
makes you happy.
-- Gillard Lies <oyrooloutacarbontax@gmail.com>, 19 Feb 2011 00:55 -0800 (PST)

[toc] | [prev] | [next] | [standalone]

#728

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web