On Tue, Sep 20, 2016 at 9:46 AM, ROGER GRAYDON CHRISTMAN <d...@psu.edu> wrote:
> 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, > since > values from the leaves of the tree have to be yielded multiple times to > the top > of the tree. > 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? 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 tree. 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 values. The downside is that inserting a new node can take a long time because, depending on the insertion point, the left and right values for each node in the tree may have to be recalculated. Now, I may have completely missed the mark here. I am completely self taught and have only been programming for about 3 years. I hope that you gleaned some value from my response either way. -- https://mail.python.org/mailman/listinfo/python-list
