zbMATH — the first resource for mathematics

An implicit data structure supporting insertion, deletion, and search in \(O(\log ^ 2\,n)\) time. (English) Zbl 0625.68044
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(\log^ 2 n)\) time while using only the storage needed for the data.

68P10 Searching and sorting
Full Text: DOI
[1] Adel’son-Vel’skiǐ, G.M.; Landis, Y.M., An algorithm for the organization of information, Dokf akad. nauk. SSSR, 146, 263-266, (1962)
[2] Floyd, R.W., Algorithm 245: treesort 3, Comm. ACM, 7, 701, (1964)
[3] Frederickson, G.N., Self organizing heuristics for implicit data structures, SIAM J. comput., 13, 277-291, (1984) · Zbl 0539.68053
[4] Frederickson, G.N., Recursively rotated orders and implicit data structures: A lower bound, Theoret. comput. sci., 29, 75-85, (1985) · Zbl 0537.68060
[5] Frederickson, G.N., Implicit data structures for the dictionary problem, J. assoc. comput. Mach., 30, No 1, 80-94, (1983) · Zbl 0497.68032
[6] Munro, J.I.; Munro, J.I., An implicit data structure for the dictionary problem that runs in polylog time, (), 369-374, Expanded version · Zbl 1130.90361
[7] Munro, J.I.; Suwanda, H., Implicit data structures for fast search and update, J. comput. system sci., 21, 236-250, (1980) · Zbl 0446.68045
[8] Munro, J.I.; Poblete, P.V., Searchability in merging and implicit data structures, (), 527-535 · Zbl 0522.68029
[9] Williams, J.W.J., Algorithm 232: heapsort, Comm. ACM, 7, 347-348, (1964)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.