Efficient binary search tree stored in a flat array?

[Douglas Alan]

I couldn't find a good algorithms forum on the Internet, so I guess
I'll ask this question here instead: Is it possible to efficiently
maintain a binary search tree in a flat array (i.e., without using
pointers), as is typically done for a binary heap?

It *is* possible, of course, to keep an ordered list in a flat array,
and then do a binary search on the ordered array, but then insertion
and deletion are O(n), rather than O(log n). It would also clearly be
possible to store a balanced binary tree in a flat array, storing the
children of the node at index i at indices 2*i and 2*i + 1, just as
one does for a binary heap. But if you do that, I don't know if you
could then do insertions and deletions in O(log n) time.

One idea that came to mind, is that maybe it is possible using a
"treap", which is a combination of a binary heap and a binary search
tree. Insertions and deletions in binary heaps can be done in O(log n)
in a flat array, but I don't know if this is also true for a treap,
since you also have the binary search tree invariants to maintain, in
addition to the binary heap invariants. For all I know, this might
cause rotations to no longer be O(log n).

|>ouglas