Efficient binary search tree stored in a flat array?

[Aahz]

In article <ae6c3191-1167-43eb-9d36-23c7c49b5876 at l28g2000vba.googlegroups.com>,
Douglas Alan  <darkwater42 at gmail.com> wrote:
>
>I couldn't find a good algorithms forum on the Internet, so I guess
>I'll ask this question here instead: Is it possible to efficiently
>maintain a binary search tree in a flat array (i.e., without using
>pointers), as is typically done for a binary heap?
>
>It *is* possible, of course, to keep an ordered list in a flat array,
>and then do a binary search on the ordered array, but then insertion
>and deletion are O(n), rather than O(log n). 

Still, unless your list is large (more than thousands of elements),
that's the way you should go.  See the bisect module.  Thing is, the
speed difference between C and Python means the constant for insertion
and deletion is very very small relative to bytecode speed.  Keep in
mind that Python's object/binding model means that you're shuffling
pointers in the list rather than items.
-- 
Aahz (aahz at pythoncraft.com)           <*>         http://www.pythoncraft.com/

"If you think it's expensive to hire a professional to do the job, wait
until you hire an amateur."  --Red Adair