No trees in the stdlib?

Terry Reedy tjreedy at udel.edu
Mon Jun 29 15:06:52 EDT 2009


Paul Rubin wrote:

> 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.

Now I get what your have been talking about over several posts.
Update and mutate are kind of synonymous in my mind, but the above 
explains how they can be different.

   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.
> 
> This is very standard stuff.

Now for someone raised on arrays, iteration, and procedural programming ;-).

>   http://en.wikipedia.org/wiki/Persistent_data_structure

Reading it now.

> 
> The wikipedia article on AVL trees makes it pretty obvious how an
> implementation would work.




More information about the Python-list mailing list