Efficient binary search tree stored in a flat array?

[Piet van Oostrum]

>>>>> Douglas Alan <darkwater42 at gmail.com> (DA) wrote:

>DA> 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?

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

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

My second sentence that you quoted more or less means `it doesn't buy
you much'. 
-- 
Piet van Oostrum <piet at cs.uu.nl>
URL: http://pietvanoostrum.com [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org