Efficient binary search tree stored in a flat array?

[Douglas Alan]

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? This is how binary heaps are typically
implemented, and it all works swimmingly. The node rotations for
keeping a binary heap balanced turn out to be suitable for
representation in a flat array. I.e., when you do the node rotations,
you only ever have to copy log n array elements.

In general, however, you can't move nodes around so easily when
represented in a flat array. A node movement in a tree represented
with pointers, might involves changing just two pointers, while when
represented as a flat array, might involve copying most of the array
to maintain the tree invariants. It just so turns out that maintaining
the invariants for a binary heap does not have this issue.

This is why I was curious about treaps, which are a type of binary
heap. The CLRS textbook on algorithms discusses treaps, but doesn't
ever mention whether they are as fortunate as less constrained binary
heaps. I'm sure I could work out for myself whether the treap
rotations are suitable for storage in a flat array, but I might make a
mistake somewhere in my reasoning, and then never know the true
answer!

|>ouglas