No trees in the stdlib?
milesck at umich.edu
Fri Jun 26 08:54:45 CEST 2009
On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:
> On Thu, Jun 25, 2009 at 10:55 PM, João Valverde<backup95 at netcabo.pt>
>> Aahz wrote:
>>> In article <mailman.2139.1245994218.8015.python-list at python.org>,
>>> Tom Reed <tomreed05 at gmail.com> wrote:
>>>> Why no trees in the standard library, if not as a built in? I
>>>> the archive but couldn't find a relevant discussion. Seems like a
>>>> omission considering the batteries included philosophy,
>>>> balanced binary search trees. No interest, no good implementations,
>>>> something other reason? Seems like a good fit for the collections
>>>> Can anyone shed some light?
>>> What do you want such a tree for? Why are dicts and the bisect
>>> inadequate? Note that there are plenty of different tree
>>> available from either PyPI or the Cookbook.
>> Simple example usage case: Insert string into data structure in
>> sorted order
>> if it doesn't exist, else retrieve it.
> That's pretty much the bisect module in a nutshell. It manipulates a
> sorted list using binary search.
With O(n) insertions and removals, though. A decent self-balancing
binary tree will generally do those in O(log n).
More information about the Python-list