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.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00073700
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 1:33:35 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Thursday, March 24, 2011 - 12:56:18 PM

Identifiers

  • 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⟩

Share

Metrics

Record views

117

Files downloads

230