Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Re: Why 'Flat is better than nested' (http://www.velocityreviews.com/forums/t948895-re-why-flat-is-better-than-nested.html)

 Terry Reedy 07-31-2012 11:57 PM

Re: Why 'Flat is better than nested'

On 7/31/2012 5:49 PM, Ian Kelly wrote:
> On Tue, Jul 31, 2012 at 3:28 PM, Ifthikhan Nazeem <iftecan2000@gmail.com> 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

 All times are GMT. The time now is 02:58 PM.