Implicit Data Structures with Fast Update (Preliminary Report)

Several new data structures for dictionaries are presented that use just one location in addition to those required for key values. The structures are generalizations of a rotated sorted list, with the best realizing a search time of 0(log n) and insert and delete times of 0(n√2/log n(log n)3/2). Similar structures are presented for a dictionary with records containing k≫1 keys, under the operations of search, partial match, insert and delete.

Authors

• Greg N. Frederickson

Keywords

• Data structures
• Dictionaries
• Computer science
• Costs
• Load Data
• Key Values
• Partial Order
• Lexicographic
• Block A
• Binary Search
• Largest Element
• Analogous Fashion
• N Log N
• Easy Exchange