DYNAMIC INTERPOLATION SEARCH

被引：22

作者：

MEHLHORN, K

TSAKALIDIS, A

机构：

[1] COMP TECHNOL INST,GR-26110 PATRAI,GREECE

[2] UNIV SAARLAND,FACHBEREICH INFORMAT,W-6600 SAARBRUCKEN,GERMANY

来源：

JOURNAL OF THE ACM | 1993年 / 40卷 / 03期

关键词：

ALGORITHMS; DYNAMIZATION; INTERPOLATION SEARCH; SEARCH TREE;

D O I：

10.1145/174130.174139

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A new data structure called interpolation search tree (IST) is presented which supports interpolation search and insertions and deletions. Amortized 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 uniform distribution but for a wide class of probability distributions.

引用

页码：621 / 634

页数：14

共 14 条

[1]

FRANKLIN WR, 1979, INFORM PROCESS LETT, V9, P161, DOI 10.1016/0020-0190(79)90060-7

[2] IMPLICIT DATA-STRUCTURES FOR THE DICTIONARY PROBLEM [J].