On Sun, 28 Jun 2009 20:54:11 -0700, Paul Rubin wrote: > 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.
The main issue here is that you need to be a bit smarter when it comes to "modifying" the tree. If you want to insert, delete or replace multiple elements, using repeated insert()s (etc) on the root is sub-optimal, as you will end up repeatedly duplicating the upper levels. Ideally you want to provide operations which will add/remove/replace multiple elements in a single traversal. -- http://mail.python.org/mailman/listinfo/python-list
