The Variance of the Profile in Digital Search Trees

Abstract : What today we call digital search tree (DST) is Coffman and Eve's sequence tree introduced in 1970. A digital search tree is a binary tree whose ordering of nodes is based on the values of bits in the binary representation of a node's key. In fact, a digital search tree is a digital tree in which strings (keys, words) are stored directly in internal nodes. The profile of a digital search tree is a parameter that counts the number of nodes at the same distance from the root. In this paper we concentrate on external profile, i.e., the number of external nodes at level k when n strings are sorted. By assuming that the n input strings are independent and follow a (binary) memoryless source the asymptotic behaviour of the average profile was determined by Drmota and Szpankowski (2011). The purpose of the present paper is to extend their analysis and to provide a precise analysis of variance of the profile. The main (technical) difference is that we have to deal with an inhomogeneous part in a proper functional-differential equations satisfied by the second moment and Poisson variance. However, we show that the variance is asymptotically of the same order as the expected value which implies concentration. These results are derived by methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization, the saddle point method and singularity analysis.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.21--38
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00990500
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:39:36
Dernière modification le : vendredi 20 avril 2018 - 10:36:01
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:24:46

Fichier

1808-6459-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00990500, version 1

Collections

Citation

Ramin Kazemi, Mohammad Q. Vahidi-Asl. The Variance of the Profile in Digital Search Trees. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 3 (3), pp.21--38. 〈hal-00990500〉

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

184