Balanced trees

[Ian Kelly]

On Mon, Mar 10, 2014 at 11:34 AM, Marko Rauhamaa <marko at pacujo.net> wrote:
> The main thing is there are use cases where order is essential. That's
> why I have had to implement the AVL tree in Python myself. No biggie,
> but a C implementation would probably be much faster. Also, a standard
> version would likely be reviewed and tested better and have all Pythonic
> accessors in place.

That last is actually quite easy to achieve, especially using the
built-in ABCs.  Just subclass from collections.MutableMapping and
implement __len__, __iter__, __getitem__, __setitem__ and __delitem__;
and default implementations of the rest will be mixed in for you.  Or
you can override those with optimized implementations.