No trees in the stdlib?
Fri Jun 26 13:25:17 EDT 2009
aahz at pythoncraft.com (Aahz) writes:
> (In particular, WRT the bisect module, although insertion and deletion
> are O(N), the constant factor for doing a simple memory move at C speed
> swamps bytecode until N gets very large -- and we already have
> collections.deque() for some other common use cases.)
Again, at least in my case, I'd hope for an immutable structure.
Also, "N very large" is likely to mean no more than a few thousand,
which is small by today's standards. And the C speed difference goes
away completely if the tree implementation is also in C.
Hedgehog Lisp has a good functional AVL tree implementation written in
C, that I might try to wrap with the Python C API sometime. I think
it is LGPL licensed though, not so good for the Python stdlib.
More information about the Python-list