zbMATH — the first resource for mathematics

Patterns in random binary search trees. (English) Zbl 0895.60010
Summary: In a randomly grown binary search tree (BST) of size \(n\), any fixed pattern occurs with a frequency that is on average proportional to \(n\). Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics.

60C05 Combinatorial probability
05C05 Trees
68P05 Data structures
Full Text: DOI