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

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 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.1--7
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990489
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:39:22
Dernière modification le : jeudi 7 septembre 2017 - 01:03:36
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:15:02

Fichier

2000-6434-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990489, version 1

Collections

Citation

Helmut Prodinger. Digital search trees with m trees: Level polynomials and insertion costs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.1--7. 〈hal-00990489〉

Partager

Métriques

Consultations de la notice

53

Téléchargements de fichiers

264