On Tue, Sep 20, 2016 at 9:46 AM, ROGER GRAYDON CHRISTMAN <<a target=""
>I am trying to find a better (i.e. more efficient) way to implement a generator
that traverses a tree.
The current model of the code (which is also used by a textbook I am teaching
from does this)
   def __iter__(node):
         for x in iter(node._left):
              yield x
         yield node._value
         for x in iter(node._right)
              yield x
This is nice, simple, and straightforward, but has an O(n log n) running time,
values from the leaves of the tree have to be yielded multiple times to the top
of the tree.

Justin Walters <walters.justi...@gmail.com> responded:

> Are the left and right attributes collections of more nodes or are they 
> simply references to the node's position in the tree? 
> From the code provided it seems like the former is true and a node's left 
> attribute is a reference to another node?

They are references to other nodes, which in turn have values and left and 
right references to more nodes, etc.
as in a particular tree.  There are no 'collections' in the sense of set or map 
or Python list, just recursive sub-trees.

> I don't know how flexible you are with the structure of your tree, 
but you could try taking the modified pre-order tree traversal approach.

> This article explains it in the context of a database, but the idea is the 
> same: <https://www.sitepoint.com/hierarchical-data-database-2/> 

> Each node would then have a parent attribute as well as left and 
right attributes. The parent would be a reference to a parent node, and 
the left and right would be integers that position the element in the 

> The upside to this is that traversal and lookup is much faster 
since you do not need to have an iterator nested in an iterator. This is
 because the top level node will always have the lowest integer as it's 
left attribute and the highest integer as it's right attribute. That 
means that you can instead have a single iterator that iterates through a
 range of integers to yield the node with the specified left and right 

I am in academia, and the current unit is the binary search tree in its 
conventional sense, instead of the tabular version.
Indeed that table would be faster for iteration, but at the increased cost of 
slowing down adding and removing elements.
If I were to use any array-based model, as this database link shows, all 
insertions and deletions would be linear-time
operations instead of logarithmic time.  

I would contrast the time to insert N elements and then to traverse the tree 
once, where the N elements arrive in any order:
Tabular approach N linear-time insertions -> quadratic time plus a linear-time 
tree traversal afterwards.
Tree approach:   N logarithm-time insertions plus an iteration that takes a 
time proportional to all that -- it still wins.
Since traversal is 'rare', I don't want to penalize the common behaviors to 
accelerate this traversal.

But I would still like to see if there is a linear traversal possible with the 
help if the itertools chain

Roger Christman
Pennsylvania State University



Reply via email to