Jump interpolation search trees and symmetric binary numbers (Q1097702)

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.