No trees in the stdlib?

[Paul Rubin]

Stefan Behnel <stefan_ml at behnel.de> writes:
> > Besides some interface glitches, like returning None
> > on delete if I recall correctly.
> 
> That's actually not /that/ uncommon. Operations that change an object are
> not (side-effect free) functions, so it's just purity if they do not have a
> return value.

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.
That allows having references to the old and new versions of the tree,
etc.