Charles Knessl - Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees

dmtcs:319 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, Vol. 6 no. 1 - https://doi.org/10.46298/dmtcs.319
Numerical Studies of the Asymptotic Height Distribution in Binary Search TreesArticle

Authors: Charles Knessl 1

  • 1 Department of Mathematics, Statistics and Computer Science [Chicago]

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.


Volume: Vol. 6 no. 1
Published on: January 1, 2003
Imported on: March 26, 2015
Keywords: asymptotics,height,binary search trees,numerical analysis,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 370 times.
This article's PDF has been downloaded 270 times.