Re: OT: Binary tree logarithms properties

Discussion in 'Python' started by Mr.SpOOn, Dec 18, 2008.

1. Mr.SpOOnGuest

2008/12/17 Terry Reedy <>:
> Nodes only have single number indexes if you arrange them linearly. Then the
> index depends on how you arrange them, whether you start the array indexes
> with 0 or 1, and whether you start the level numbers with 0 or 1. Call the
> breadth-first sequence bf. Then the 1-based slice for 1-first level k is
> bf[2**(k-1):2**k)]. Again, proof by induction.

Yes, I was referring to the heap numeration.
Anyway, Francesco Guerrieri answered me in a private message and
explained me the formula.

But actually I was searching for other similar properties.

Mr.SpOOn, Dec 18, 2008

On Dec 18, 4:34 am, Mr.SpOOn <> wrote:
> 2008/12/17 Terry Reedy <>:
>
> > Nodes only have single number indexes if you arrange them linearly. Then the
> > index depends on how you arrange them, whether you start the array indexes
> > with 0 or 1, and whether you start the level numbers with 0 or 1.  Call the
> > breadth-first sequence bf.  Then the 1-based slice for 1-first level k is
> > bf[2**(k-1):2**k)].  Again, proof by induction.

>
> Yes, I was referring to the heap numeration.
> Anyway, Francesco Guerrieri answered me in a private message and
> explained me the formula.
>
> But actually I was searching for other similar properties.

A tree with one node A, can have two children

A CD

C and D can each have two children

A CD EF GH

Taking 'x' to be the level number, each level can have 2**x members.
Each member is a child of the higher level. You see the pattern, 1,
2, 4... then 8, 16, etc.

The total number of nodes at a level is 2**x plus its earlier levels.

2**x + 2**(x-1) + ... + 2**0.

= 2**(x+1) - 1.

Taking the log2 of both sides, we have:

log2 count_of_nodes = log2( 2**(x+1) - 1 )

Better yet:

log2 ( count_of_nodes + 1 ) = log2( 2**(x+1) )
log2 ( count_of_nodes + 1 ) = x+1