No trees in the stdlib?

[Daniel Stutzbach]

On Fri, Jun 26, 2009 at 1:54 AM, Miles Kaufmann <milesck at umich.edu> wrote:

> On Jun 26, 2009, at 2:23 AM, Chris Rebert wrote:
>
>> 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).


FWIW, you can get O(log**2 n) inserts and deletes by using the bisect module
on my blist extension type (http://pypi.python.org/pypi/blist/).  It's a
drop-in replacement for list(), with different asymptotic performance
characteristics.

Copying a blist is O(1), so the functional-programming types can wrap it in
non-mutating semantics if they so choose. ;)

--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20090626/b4770637/attachment-0001.html>