𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distribution of Distances in Random Binary Search Trees

✍ Scribed by Hosam M. Mahmoud and Ralph Neininger

Book ID
118203813
Publisher
Institute of Mathematical Statistics
Year
2003
Tongue
English
Weight
447 KB
Volume
13
Category
Article
ISSN
1050-5164

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Distances in random digital search trees
Distances in random digital search trees
✍ Rafik Aguech; Nabil Lasmar; Hosam Mahmoud πŸ“‚ Article πŸ“… 2006 πŸ› Springer-Verlag 🌐 English βš– 274 KB
Patterns in random binary search trees
Patterns in random binary search trees
✍ Philippe Flajolet; Xavier Gourdon; Conrado MartΓ­nez πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 243 KB

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 probabilit

On the distribution of binary search tre
On the distribution of binary search trees under the random permutation model
✍ James Allen Fill πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 865 KB

We study the distribution Q on the set B, of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B,, when successive requests ar