Efficient binary search tree stored in a flat array?

[Douglas Alan]

On Jul 14, 9:19 am, Scott David Daniels <Scott.Dani... at Acm.Org> wrote:

> It may well be that there is no good simple solution, and people avoid
> writing about non-existent algorithms.

I can't imagine why that should be the case. The CLRS textbook on
algorithms, for instance, goes to some pains to mathematically prove
that there is no comparison sort that can operate in faster than O(n
log n) time.

And any decent discussion of rabies would be sure to mention that
there is no known cure.

CLRS talks about binary heaps, binary search trees, and treaps, and it
shows how to maintain a binary heap in a flat array efficiently (n log
n time overall), but it never even seems to bring up the subject as to
whether a binary search tree or a treap can also be efficiently
maintained in a flat array.

Though it may be the case that these questions are left as exercises
for the student, and therefore buried in the exercises and problem
sets that I didn't read carefully.

> Piet van Oostrum wrote:

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

I can't see that a binary search tree would typically have
particularly good cache-friendliness, so I can't see why a flat-array
representation, such as is done for a binary heap, would have
particularly worse cache-reference.

|>ouglas