No trees in the stdlib?

[Aahz]

In article <006078f0$0$9721$c3e8da3 at news.astraweb.com>,
Steven D'Aprano  <steve at REMOVE-THIS-cybersource.com.au> wrote:
>
>Hash tables (dicts) are useful for many of the same things that trees are 
>useful for, but they are different data structures with different 
>strengths and weaknesses, and different uses. To argue that we don't need 
>trees because we have dicts makes as much sense as arguing that we don't 
>need dicts because we have lists.

The problem is that trees are like standards: there are so many to choose
from.  Each has its own tradeoffs, and because Python dicts and lists can
substitute for many of the traditionals uses of trees, the tradeoffs are
less clear.  I think nobody would object to adding trees to the standard
library, but it will certainly require a clear PEP, preferably with a
pointer to an existing PyPI library that has acquired real-world use.

(In particular, WRT the bisect module, although insertion and deletion
are O(N), the constant factor for doing a simple memory move at C speed
swamps bytecode until N gets very large -- and we already have
collections.deque() for some other common use cases.)
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"as long as we like the same operating system, things are cool." --piranha