Abstract: |
This entry contains proofs for the textbook results about the
distributions of the height and internal path length of random binary
search trees (BSTs), i. e. BSTs that are formed by taking
an empty BST and inserting elements from a fixed set in random
order. In particular, we prove a logarithmic upper
bound on the expected height and the Θ(n log n)
closed-form solution for the expected internal path length in terms of
the harmonic numbers. We also show how the internal path length
relates to the average-case cost of a lookup in a BST. |
BibTeX: |
@article{Random_BSTs-AFP,
author = {Manuel Eberl},
title = {Expected Shape of Random Binary Search Trees},
journal = {Archive of Formal Proofs},
month = apr,
year = 2017,
note = {\url{http://isa-afp.org/entries/Random_BSTs.html},
Formal proof development},
ISSN = {2150-914x},
}
|