On the silhouette of binary search trees

Authors
Citation
Grübel, Rudolf, On the silhouette of binary search trees, Annals of applied probability , 19(5), 2009, pp. 1781-1802
ISSN journal
10505164
Volume
19
Issue
5
Year of publication
2009
Pages
1781 - 1802
Database
ACNP
SICI code
Abstract
A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.