scientific article; zbMATH DE number 3909753
From MaRDI portal
Publication:3686050
[For the entire collection see Zbl 0563.00018.] We present a new data structure called Interpolations Search tree (IST) 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.
Recommendations
Cited in
(10)- Interpolation-binary search
- Jump interpolation search trees and symmetric binary numbers
- Parallel processing can be harmful: The unusual behavior of interpolation search
- Dynamic interpolation search revisited
- Dynamic interpolation search
- Dynamic Interpolation Search Revisited
- scientific article; zbMATH DE number 4062609 (Why is no real title available?)
- Dynamic interpolation search in o( n) time
- scientific article; zbMATH DE number 6469186 (Why is no real title available?)
- ISB-tree: A new indexing scheme with efficient expected behaviour
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3686050)