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.











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)