No trees in the stdlib?

João Valverde backup95 at
Mon Jun 29 01:24:36 EDT 2009

João Valverde wrote:
> Paul Rubin wrote:
>> João Valverde <backup95 at> writes:
>>> Could you clarify what you mean by immutable? As in... not mutable? As
>>> in without supporting insertions and deletions?      
>> Correct. 
>>> 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)

Heh, that's a poor example for a mapping. But:

bst[key] = object

is even dicier for immutable structures no?

More information about the Python-list mailing list