Expected Shape of Random Binary Search Trees (Q7361825)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
AFP entry Random_BSTs
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Expected Shape of Random Binary Search Trees |
AFP entry Random_BSTs |
Statements
4 April 2017
0 references
Manuel Eberl
0 references
Expected Shape of Random Binary Search Trees (English)
0 references
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.
0 references
