No trees in the stdlib?

[Jason Scheirer]

On Jun 25, 10:32 pm, a... at pythoncraft.com (Aahz) wrote:
> In article <mailman.2139.1245994218.8015.python-l... at python.org>,
> Tom Reed  <tomree... at gmail.com> 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 pythoncraft.com)           <*>        http://www.pythoncraft.com/
>
> "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.