Profile of Random Search Trees
- 2004-07-12 (Mon.), 10:30 AM
- Recreation Hall, 2F, Institute of Statistical Science
- Prof. Hsien-Kuei Hwang
- Institute of Statistical Science, Academia Sinica
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.
Update: