Numerical Studies of the Asymptotic Height Distribution in Binary Search Trees
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2003-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/179 |
| Summary: | 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. |
|---|---|
| ISSN: | 1462-7264 1365-8050 |