No trees in the stdlib?

Stefan Behnel stefan_ml at
Fri Jun 26 15:14:25 EDT 2009

João Valverde wrote:
> What's lacking is an associative array that preserves ordering, doesn't
> require a hash function and has fast insertions and deletions in
> O(log(n)).
> [...]
> I'm genuinely surprised to know
> there are no data structures that efficiently support such a common need
> in Python.

That's because it's simply not that a common need (in the sense that there
isn't a suitable alternative). I know that Trees have their use cases where
they really shine, but in surprisingly many cases a dict, a set, a list or
a combination of them will do just fine. And if you find a case where those
just don't fit, you may need a database anyway.


More information about the Python-list mailing list