Balanced trees

Daniel Stutzbach stutzbach at
Tue Mar 18 21:18:40 CET 2014

On Tue, Mar 18, 2014 at 12:26 PM, Dan Stromberg <drsalists at> wrote:

> In short, blist.sorteddict didn't do that well, despite being in C.

blist.blist is written in C, but blist.sorteddict is written in Python on
top of blist.blist.  It won't perform as well as a class written entirely
in C that has similar asymptotic properties.  If the objects in the tree
are non-trivial (i.e., not a built-in type), the cost of calling the __lt__
method may be more important than the choice of blist vs. AVL tree, but I
haven't tested it.

Daniel Stutzbach
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Python-list mailing list