Re: Why 'Flat is better than nested'

Discussion in 'Python' started by Terry Reedy, Aug 1, 2012.

  1. Terry Reedy

    Terry Reedy Guest

    On 7/31/2012 5:49 PM, Ian Kelly wrote:
    > On Tue, Jul 31, 2012 at 3:28 PM, Ifthikhan Nazeem <> wrote:
    >> as many as (about) 2*N - log2(N) parent child relationships
    >>
    >> I would like to know how did you come up with the above formula? Forgive my
    >> ignorance.


    By non-rigorous experimentation, which did not quite count everything.

    > I come up with 2N - 2 myself. If there are N leaf nodes and N - 1
    > non-leaf nodes, then there are 2N - 1 total nodes, each of which has
    > one parent except for the root. That's 2N - 2 parent-child
    > relationships.


    That looks right. I was trying to think recursively, which in this case
    is more rather than less complicated. That actually sharpens my original
    point. N-1 new nodes and 2N-2 new relationships is 3N-3 new entities.

    The internal node limit of N-1 only applies to full-proper-strict binary
    trees without one-child internal nodes. Otherwise, a single leaf node
    could have an indefinite number of ancestors.

    from https://en.wikipedia.org/wiki/Binary_tree
    "A full binary tree (sometimes proper binary tree or 2-tree or strictly
    binary tree) is a tree in which every node other than the leaves has two
    children."

    --
    Terry Jan Reedy
    Terry Reedy, Aug 1, 2012
    #1
    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. Mr. SweatyFinger
    Replies:
    2
    Views:
    1,766
    Smokey Grindel
    Dec 2, 2006
  2. Peter Bencsik
    Replies:
    2
    Views:
    813
  3. kj
    Replies:
    53
    Views:
    2,463
    alex23
    Nov 10, 2010
  4. Terry Reedy

    Why 'Flat is better than nested'

    Terry Reedy, Jul 31, 2012, in forum: Python
    Replies:
    0
    Views:
    151
    Terry Reedy
    Jul 31, 2012
  5. Ian Kelly

    Re: Why 'Flat is better than nested'

    Ian Kelly, Jul 31, 2012, in forum: Python
    Replies:
    0
    Views:
    142
    Ian Kelly
    Jul 31, 2012
Loading...

Share This Page