No trees in the stdlib?

[Steven D'Aprano]

On Fri, 26 Jun 2009 00:09:06 -0700, Jason Scheirer wrote:

> 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 dicts require hashable keys, and are in arbitrary order. You can't 
(for example) traverse a dict in post-order. 

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.



-- 
Steven