The Height of a Binary Search Tree: The Limiting Distribution Perspective
Author
Charles Knessl, Wojciech Szpankowski
Tech report number
CERIAS TR 2002-09
Abstract
We study the height of the binary search tree - the most fundamental data structure used for searching. We assume that the binary search tree is built from a random permutation of n elements. Under this assumption, we study the limiting distribution of the height as n approaches infinity. We show that the distribution has six asymptotic regions (scales). These correspond to different ranges of k and n where Pr{Hn <= k} is the height distribution. In the critical region (the so-called central region), where most of the probability mass is concentrated, the limiting distribution satisfies a non-linear integral equation. While we cannot solve this equation exactly, we show that both tails of the distribution are roughly of a double exponential form. From our analysis we conclude that the average height E[Hn] ~ A log n
Institution
CERIAS, Purdue University
Journal
Theoretical Computer Science
Note
Theoretical Computer Science, 2002
Publication Date
1900-01-01
Keywords
Binary search trees, limiting height distribution, saddle point method, matched asymptotics, linearization, WKB method, non-linear integral equation