Discrete Mathematics & Theoretical Computer Science, Vol 13, No 3 (2011)

Font Size:  Small  Medium  Large

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

Helmut Prodinger


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 formulæ from q-analysis. The asymptotics of expectation and variance of the insertion cost are fairly standard these days and done with Rice's method.

Full Text: PDF PostScript