No trees in the stdlib?
daniel at stutzbachenterprises.com
Fri Jun 26 19:33:31 CEST 2009
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
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...
More information about the Python-list