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.
--
http://mail.python.org/mailman/listinfo/python-list
