On Wed, 21 Sep 2016 12:44 pm, Random832 wrote:
> On Tue, Sep 20, 2016, at 22:34, Steve D'Aprano wrote:
>> I'm afraid I don't understand this. This is a standard binary tree
>> inorder traversal. Each node is visited once, and there are N nodes,
>> so I make that out to be O(N) not O(N log N). I'm afraid I can't parse
>> your final clause:
>>
>> "since values from the leaves of the tree have to be yielded
>> multiple times to the top of the tree"
>>
>> Each leaf is yielded once, and I don't understand what you mean by
>> yielding to the top of the tree.
>
> His point is that in order for the top-level iterator to return a given
> node there's a yield call in the top level's iterator , that calls the
> next level's iterator's yield, that calls the next one, so on, in a call
> stack log(n) levels deep.
Right. That's the whole point of a binary search tree. An unbalanced binary
tree may be as deep as N, but a balanced one, or a random unbalanced one,
is only log N deep.
log N is a long way from N log N.
I don't see what is the actual problem we are being asked to solve. Is it
the stack space needed to walk the tree? The time taken? The Original
Poster said:
"O(n log n) running time"
so I don't think the O(log N) stack space used is relevant.
In a practical sense, the right way to solve this problem is to not use a
tree in the first place. But presumably the OP is using this for teaching
about trees, not as production software.
--
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.
--
https://mail.python.org/mailman/listinfo/python-list
