论文标题
关于随机二进制树的边缘子树的集合
On the Collection of Fringe Subtrees in Random Binary Trees
论文作者
论文摘要
根树的条纹子树是由一个节点及其所有后代组成的子树。在本文中，我们特别对出现在二进制树所有边缘子树的集合中的非同形树的数量特别感兴趣。该数字在两个不同的随机模型下进行分析：统一的随机二进制树和随机的二进制搜索树。 在统一的随机二进制树的情况下，我们表明，非同构边缘子树的数量位于$ C_1N/\ sqrt {\ ln n}（\ ln n}（1+o（1+o（1））$和$ C_2N/\ c_2n/\ sqrt {\ sqrt {\ ln n}（\ ln n}（\ ln n}（\ ln n}（1+o（1+o（1+o（1+o（1+o（1+o）， $ c_2 \大约1.0761505454 $，无论是预期的还是很高的概率，其中$ n $表示均匀随机二进制树的大小（叶子数）。对于随机的二进制搜索树而言，类似的结果被证明，但是在这种情况下，数量级为$ n/\ ln n $。 我们的证明技术也可以用来加强有关不同条纹子树数量的已知结果（从有序树的意义上讲）。在两种情况下，此数量的数量级相同，但上限和下限的常数略有不同。
A fringe subtree of a rooted tree is a subtree consisting of one of the nodes and all its descendants. In this paper, we are specifically interested in the number of non-isomorphic trees that appear in the collection of all fringe subtrees of a binary tree. This number is analysed under two different random models: uniformly random binary trees and random binary search trees. In the case of uniformly random binary trees, we show that the number of non-isomorphic fringe subtrees lies between $c_1n/\sqrt{\ln n}(1+o(1))$ and $c_2n/\sqrt{\ln n}(1+o(1))$ for two constants $c_1 \approx 1.0591261434$ and $c_2 \approx 1.0761505454$, both in expectation and with high probability, where $n$ denotes the size (number of leaves) of the uniformly random binary tree. A similar result is proven for random binary search trees, but the order of magnitude is $n/\ln n$ in this case. Our proof technique can also be used to strengthen known results on the number of distinct fringe subtrees (distinct in the sense of ordered trees). This quantity is of the same order of magnitude in both cases, but with slightly different constants in the upper and lower bounds.
