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