Growing Binary Trees

本文引入了一种新颖的组合框架，通过将动态过程与经典无标签树及曼德尔布罗特多项式联系起来的离散演化规则来对二叉树增长进行建模，并最终开发出一种用于生成具有特定剖面的树的最优迭代采样器。

要点

想象一下你是一位园丁，拥有一种非常特殊的、神奇的种树规则。这不仅仅是播种，而是一个关于每部分都有其天命的逐步演化过程。

这里是 Bodini、Genitrini 和 Nurligareev 的论文《生长二叉树》（Growing Binary Trees）的简单解释。

神奇花园：一种新的种树方式

通常，当数学家研究树如何生长时，他们想象的是一个树只会不断变大的过程。每一条已经存在的树枝都是一个潜在的新叶生长点，且一旦开始生长，就永不停止。这就像一棵只能扩张、永远不会萎缩或死亡的树。

重大变化：
这篇论文的作者决定增加一条新规则：灭绝（Extinction）。
在他们的模型中，一棵树有三种类型的组成部分：

1. 活跃锚点 (◦)： 这些是“生长尖端”。它们是活着的，并准备好进行分裂。
2. 内部节点 (•)： 这些是已经完成分裂的坚实树枝。
3. 死亡叶片 (□)： 这些是决定停止生长的尖端。

过程：
想象你从一个单一的“锚点”（一个小嫩芽）开始。在每一个时间步，你观察树上的每一个锚点，并给它一个选择：

• 选项 A（死亡）： 锚点变成一个死亡叶片。它永远停止生长。
• 选项 B（生长）： 锚点分裂成一个新的分支，并在末端产生两个新的锚点。

这个简单的“生死”游戏创造了一类独特的树族。因为锚点会死亡，这些树最终会停止生长，并变成数学家所说的“无标签二叉树”（即计算机科学中常见的经典树）。

隐藏的数学：与混沌与编码的联系

作者发现，这种简单的园艺游戏与一些非常复杂的数学有着深刻的联系。

• 曼德博特（Mandelbrot）的联系： 他们发现，描述这些树如何生长的数学与 曼德博特多项式 相关联。你可能知道曼德博特集合，它是那个著名的、无限复杂的分形形状，看起来像一颗带有旋转边缘的黑色心形。论文表明，这些树的“生长”行为类似于该分形中的相变。如果生长率过高，树会爆炸式增长；如果生长率过低，它就会枯萎。树能够完美生长的那个“甜点位”（sweet spot），在数学上与那个著名分形的边缘紧密相连。
• “丛生”的树： 作者观察了给定规模下最“丛生”（bushy）的树（即在最底层拥有最大数量叶片的树）。他们发现，这些树的模式遵循一种奇怪的自指序列（称为元斐波那契序列/meta-Fibonacci sequence）。这就像是一个通过观察自身之前的数字来定义自身的数字模式。
• 编码理论： 他们还意识到这些树与编码理论（即如何在传输数据时不产生错误而进行编码的数学）有关。这些树中叶片分布的方式遵循与“克拉夫特不等式”（Kraft's inequality）相同的规则，这是用于设计高效计算机代码的规则。

实用工具：自底向上构建树

这篇论文中最实用的部分是一种新的随机生成这些树的方法。

假设你想创建一个具有特定形状（即具有特定层级叶片分布特征的“轮廓”）的树。

• 旧方法： 通常，你会从顶部（根节点）开始，尝试猜测哪些分支应该生长。这就像是在还没打好地基之前，就试图通过猜测屋顶的位置来盖房子。这很慢，很复杂，并且需要大量的尝试和错误。
• 新方法： 作者发明了一种从底向上（由下而上）工作的方法。
  1. 从最底层（最深层）的叶片开始。
  2. 随机打乱它们。
  3. 将它们配对，形成位于它们正上方的树枝。
  4. 保持这种方式逐层向上移动，直到到达根节点。

这个方法就像是通过从地面向上堆叠石头来建造金字塔，而不是试图在一个堆叠的石头顶端平衡一块单石。作者证明了这种新方法是极其高效的。它使用了最少的时间、最少的计算机内存以及最少的“随机比特”（数字世界的硬币投掷）。

总结

简而言之，这篇论文引入了一种新的“树生长游戏”，其中树枝可以死亡。这种简单的规则架起了动态生长过程与静态经典树形之间的桥梁。它揭示了这些树在秘密地与著名的分形（曼德博特）和数据压缩编码相连。最后，作者利用这些见解，开发了一个超快速、完美的工具，通过自底向上的方式，生成具有特定形状的随机树。

技术摘要

技术摘要：增长型二叉树

问题陈述
本文探讨了二叉树演化的组合建模，特别是弥合了动态增长过程与经典无标签二叉树结构之间的鸿沟。以往的文献广泛研究了“递增树”（increasing trees），即节点在时间约束下（如递归树、Schröder 树）进行顺序添加的模型；然而，这些模型本质上是单调的：结构只能扩张，且每个叶节点始终是进一步发展的潜在位点。作者指出，有必要在增长过程中引入一个“灭绝”或“死亡”规则。这一规则的加入允许分支终止，从而将动态进化模型与经典的无标签二叉树重新联系起来。其挑战在于刻画由此产生的结构，特别是树的高度、最深层级最大叶子数以及整体树轮廓（tree profile，即叶子在各层级的分布），这些参数在传统的动态框架中通常难以获取。

方法论
作者为一类特定的二叉树（称为“增长型二叉树”）引入了一种离散演化过程。该模型定义了三种节点类型：

1. 内部节点 ($\bullet$)：始终有两个子节点。
2. 活跃叶节点或锚点 ($\circ$)：潜在的增长位点。
3. 死亡叶节点 ($\square$)：已终止的分支。

增长过程在离散时间步 $t \in \mathbb{Z}_{\geq 0}$ 中进行。从 $t=0$ 时的一个单一锚点开始，在随后的每一个步骤中，每个锚点要么被替换为一个死亡叶节点，要么被替换为一个由一个内部节点和两个新锚点组成的子树。

该方法结合了符号组合学和多项式迭代分析：

• 生成函数： 作者定义了一个二元生成函数 $T(x,z)$，其中 $x$ 标记锚点，$z$ 标记内部节点。基于增长过程的替换规则，他们推导出了一个泛函方程：$T(x,z) = x + T(1+zx^2, z) - T(1,z)$。
• 多项式迭代： 通过对生成函数求导并分析递归关系，作者将树的增长动力学与一系列多项式 $p_h(x,z)$ 联系起来。这些多项式被识别为与 Mandelbrot 多项式 ($M_h(z)$) 相关，建立了树增长与 Mandelbrot 集动力学之间的联系。
• 组合计数： 本文分析了具有 $n$ 个内部节点和 $2k$ 个锚点的树 $t_{n,2k}$ 的数量。作者研究了代表给定规模 $n$ 的树的最大锚点数序列 $a_n$，并将其与 Meta-Fibonacci 数列联系起来。
• 几何分析： 对于固定高度 $h$ 的树，作者定义了一个有效的 $(n, k)$ 对构成的区域 $S_h$，并分析了其边界和缩放极限。
• 算法设计： 利用树轮廓的组合结构，作者设计了一种用于均匀随机采样的迭代算法。

核心贡献与结果

1. 带有灭绝机制的组合框架： 本文通过引入终止规则，成功扩展了递增树模型。这实现了动态增长过程与经典无标签二叉树之间的直接映射。作者将节点分类为内部、活跃和死亡，为分析树轮廓提供了严谨的框架。

2. 与 Mandelbrot 多项式及相变的联系： 一个重要的理论贡献是发现该增长过程的生成函数与涉及 Mandelbrot 多项式的多项式迭代相关联。作者证明了在临界值 $z_c = 1/4$ 处，树增长动力学存在相变。对于 $|z| < 1/4$，过程向 Catalan 生成函数收缩（几乎确定灭绝）；而对于 $z > 1/4$，则会发生发散（爆炸式增长）。这将其过程的解析域与 Mandelbrot 集的主心形区域（main cardioid）联系起来。

3. 树参数的刻画：

   • 最大锚点数： 作者将序列 $a_n$（规模为 $n$ 的树的最大锚点数）刻画为 Meta-Fibonacci 数列（OEIS A006949）。他们提供了递归关系及其渐近行为（$\lim_{n \to \infty} a_n/n = 1/2$）。
   • 树高度与轮廓： 本文建立了关于内部节点数、锚点数和高度之间的严格不等式关系。他们描述了固定高度下有效树的几何区域，并表明随着高度 $h \to \infty$，归一化后的区域收敛于顶点为 $(0,0)$, $(1,0)$, 和 $(2,1)$ 的三角形。
   • 轮廓计数： 利用编码理论中的 Kraft-McMillan 等式，作者推导出了拥有特定叶子轮廓的二叉树数量的乘积公式。

4. 最优随机采样算法： 作者提出了 算法 1，一种针对具有特定轮廓的二叉树的自底向上迭代均匀随机采样器。不同于计算量巨大的传统自顶向下递归方法，该方法从最深层向上构建树。该算法在时间复杂度、空间复杂度和随机比特消耗方面均被证明是优化的。

意义与主张
本文声称提供了一种新的组合视角来建模树的增长，该视角统一了动态进化过程与经典结构参数。通过引入灭绝规则，作者使得研究“丛生型”（bushy）树和树轮廓成为可能，这在之前的单调递增树模型中是无法实现的。

这项工作的意义在于：

• 结构联系： 揭示了树增长、Mandelbrot 多项式以及编码理论（特别是通过 Kraft-McMillan 等式）之间的深层联系。
• 算法效率： 提供了一种实现均匀随机采样的有效方法，达到了最优复杂度，克服了以往针对轮廓约束树的递归方法的局限性。
• 理论洞察： 对最深层叶子的极限分布以及树区域的几何缩放提供了精确的刻画。

作者将这项工作定位为基础性的一步，指出 Mandelbrot 多项式与 Flajolet-Odlyzko 迭代之间的联系，为基于灭绝的增长过程提供了一个统一的组合视角，并具有向二叉森林及具有部分轮廓之树扩展的潜力。