On the Collection of Fringe Subtrees in Random Binary Trees
On the Collection of Fringe Subtrees in Random Binary Trees
复制标题
DOI：
10.1007/978-3-030-61792-9_43
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Louisa Seelbach Benkner;S. Wagner
中科院分区：
文献类型：
--
作者：
Louisa Seelbach Benkner;S. Wagner
根树的边缘子树是由一个节点及其所有后代组成的子树。在本文中，我们特别感兴趣的非同构树，出现在一个二叉树的所有边缘子树的集合中的数量。在均匀随机二叉树和随机二叉搜索树两种不同的随机模型下分析了这个数.在均匀随机二叉树的情况下，我们证明了对于两个常数和，非同构边缘子树的数目在期望和高概率之间，其中表示均匀随机二叉树的大小（叶子的数目）。一个类似的结果被证明为随机二叉搜索树，但数量级是在这种情况下，我们的证明技术也可以用来加强不同的边缘子树（在有序树的意义上不同）的数量的已知结果。这个量在两种情况下具有相同的数量级，但是在上界和下界中具有略微不同的常数。
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 betweenandfor two constantsand, both in expectation and with high probability, wherendenotes 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 isin 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.