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

Robert Kern rkern at ucsd.edu
Sun Jun 5 02:30:19 CEST 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