Efficient binary search tree stored in a flat array?

[Douglas Alan]

On Jul 13, 3:57 pm, a... at pythoncraft.com (Aahz) wrote:

> 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.

Thank you. My question wasn't intended to be Python specific, though.
I am just curious for purely academic reasons about whether there is
such an algorithm. All the sources I've skimmed only seem to the
answer the question via omission. Which is kind of strange, since it
seems to me like an obvious question to ask.

If I find the free time, I might try to work out myself whether it can
be done with a treap.

|>ouglas