No trees in the stdlib?
backup95 at netcabo.pt
Fri Jun 26 09:09:36 CEST 2009
João Valverde wrote:
> 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
>>> searched the archive but couldn't find a relevant discussion. Seems
>>> like a glaring omission considering the batteries included
>>> philosophy, particularly balanced binary search trees. No interest,
>>> no good implementations, something other reason? Seems like a good
>>> fit for the collections module. Can anyone shed some light?
>> What do you want such a tree for? Why are dicts and the bisect module
>> inadequate? Note that there are plenty of different tree
>> available from either PyPI or the Cookbook.
> A hash table is very different to a BST. They are both useful. The
> bisect module I'm not familiar with, I'll have to look into that, thanks.
> I have found pyavl on the web, it does the job ok, but there no
> implementations for python3 that I know of.
> Simple example usage case: Insert string into data structure in sorted
> order if it doesn't exist, else retrieve it.
After browsing the bisect module I don't think it is the complete
answer. Please correct me if I'm mistaken but...
Ignoring for a moment that subjectively I feel this is not very pythonic
for my use case, if I get back the insertion position, doesn't that mean
I have to go over on average N/2 items on a linked list to insert the
item in position? Maybe less for sophisticated implementations but still
O(n)? That doesn't compare favorably to the cost of (possibly) having to
rebalance a tree on insertion.
More information about the Python-list