Jump interpolation search trees and symmetric binary numbers

DOI10.1016/0020-0190(87)90005-6MaRDI QIDQ1097702zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90005-6

zbMATH Keywords

data structures for searchinginterpolation search treesnumber representationssearch algorithms

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Review text

Interpolation normally needs more than one interpolation step and, consequently, one has to interpolate repetitively from intermediate positions to the intended goal. At first sight this seems to necessitate that one must be able to leap from every position in a file to most, if not all, others as is indeed the case in arrays where O(N 2) pointers are available implicitly. In files with records of variable sizes, however, it would be unrealistic, by reasons of space complexity, to provide O(N 2) pointers. But, fortunately, for an interpolation step, accuracy is required only relative to the jump size. Loosely speaking, a far reaching interpolation jump may be determined less accurately than a short one, without loss of efficiency. The purpose of this paper is to introduce particular data structures which allow efficient interpolation in this sense and which, being trees, have at the same time an affordable space complexity. These structures represent therefore an interesting class of interpolation search trees, which is quite different from the class of interpolation search trees investigated by \textit{K. Mehlhorn} and \textit{A. Tsakalidis} [Lect. Notes Comput. Sci. 194, 424-434 (1985; Zbl 0569.68050)] where the roots have degrees of O(\(\sqrt{N})\), whereas for the trees introduced here it is O(log N). Moreover the trees studied in this paper have properties which by themselves are worth mentioning. One is that the searching complexity without interpolation is 1/3(log N)(1\(+o(1))\) which is better than for most other trees investigated. Furthemore, the trees presented here bear an intimate relation to an interesting class of binary representations of integers with a minimal number of nonzero digits.

Recommendations

• scientific article; zbMATH DE number 1103060
• Binary jumbled pattern matching on trees and tree-like structures
• Binary jumbled pattern matching on trees and tree-like structures
• On the average profile of symmetric digital search trees
• External profile of symmetric digital search trees (extended abstract)
• scientific article; zbMATH DE number 2013191
• A new representation of binary search trees
• Interpolation-binary search
• The algebra of binary search trees
• Binary search trees of almost optimal height

Cites work

• An algorithmic and complexity analysis of interpolation search
• scientific article; zbMATH DE number 3909753 (Why is no real title available?)
• scientific article; zbMATH DE number 3731331 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Interpolation search—a log log N search
• Number Systems and Arithmetic
• Understanding the complexity of interpolation search

Cited in

(2)

• On -greedy expansions of numbers
• Parallel algorithms for power circuits and the word problem of the Baumslag group

This page was built for publication: Jump interpolation search trees and symmetric binary numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1097702)