Efficient random sampling of binary and unary-binary trees via holonomic equations

Axel Bacher, Olivier Bodini, Alice Jacquot

We present a new uniform random sampler for binary trees with $n$ internal nodes consuming $2n+\Theta (\log (n{)}^2)$ random bits on average. This makes it quasi-optimal and out-performs…