OT: Binary tree logarithms properties

[Aaron Brady]

On Dec 18, 4:34 am, Mr.SpOOn <mr.spoo... at gmail.com> wrote:
> 2008/12/17 Terry Reedy <tjre... at udel.edu>:
>
> > 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