An implicit data structure supporting insertion, deletion, and search in Olog2n) time

摘要

We introduce a data structure that requires only one pointer for every k data values and supports searches in O(log n) time and insertions and deletions in O(k+log n) time. By choosing k to be O(log n), pointers can be encoded into the relative order of data values and this technique can be used to support insert, delete and search in O(log2n) time while using only the storage needed for the data.