### 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.

### License

BSD License

### Topics

- Computer science/Data structures
- Computer science/Algorithms/Randomized

### Session Random_BSTs

- Random_BSTs

### Depends on

- Landau Symbols
- The number of comparisons in QuickSort

### Used by

- Randomised Binary Search Trees
- Treaps

### Auto-related entries

- Pratt’s Primality Certificates

## Cite

×

Random_BSTs-AFP

    @article{Random_BSTs-AFP,
      author  = {Manuel Eberl},
      title   = {Expected Shape of Random Binary Search Trees},
      journal = {Archive of Formal Proofs},
      month   = {April},
      year    = {2017},
      note    = {\url{https://isa-afp.org/entries/Random_BSTs.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest

Older releases:

- Sep 13, 2023 : Isabelle2023
- Oct 27, 2022 : Isabelle2022
- Dec 14, 2021 : Isabelle2021-1
- Feb 23, 2021 : Isabelle2021
- Apr 20, 2020 : Isabelle2020
- Jun 11, 2019 : Isabelle2019
- Aug 16, 2018 : Isabelle2018
- Oct 10, 2017 : Isabelle2017
- Apr 4, 2017 : Isabelle2016-1