No trees in the stdlib?

João Valverde backup95 at netcabo.pt
Tue Jun 30 01:27:33 CEST 2009


alex23 wrote:
> João Valverde <backu... at netcabo.pt> wrote:
>   
>> Currently I don't have a strong need for this.
>>     
>
> And clearly neither has anyone else, hence the absence from the
> stdlib. As others have pointed out, there are alternative approaches,
> and plenty of recipes on ActiveState, which seem to have scratched
> whatever itch there is for the data structure you're advocating.
>
>   

I can't resist quoting Sedgewick here. Then I'll shut up about it.

[quote=http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf]
Abstract
The red-black tree model for implementing balanced search trees, 
introduced by Guibas and Sedge-
wick thirty years ago, is now found throughout our computational 
infrastructure. Red-black trees
are described in standard textbooks and are the underlying data 
structure for symbol-table imple-
mentations within C++, Java, Python, BSD Unix, and many other modern 
systems.
[/quote]

You'd think so, but no. You should correct him that in Python a balanced 
search tree is the useless cross between a dict and a database.




More information about the Python-list mailing list