Efficient binary search tree stored in a flat array?
Mon Jul 13 20:55:34 CEST 2009
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.
More information about the Python-list