No trees in the stdlib?

[Paul Rubin]

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.