The CRT is the scaling limit of unordered binary trees
The CRT is the scaling limit of unordered binary trees
复制标题
CRT是无序二叉树的缩放限制
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
G. Miermont
中科院分区：
文献类型：
--
作者：
J. Marckert;G. Miermont
我们证明了一棵有n个叶子的一致的，有根的无序二叉树（也称为有根的，二叉Pólya树）具有布朗连续统随机树作为其Gromov‐Hausdorff拓扑的缩放极限。因此，在一个常数因子范围内，其极限与均匀平面树或标记树的极限相同。我们的分析基于对树木适当修剪程序的组合和概率研究。©2011 Wiley期刊公司随机结构。Alg。中文信息学报，38,467 - 501,2011
We prove that a uniform, rooted unordered binary tree (also known as rooted, binary Pólya tree) with n leaves has the Brownian continuum random tree as its scaling limit for the Gromov‐Hausdorff topology. The limit is thus, up to a constant factor, the same as that of uniform plane trees or labeled trees. Our analysis rests on a combinatorial and probabilistic study of appropriate trimming procedures of trees. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 467–501, 2011