João Valverde <backu...@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. -- http://mail.python.org/mailman/listinfo/python-list
