No trees in the stdlib?
backup95 at netcabo.pt
Mon Jun 29 07:17:01 CEST 2009
Paul Rubin wrote:
> João Valverde <backup95 at netcabo.pt> writes:
>> Could you clarify what you mean by immutable? As in... not mutable? As
>> in without supporting insertions and deletions?
>> That's has the same performance as using binary search on a sorted
>> list. What's the point of using a tree for that?
> The idea is you can accomplish the equivalent of insertion or deletion
> by allocating a new root, along with the path down to the place you
> want to insert, i.e. O(log n) operations. So instead of mutating an
> existing tree, you create a new tree that shares most of its structure
> with the old tree, and switch over to using the new tree. This
> trivially lets you maintain snapshots of old versions of the tree,
> implement an "undo" operation, have a background thread do a complex
> operation on a snapshot while the foreground thread does any number of
> update-and-replace operations, etc.
Interesting, thanks. The concept is not difficult to understand but I'm
not sure it would be preferable. A copy operation should have the same
cost as a "snapshot", undo is kind of redundant and multithreading...
don't see a compelling use that would justify it. Also the interface is
a mapping so it'd be rather nice to emulate dict's.
Have you considered how the syntax would work in Python by the way? This:
new_tree = old_tree.insert(object)
Just looks wrong. The interface should support non functional idioms too.
More information about the Python-list