No trees in the stdlib?

João Valverde backup95 at
Fri Jun 26 03:48:49 EDT 2009

Jason Scheirer wrote:
> On Jun 25, 10:32 pm, a... at (Aahz) wrote:
>> In article <mailman.2139.1245994218.8015.python-l... at>,
>> Tom Reed  <tomree... at> wrote:
>>> Why no trees in the standard library, if not as a built in? I searched
>>> the archive but couldn't find a relevant discussion. Seems like a
>>> glaring omission considering the batteries included philosophy,
>>> particularly balanced binary search trees. No interest, no good
>>> implementations, something other reason? Seems like a good fit for the
>>> collections module. Can anyone shed some light?
>> What do you want such a tree for?  Why are dicts and the bisect module
>> inadequate?  Note that there are plenty of different tree implementations
>> available from either PyPI or the Cookbook.
>> --
>> Aahz (a... at           <*>
>> "as long as we like the same operating system, things are cool." --piranha
> ...And heapq is more-or-less an emulation of a tree structure in its
> underlying model. I once wrote a binary sorted tree data structure for
> Python in C. It performed anywhere from 15-40% worse than dicts. I
> think with optimization it will only perform 10% worse than dicts at
> best.
> Oh hey maybe that is why trees aren't an emphasized part of the
> standard. They are going to be much slower than the ultra-optimized
> dicts already in the standard lib.
But a dict can't be used to implement a (sorted) table ADT.

More information about the Python-list mailing list