Left and right length of paths in binary trees or on a question of Knuth

Abstract : We consider extended binary trees and study the common right and left depth of leaf $j$, where the leaves are labelled from left to right by $0, 1, \ldots, n$, and the common right and left external pathlength of binary trees of size $n$. Under the random tree model, i.e., the Catalan model, we characterize the common limiting distribution of the suitably scaled left depth and the difference between the right and the left depth of leaf $j$ in a random size-$n$ binary tree when $j \sim \rho n$ with $0< \rho < 1$, as well as the common limiting distribution of the suitably scaled left external pathlength and the difference between the right and the left external pathlength of a random size-$n$ binary tree.
Type de document :
Communication dans un congrès
Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.415-418, 2006, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01184699
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 17 août 2015 - 16:06:12
Dernière modification le : mercredi 10 mai 2017 - 17:40:29
Document(s) archivé(s) le : mercredi 18 novembre 2015 - 12:08:10

Fichier

dmAG0136.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184699, version 1

Collections

Citation

Alois Panholzer. Left and right length of paths in binary trees or on a question of Knuth. Chassaing, Philippe and others. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 2006, Nancy, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, pp.415-418, 2006, DMTCS Proceedings. 〈hal-01184699〉

Partager

Métriques

Consultations de la notice

225

Téléchargements de fichiers

69