𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Generating binary trees at random

✍ Scribed by M.D. Atkinson; J.-R. Sack

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
260 KB
Volume
41
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On growing random binary trees
On growing random binary trees
✍ Boris Pittel πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 841 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

Generating convex polyominoes at random
Generating convex polyominoes at random
✍ Winfried HochstΓ€ttler; Martin Loebl; Christoph Moll πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 517 KB

We give a new recursion formula for the number of convex polyominoes with fixed perimeter. From this we derive a bijection between an interval of natural numbers and the polyominoes of given perimeter. This provides a possibility to generate such polyominoes at random in polynomial time. Our method