Profile of Random Search Trees

Abstract

Our recent discovery of many intriguing phenomena in the profile of random search trees is presented. The profile of a tree is the sequence of numbers counting the number of nodes at the same distance to the root. Special features for the profile of random search trees include: unimodal mean but bimodal variance, the range for convergence in distribution differs from that for convergence of all moments, there exists a small range where the limit law does not exist, and sharp sign-changes for the correlation coefficients, etc.