Is there a data structure that supports searching, inserting, deletion in worst-case O(log n) time and that satisfies the following array implementation property: at any point in time, the data structure only occupies memory cells 1..n (or 1..O(n)) if there are n elements?Note that e.g. heaps do satisfy the property.In particular, do standard data structures such as red-black, AVL, etc. allow for such an implementation?  (And if so, why is this not discussed in standard textbooks?)(This is vaguely related to a previous question which got no answer.)
Array implementation of dictionary data structure
ds.data structures
I believe you are looking for the paper Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees by Franceschini and Grossi.