Re: OT: Binary tree logarithms properties

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

  1. Mr.SpOOn

    Mr.SpOOn Guest

    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
    #1
    1. Advertising

  2. Mr.SpOOn

    Aaron Brady Guest

    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
    Aaron Brady, Dec 18, 2008
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,079
  2. create

    logarithms PACKAGE MATH_REAL

    create, Jan 28, 2008, in forum: VHDL
    Replies:
    1
    Views:
    628
  3. Replies:
    30
    Views:
    2,646
    Arne Vajhøj
    Aug 4, 2008
  4. Mr.SpOOn
    Replies:
    0
    Views:
    275
    Mr.SpOOn
    Dec 17, 2008
  5. Konstantin Loguinov

    Logarithms

    Konstantin Loguinov, Nov 2, 2004, in forum: ASP General
    Replies:
    13
    Views:
    253
    Evertjan.
    Nov 4, 2004
Loading...

Share This Page