Efficient binary search tree stored in a flat array?

[Douglas Alan]

I wrote:

> On Jul 14, 8:10 am, Piet van Oostrum <p... at cs.uu.nl> 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 why is this a problem?

Oh, I'm sorry -- I see what you are saying now. You're saying you can
just implement a normal binary search tree, but store the tree nodes
in an array, as if it were a chunk of memory, and use array indices as
pointers, rather than using memory addresses as pointers.

Fair enough, but I'm not sure what that would buy you. Other than,
perhaps some improved locality of reference, and the potential to
perhaps get the pointers take up less space if you know the array is
never going to grow to be very large.

|>ouglas