No trees in the stdlib?

[Paul Rubin]

Stefan Behnel <stefan_ml at behnel.de> writes:
> > But deletes in an AVL tree should not cause mutation.  They should
> > just allocate a new root and path up to where the deleted node was.
> I doubt that there are many AVL implementations that do that. Plus, if
> deletion doesn't delete, I'd happily consider that a bug.

I've never seen one that DIDN'T do that, but maybe it's just the crowd
I hang out with.

See "Purely Functional Data Structures" by Chris Okasaki for more
detailed descriptions of such methods.