✦ LIBER ✦

On the richness of the collection of subtrees in random binary search trees

✍ Scribed by Luc Devroye

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 318 KB
Volume: 65
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(97)00206-8

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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 log-product of the subtree-sizes

On the log-product of the subtree-sizes of random trees

✍ A. Meir; J. W. Moon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 2 views

We determine the asymptotic behavior of the expected value and the variance of the log-product of the subtree-sizes of trees T belonging to simply generated families of n

Addendum to “On the log-product of the s

Addendum to “On the log-product of the subtree-sizes of random trees”

✍ A. Meir; J. W. Moon 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 2 views

The asymptotic behavior of the mean and the variance of the log-product of the subtree-sizes of trees belonging to simply generated families of rooted trees were determined in this paper. The authors have learned that Professor Boris Pittel, in a manuscript entitled ''Normal Convergence Problem? Two

A note on subtrees rooted along the prim

A note on subtrees rooted along the primary path of a binary tree

✍ Brent M. Troutman; Michael R. Karlinger 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 348 KB

On the Total Heights of Random Rooted Bi

On the Total Heights of Random Rooted Binary Trees

✍ L. Takacs 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 306 KB

Denote by \(S_{n}\) the set of all distinct rooted binary trees with \(n\) unlabeled vertices. Define \(\sigma_{n}\) as a total height of a tree chosen at random in the set \(S_{n}\), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the

New lower bounds on the cost of binary s

New lower bounds on the cost of binary search trees

✍ Roberte De Prisco; Alfredo De Santis 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 674 KB