An array of n distinct keys can be sorted for logarithmic searching or can be organized as a heap for logarithmic updating, but it is unclear how to attain logarithmic time for both searching and updating. This natural question dates back to the heap of Williams and Floyd in the sixties and relates to the fundamental issue whether additional space besides those for the keys gives more computational power in dictionaries and how data ordering helps. Implicit data structures were introduced in the eighties with this goal, providing the best bound of O(log(2) n) time. until a recent result showing O(log(2) n/log log n) time. In this paper we describe the flat implicit tree, which is the first data structure obtaining O(log n) time for search and (amortized) update using an array of n cells.
Optimal implicit dictionaries over unbounded universes / Franceschini, Gianni; Roberto, Grossi. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - STAMPA. - 39:2(2006), pp. 321-345. (Intervento presentato al convegno 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) tenutosi a EINDHOVEN, NETHERLANDS nel JUN 30-JUL 04, 2003) [10.1007/s00224-005-1167-9].
Optimal implicit dictionaries over unbounded universes
FRANCESCHINI, GIANNI;
2006
Abstract
An array of n distinct keys can be sorted for logarithmic searching or can be organized as a heap for logarithmic updating, but it is unclear how to attain logarithmic time for both searching and updating. This natural question dates back to the heap of Williams and Floyd in the sixties and relates to the fundamental issue whether additional space besides those for the keys gives more computational power in dictionaries and how data ordering helps. Implicit data structures were introduced in the eighties with this goal, providing the best bound of O(log(2) n) time. until a recent result showing O(log(2) n/log log n) time. In this paper we describe the flat implicit tree, which is the first data structure obtaining O(log n) time for search and (amortized) update using an array of n cells.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.