On the silhouette of binary search trees

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.

Published in at http://dx.doi.org/10.1214/08-AAP593 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)