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

被引：4

作者：

Bacher, Axel ^{[1
]}

Bodini, Olivier ^{[2
]}

Jacquot, Alice ^{[2
]}

机构：

[1] Johannes Kepler Univ Linz, RISC, Altenbergerstr 69, A-4040 Linz, Austria

[2] Univ Paris 13, Sorbonne Paris Cite, LIPN, CNRS,UMR 7030, F-93430 Villetaneuse, France

来源：

THEORETICAL COMPUTER SCIENCE | 2017年 / 695卷

关键词：

Random sampling; Remy algorithm; Holonomic equation; Plane trees; RANDOM GENERATION;

D O I：

10.1016/j.tcs.2017.07.009

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 outperforms the classical Remy algorithm. We also present a sampler for unary-binary trees with n nodes taking Theta(n) random bits on average. Both are the first linear-time algorithms to be optimal up to a constant. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：42 / 53

页数：12

共 4 条

[1] Holonomic equations and efficient random generation of binary trees
Lescanne, Pierre
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2023, 25 (02)
[2] On the Number of Unary-Binary Tree-Like Structures with Restrictions on the Unary Height
Bodini, Olivier
Gardy, Daniele
Gittenberger, Bernhard
Golebiewski, Zbigniew
ANNALS OF COMBINATORICS, 2018, 22 (01) : 45 - 91
[3] Simple Random Sampling of Binary Forests with Fixed Number of Nodes and Trees
Dimitrov, Stoyan
COMBINATORIAL ALGORITHMS, IWOCA 2024, 2024, 14764 : 43 - 54
[4] Efficient Stochastic Analysis of Real-Time Systems via Random Sampling
Refaat, Khaled S.
Hladik, Pierre-Emmanuel
22ND EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS (ECRTS 2010), 2010, : 175 - 183

← 1 →