Sorted List (binary tree) why no built-in/module?
pinard at iro.umontreal.ca
Sun Jun 5 04:01:39 CEST 2005
> 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