Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/hal-00958992
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Thursday, March 13, 2014 - 4:59:23 PM
Last modification on : Thursday, August 1, 2019 - 2:12:40 PM
Long-term archiving on: : Friday, June 13, 2014 - 12:09:09 PM

File

dm060107.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

129

Files downloads

816