HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Digital search trees with m trees: Level polynomials and insertion costs

Abstract : We adapt a novel idea of Cichon's related to Approximate Counting to the present instance of Digital Search Trees, by using m (instead of one) such trees. We investigate the level polynomials, which have as coefficients the expected numbers of data on a given level, and the insertion costs. The level polynomials can be precisely described, thanks to formulae from q-analysis. The asymptotics of expectation and variance of the insertion cost are fairly standard these days and done with Rice's method.
Document type :
Journal articles
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 3:39:22 PM
Last modification on : Thursday, September 7, 2017 - 1:03:36 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:15:02 PM


Files produced by the author(s)




Helmut Prodinger. Digital search trees with m trees: Level polynomials and insertion costs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.1--7. ⟨10.46298/dmtcs.557⟩. ⟨hal-00990489⟩



Record views


Files downloads