On Fri, Jun 26, 2009 at 12:09 AM, João Valverde<backu...@netcabo.pt> 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
Linked list?! Python lists are *array-based*. <"You must be new here" joke redacted> Cheers, Chris -- http://blog.rebertia.com -- http://mail.python.org/mailman/listinfo/python-list
