Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2003

Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees

Résumé

We study numerically a non-linear integral equation that arises in the study of binary search trees. If the tree is constructed from n elements, this integral equation describes the asymptotic (as n→∞) distribution of the height of the tree. This supplements some asymptotic results we recently obtained for the tails of the distribution. The asymptotic height distribution is shown to be unimodal with highly asymmetric tails.
Fichier principal
Vignette du fichier
dm060107.pdf (91.38 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00958992 , version 1 (13-03-2014)

Identifiants

Citer

Charles Knessl. Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees. Discrete Mathematics and Theoretical Computer Science, 2003, Vol. 6 no. 1 (1), pp.91-100. ⟨10.46298/dmtcs.319⟩. ⟨hal-00958992⟩

Collections

TDS-MACS
50 Consultations
691 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More