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.
Discrete Mathematics & Theoretical Computer Science