In article <(E-Mail Removed)>,

Douglas Alan <(E-Mail Removed)> 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 ((E-Mail Removed)) <*>

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