João Valverde wrote:
João Valverde wrote:
Aahz wrote:
In article <mailman.2139.1245994218.8015.python-l...@python.org>,
Tom Reed <tomree...@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
implementations
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.
I was indeed corrected on this shameful blunder, but in my defense array
based lists are implementation dependent and the case for trees can be
made on deletion.
--
http://mail.python.org/mailman/listinfo/python-list
