Efficient binary search tree stored in a flat array?

[Paul Rubin]

Douglas Alan <darkwater42 at gmail.com> writes:
> 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.

Probably not.  Maybe you could organize a 2-3 tree like that, at the
expense of some space.