Efficient Insertion of Approximately Sorted Sequences of Items into a Dictionary

摘要

In this paper a new data structure is introduced for the effi-cient on-line insertion of a sequence S of keys into a dictionary. The data structure takes advantage by the presence in S of subsets of adjacent keys which maintain their adjacency in the dictionary too, supporting the insertion of t keys in O(plogs + (t — p)) worst case time and O(a) worst case space, where s is the size of the dictionary andp is the number of such subsets. Some applications, as specified in the paper, specifically require for this property.