Sorted List (binary tree) why no built-in/module?

François Pinard pinard at iro.umontreal.ca
Sun Jun 5 04:01:39 CEST 2005


[Alex Stapleton]

> Unless I've totally missed it, there isn't a binary tree/sorted list
> type arrangement in Python.  Sometimes it might be preferable over
> using a list and calling list.sort() all the time ;)

Well, after `some_list.sort()', `some_list' is indeed a sorted list. :-)
You can use the `bisect' module after that for sorted insertion.

Lists can also be used for representing binary trees, and with a bit of
imagination, the `heapq' module might help you at keeping a binary tree
"half-sorted".  This is sometimes sufficient for some applications.  Or
else, you have to resort to "avl" tree modules, available separately!

> On a somewhat unrelated note, does anyone know how python searches
> lists when you do things list list.index(n), is it a binary search, or
> does it just scan the list?

As Python does not know if a list is sorted or not, it cannot binary
search them by default.  But you, as a programmer, know.  Then, the
`bisect' module might be helpful for binary searches.

-- 
François Pinard   http://pinard.progiciels-bpi.ca



More information about the Python-list mailing list