No trees in the stdlib?
nobody at nowhere.com
Mon Jun 29 04:59:54 EDT 2009
On Sun, 28 Jun 2009 20:54:11 -0700, Paul Rubin wrote:
> 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?
>> 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.
More information about the Python-list