Yoshiaki Itoh, Inst. of Statistical Maths, Tokyo, Japan

Binary Search Trees and 1-Dimensional Random Packing

One-dimensional random sequential packing is known as the car parking problem. The sequential packing is continued until none of the lengths of gaps generated by the cars of length $1$ placed in $[0,x]$ is greater than 1. We study the expected number of intervals packed by this procedure and the expected minimum length of the gaps. This is extended to study the probability distribution of the height of binary search trees.