The Height of a Binary Search Tree: The Limiting Distribution Perspective

Get BibTex-formatted data

Download

PDF

Author

Charles Knessl, Wojciech Szpankowski

Tech report number

CERIAS TR 2002-09

Entry type

article

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

Download

PDF

Date

2002

URL

https://www.cerias.purdue.edu/papers/archive/2002-09.ps

Institution

CERIAS, Purdue University

Journal

Theoretical Computer Science

Key alpha

Knessl

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

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Article{ Knessl,
	title = "The Height of a Binary Search Tree: The Limiting Distribution Perspective",
	author = "Charles Knessl, Wojciech Szpankowski",
	year = "2002",
	institution = "CERIAS, Purdue University",
	journal = "Theoretical Computer Science",
	note = "Theoretical Computer Science, 2002",
	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 ",
	keywords = "Binary search trees, limiting height distribution, saddle point method, matched asymptotics, linearization, WKB method, non-linear integral equation",
	url = "https://www.cerias.purdue.edu/papers/archive/2002-09.ps",
}