No trees in the stdlib?

Daniel Stutzbach daniel at
Fri Jun 26 13:33:31 EDT 2009

On Fri, Jun 26, 2009 at 1:54 AM, Miles Kaufmann <milesck at> 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 (  It's a
drop-in replacement for list(), with different asymptotic performance

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 <>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Python-list mailing list