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

Authors: Prodinger, Helmut

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.


Source : oai:HAL:hal-00990489v1
Volume: Vol. 13 no. 3
Section: Analysis of Algorithms
Published on: August 30, 2011
Submitted on: June 23, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Browsing statistics

This page has been seen 197 times.
This article's PDF has been downloaded 48 times.