Helmut Prodinger - Digital search trees with m trees: Level polynomials and insertion costs

dmtcs:557 - Discrete Mathematics & Theoretical Computer Science, August 30, 2011, Vol. 13 no. 3 - https://doi.org/10.46298/dmtcs.557
Digital search trees with m trees: Level polynomials and insertion costsArticle

Authors: Helmut Prodinger 1

  • 1 Department of Mathematical Sciences [Matieland, Stellenbosch Uni.]

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.


Volume: Vol. 13 no. 3
Section: Analysis of Algorithms
Published on: August 30, 2011
Accepted on: June 9, 2015
Submitted on: June 23, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 745 times.
This article's PDF has been downloaded 308 times.