Efficient binary search tree stored in a flat array?

[Scott David Daniels]

Piet van Oostrum wrote:
>>>>>> Douglas Alan <darkwater42 at gmail.com> (DA) wrote:
> 
>> DA> 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.
> 
>> DA> Thank you. My question wasn't intended to be Python specific, though.
>> DA> I am just curious for purely academic reasons about whether there is
>> DA> such an algorithm. All the sources I've skimmed only seem to the
>> DA> answer the question via omission. Which is kind of strange, since it
>> DA> seems to me like an obvious question to ask.

It may well be that there is no good simple solution, and people avoid
writing about non-existent algorithms.  I certainly cannot imagine
trying to write an article that carefully covered ideas which don't
have well-studied data structures available, and calling them out
only to say, "we don't know how to do this well."  If such an algorithm
were simple and obvious, I dare say you'd be taught about it around the
time you learn binary search.

> Of course you can take any BST algorithm and replace pointers by indices
> in the array and allocate new elements in the array. But then you need
> array elements to contain the indices for the children explicitely.

And you loower your locality of reference (cache-friendliness).
Note the insert in Python, for example, is quite cache-friendly.

--Scott David Daniels
Scott.Daniels at Acm.Org