Raymond Hettinger <pyt...@rcn.com> writes:
> Can you give an example of a list of trees and a cmp function
> that recursively compares them?
Example of list of trees (nested dicts). In practice you could get
such a list from the simplejson module:
list_of_trees = [{'value':1, 'left':{'value':3,'left':None,'right':None},
'right':{'value':7,'left':{'value':5, ...}}},
{'value':19, 'left':{'value':23', ...}},
...
]
Example comparison function:
def compare(tree1, tree2):
c = cmp(tree1['value'], tree2['value'])
if c != 0: return c
c = cmp(tree1['left'], tree2['left'])
if c != 0: return c
return cmp(tree1['right'], tree2['right])
> Are the trees user defined classes?
Not in general. They might be nested tuples, lists, or dictionaries.
Or they could come from a non-extensible library-defined class, like
from cElementTree.
> From the sound of it, the trees are static during the sort and
> would get a nice O(n log n) --> O(n) speed-up if a key function
> were allowed to flatten them in a single pass.
But the key function has to do all those comparisons on the internal
nodes.
--
http://mail.python.org/mailman/listinfo/python-list
