Sorted List (binary tree) why no built-in/module?
Robert Kern
rkern at ucsd.edu
Sat Jun 4 20:30:19 EDT 2005
Alex Stapleton wrote:
> Unless I've totally missed it, there isn't a binary tree/sorted list
> type arrangement in Python. Is there a particular reason for this?
> Sometimes it might be preferable over using a list and calling
> list.sort() all the time ;)
Well, I believe that list.sort() has been optimized for the case where
an item has been appended to the end of a sorted list.
Also, look at the bisect module.
> 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?
It just scans the list since there is no guarantee that it is sorted.
The bisect module has a binary search for sorted lists.
--
Robert Kern
rkern at ucsd.edu
"In the fields of hell where the grass grows high
Are the graves of dreams allowed to die."
-- Richard Harter
More information about the Python-list
mailing list