Patterns in Random Binary Search Trees

Résumé : Dans un arbre binaire de recherche (ABR) de taille~$n$ construit par insertions aléatoires, chaque motif appara{î}t avec une frequence qui est en moyenne proportionnelle à~$n$. Les déviations du cas moyen sont rares et bien quantifiées par une loi gaussienne. Les arbres à motifs exclus apparaissent avec une probabilité exponentiellement petite caractérisée en terme de fonctions de Bessel. Ces résultats étendent aux ABR des propriétés connues par ailleurs dans le cas des cha{î}nes de caractères ou des arbres obéissant aux modèles combinatoires uniformes. Ils s'appliquent à la pagination et aux arbres d'index ainsi qu'au comportement du «tri-rapide» (quicksort). Comme conséquence, plusieurs stratégies d'allocation de mémoire peuvent être précisément quantifiées. Les méthodes utilisées sont de nature analytique et reposent sur l'asymptotique de perturbation de singularités appliquée aux séries génératrices multivariées.
Type de document :
Rapport
[Research Report] RR-2997, INRIA. 1996
Liste complète des métadonnées

https://hal.inria.fr/inria-00073700
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 13:33:35
Dernière modification le : vendredi 25 mai 2018 - 12:02:02
Document(s) archivé(s) le : jeudi 24 mars 2011 - 12:56:18

Fichiers

Identifiants

  • HAL Id : inria-00073700, version 1

Collections

Citation

Philippe Flajolet, Xavier Gourdon, Conrado Martinez. Patterns in Random Binary Search Trees. [Research Report] RR-2997, INRIA. 1996. 〈inria-00073700〉

Partager

Métriques

Consultations de la notice

100

Téléchargements de fichiers

167