Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.91-100
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00958992
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 13 mars 2014 - 16:59:23
Dernière modification le : mercredi 29 novembre 2017 - 10:26:23
Document(s) archivé(s) le : vendredi 13 juin 2014 - 12:09:09

Fichier

dm060107.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00958992, version 1

Collections

Citation

Charles Knessl. Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2003, 6 (1), pp.91-100. 〈hal-00958992〉

Partager

Métriques

Consultations de la notice

89

Téléchargements de fichiers

157