No trees in the stdlib?

Stefan Behnel stefan_ml at
Fri Jun 26 07:37:25 EDT 2009

Paul Rubin wrote:
> Stefan Behnel 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.

I doubt that there are many AVL implementations that do that. Plus, if
deletion doesn't delete, I'd happily consider that a bug.


More information about the Python-list mailing list