No trees in the stdlib?

[Steven D'Aprano]

On Fri, 03 Jul 2009 20:08:20 +1200, Lawrence D'Oliveiro wrote:

> In message <mailman.2446.1246491262.8015.python-list at python.org>, João
> Valverde wrote:
> 
>> Lawrence D'Oliveiro wrote:
[...]
>>> Want sorted order?
>>>
>>>     sorted(tuple(the_set))
>>>
>>> What could be simpler?
>> 
>> Try putting that inside a loop with thousands of iterations and you'll
>> see what the problem is.
> 
> You could apply the same argument to anything. E.g. why create a tree
> structure with a million elements? Try putting that inside a loop with
> thousands of iterations and you'll see what the problem is.

The difference is, it's vanishingly rare to want to build a tree with 
millions of elements thousands of times over and over again, but it is 
not unreasonable to want to access sorted data thousands of times. 
Needing to re-sort it over and over and over again is wasteful, slow and 
stupid. Binary trees were invented, in part, specifically to solve this 
use-case.



-- 
Steven