𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distances in random digital search trees

✍ Scribed by Rafik Aguech; Nabil Lasmar; Hosam Mahmoud

Publisher
Springer-Verlag
Year
2006
Tongue
English
Weight
274 KB
Volume
43
Category
Article
ISSN
0001-5903

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Imbalance in Random Digital Trees
Imbalance in Random Digital Trees
✍ Hosam M. Mahmoud πŸ“‚ Article πŸ“… 2008 πŸ› Springer US 🌐 English βš– 379 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

Further results on digital search trees
Further results on digital search trees
✍ Peter Kirschenhofer; Helmut Prodinger πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 460 KB