Digital search trees with m trees: Level polynomials and insertion costs
Helmut Prodinger
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 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