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

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> (permalink)
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

Show key headers only | 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