OT: Binary tree logarithms properties

[Mr.SpOOn]

Hi,
I'm searching for a clear explanation of binary tree properties,
expecially the ones related to logarithms.

For example, I know that in a tree with 2n-1 nodes, we have log(n)
levels, from 0 to log(n).
So, if k is the level, the nodes on a level have indexes between 2^k
and 2^(k+1)-1.

For k=0 we have 2 and 3.
For k=1 we have 4, 5, 6, 7
and so on.

I know this after I studied some exercises on my book. Anyway there is
no explanation or demonstration of these properties.

I know this is not the better place to ask (or maybe it is?), but
maybe someone can point me to something useful.

Thanks,
bye

[Terry Reedy]

Mr.SpOOn wrote:
> Hi,
> I'm searching for a clear explanation of binary tree properties,
> expecially the ones related to logarithms.
>
> For example, I know that in a tree with 2n-1 nodes, we have log(n)
> levels, from 0 to log(n).

A *complete* binary tree with n levels has 2**n - 1 nodes. This is
easily shown by induction. (Try Wikipedia for induction proof if you are
not familiar with such.)

> So, if k is the level, the nodes on a level have indexes between 2^k
> and 2^(k+1)-1.
>
> For k=0 we have 2 and 3.
> For k=1 we have 4, 5, 6, 7
> and so on.

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.

Terry Jan Reedy

[Mr.SpOOn]

2008/12/17 Terry Reedy <tjr...@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.

[Aaron Brady]

On Dec 18, 4:34 am, Mr.SpOOn <mr.spoo...@gmail.com> wrote:
> 2008/12/17 Terry Reedy <tjre...@udel.edu>:

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