Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.org!de-l.enfer-du-nord.net!feeder1.enfer-du-nord.net!cs.uu.nl!news.stack.nl!.POSTED!not-for-mail
From: Willem <willem@toad.stack.nl>
Newsgroups: comp.programming
Subject: Re: Is it possible to determine an n-ary tree nodes depth given its index?
Date: Mon, 1 Aug 2011 11:26:47 +0000 (UTC)
Organization: Stack Usenet News Service
Lines: 48
Message-ID: <slrnj3d3bn.341.willem@toad.stack.nl>
References: <fa36bcad-27a2-41ac-ad99-673672dd0a0e@y16g2000yqk.googlegroups.com> <4e36763d$0$13390$afc38c87@news.optusnet.com.au>
NNTP-Posting-Host: toad.stack.nl
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Trace: mud.stack.nl 1312198007 88347 2001:610:1108:5010::135 (1 Aug 2011 11:26:47 GMT)
X-Complaints-To: abuse@stack.nl
NNTP-Posting-Date: Mon, 1 Aug 2011 11:26:47 +0000 (UTC)
User-Agent: slrn/0.9.9p1 (FreeBSD)
Xref: x330-a1.tempe.blueboxinc.net comp.programming: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