Email Gateway (Aug 22 2022 at 15:20): Email Gateway (Aug 22 2022 at 15:20):From: Tobias Nipkow <nipkow@in.tum.de>
Expected Shape of Random Binary Search Trees
Manuel Eberl
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.
https://www.isa-afp.org/entries/Random_BSTs.shtml
Enjoy!
smime.p7s
Last updated: Apr 24 2024 at 04:17 UTC