The total path length of split trees

Nicolas Broutin 1, 2 Cecilia Holmgren 2
2 ALGORITHMS - Algorithms
Inria Paris-Rocquencourt
Abstract : We consider the model of random trees introduced by Devroye [SIAM J. Comput. 28 (1999) 409-432]. The model encompasses many important randomized algorithms and data structures. The pieces of data (items) are stored in a randomized fashion in the nodes of a tree. The total path length (sum of depths of the items) is a natural measure of the efficiency of the algorithm/data structure. Using renewal theory, we prove convergence in distribution of the total path length toward a distribution characterized uniquely by a fixed point equation. Our result covers, using a unified approach, many data structures such as binary search trees, m-ary search trees, quad trees, median-of-(2k+1) trees, and simplex trees.
Type de document :
Article dans une revue
Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2012, 22 (5), pp.1745-1777. 〈10.1214/11-AAP812〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00773367
Contributeur : Nicolas Broutin <>
Soumis le : dimanche 13 janvier 2013 - 16:07:23
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Nicolas Broutin, Cecilia Holmgren. The total path length of split trees. Annals of Applied Probability, Institute of Mathematical Statistics (IMS), 2012, 22 (5), pp.1745-1777. 〈10.1214/11-AAP812〉. 〈hal-00773367〉

Partager

Métriques

Consultations de la notice

233