✦ LIBER ✦

A study of random Weyl trees

✍ Scribed by Luc Devroye; Amar Goudjil

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 261 KB
Volume: 12
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199805)12:3<271::aid-rsa4>3.0.co;2-s

No coin nor oath required. For personal study only.

✦ Synopsis

We study binary search trees constructed from Weyl sequences n , n G 1, Ä 4 where is an irrational and и denotes ''mod 1.'' We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of . If H is n w x the height of the tree with n nodes when is chosen at random and uniformly on 0, 1 , then Ž 2 . we show that in probability, H ; 12r log n log log n.

📜 SIMILAR VOLUMES

A family of random trees with random edg

A family of random trees with random edge lengths

✍ David Aldous; Jim Pitman 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 212 KB 👁 2 views

We introduce a family of probability distributions on the space of trees with I labeled vertices and possibly extra unlabeled vertices of degree 3, whose edges have positive real lengths. Formulas for distributions of quantities such as degree sequence, shape, and total length are derived. An interp

On the profile of random trees

✍ Michael Drmota; Bernhard Gittenberger 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 302 KB 👁 1 views

Let T be a plane rooted tree with n nodes which is regarded as family tree of a Galton-Watson branching process conditioned on the total progeny. The profile of the tree ' may be described by the number of nodes or the number of leaves in layer t n , respectively. It is shown that these two processe

The distribution of nodes of given degre

The distribution of nodes of given degree in random trees

✍ Drmota, Michael; Gittenberger, Bernhard 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 391 KB 👁 2 views

Let T n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of T n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ∼ µ k n and variance ∼ σ 2 k n with positive constants µ

A Garden of Trees

✍ Nicholas Mosley 📂 Fiction 📅 2012 🏛 Columbia University Press;Dalkey Archive Press 🌐 en-US ⚖ 168 KB 👁 2 views

Returning to London from a trip to the West Indies, an aspiring writer encounters a bewitching trio of friends whose magic lies in their ability to turn any situation into fantasy. Previously out of place in the world, the narrator falls in love with the young brother-sister pair of Peter and Annabe

A Dream of Trees

✍ Samantha Sotto 📂 Fiction 📅 2019 🏛 Stripe&Yellow 🌐 English ⚖ 131 KB 👁 2 views

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