OT: Binary tree logarithms properties
castironpi at gmail.com
Thu Dec 18 11:52:43 CET 2008
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
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 )
log2 ( count_of_nodes + 1 ) = log2( 2**(x+1) )
log2 ( count_of_nodes + 1 ) = x+1
More information about the Python-list