Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: Why 'Flat is better than nested'

Reply
Thread Tools

Re: Why 'Flat is better than nested'

 
 
Terry Reedy
Guest
Posts: n/a
 
      07-31-2012
On 7/31/2012 5:49 PM, Ian Kelly wrote:
> On Tue, Jul 31, 2012 at 3:28 PM, Ifthikhan Nazeem <(E-Mail Removed)> 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



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Is a blank at the end of a C file a better style than a newline atthe end of the file or is it better to place none? Jimmy C Programming 3 09-09-2011 10:36 PM
GL2 better than the XLs? Consumer grade HDs better than pro-sumer Mini DVs? dh@. DVD Video 1 08-28-2008 07:20 PM
findcontrol("PlaceHolderPrice") why why why why why why why why why why why Mr. SweatyFinger ASP .Net 2 12-02-2006 03:46 PM
Is splint really better than lint? Is there a better tool than splint? Peter Bencsik C Programming 2 09-21-2006 10:02 PM
Build a Better Blair (like Build a Better Bush, only better) Kenny Computer Support 0 05-06-2005 04:50 AM



Advertisments