No trees in the stdlib?

Paul Rubin http
Sun Jun 28 23:54:11 EDT 2009


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?  

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.

This is very standard stuff.  See:

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

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



More information about the Python-list mailing list