ON THE VARIANCE OF THE HEIGHT OF RANDOM BINARY SEARCH-TREES

Authors
DEVROYE L REED B
Citation
L. Devroye et B. Reed, ON THE VARIANCE OF THE HEIGHT OF RANDOM BINARY SEARCH-TREES, SIAM journal on computing, 24(6), 1995, pp. 1157-1162
Citations number
16
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
SIAM journal on computing → ACNP
ISSN journal
00975397
Volume
24
Issue
6
Year of publication
1995
Pages
1157 - 1162
Database
ISI
SICI code
0097-5397(1995)24:6<1157:OTVOTH>2.0.ZU;2-X
Abstract
Let H-n be the height of a random binary search tree on n nodes. We sh ow that there exists a constant alpha = 4.31107...such that P {/H-n - alpha log n\ > beta log log n} --> 0, where beta > 15 alpha/1n2 = 93.2 933.... The proof uses the second moment method and does not rely on p roperties of branching processes. We also show that Var{H-n} = 0 ((log log n)(2)).