No trees in the stdlib?

[Nobody]

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?  
> 
> 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.