DYNAMIC INTERPOLATION SEARCH

Authors
MEHLHORN K TSAKALIDIS A
Citation
K. Mehlhorn et A. Tsakalidis, DYNAMIC INTERPOLATION SEARCH, Journal of the Association for Computing Machinery, 40(3), 1993, pp. 621-634
Citations number
14
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411 → ACNP
Volume
40
Issue
3
Year of publication
1993
Pages
621 - 634
Database
ISI
SICI code
Abstract
A new data structure called interpolation search tree (IST) is present ed which supports interpolation search and insertions and deletions. A mortized insertion and deletion cost is O(log n). The expected search time in a random file is O(log log n). This is not only true for the u niform distribution but for a wide class of probability distributions.