Balanced trees

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


On Tue, Mar 18, 2014 at 12:26 PM, Dan Stromberg <drsalists at gmail.com> 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: <http://mail.python.org/pipermail/python-list/attachments/20140318/7f955dcb/attachment.html>


More information about the Python-list mailing list