𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Profiles of Random Trees: Limit Theorems for Random Recursive Trees and Binary Search Trees

✍ Scribed by Michael Fuchs; Hsien-Kuei Hwang; Ralph Neininger

Publisher
Springer
Year
2006
Tongue
English
Weight
469 KB
Volume
46
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
✍ Luc Devroye; Carlos Zamora-Cura πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 256 KB πŸ‘ 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co