Efficient binary search tree stored in a flat array?

[Piet van Oostrum]

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

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.
-- 
Piet van Oostrum <piet at cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org