论文标题
两种对数深度树模型的压实：分析和实验
Compaction for two models of logarithmic-depth trees: Analysis and Experiments
论文作者
论文摘要
我们对两种经典树木家庭的压实率的定量分析感兴趣：递归树木和平面二进制二进制树木。这些家庭是深度较小的树模型的典型代表。一旦一棵大树$ n $的树即可通过仅保留一个出现在树上的所有边缘子树的出现来压实，结果图仅包含$ o（n / \ ln n）$节点。必须将此结果与简单生成的树的家族的压实结果进行比较，在这种情况下，类似结果指出，紧凑的结构是$ n / \ sqrt {\ ln n n} $的顺序大小的大小。关于飞机增加树木的结果已经得到证明，但是我们提出了一种新的通用方法来获得结果。最后，基于压实的二进制搜索树的原型实施，提出了一项实验研究，这些搜索树是由平面二进制增加的树木建模的。
We are interested in the quantitative analysis of the compaction ratio for two classical families of trees: recursive trees and plane binary increasing trees. These families are typical representatives of tree models with a small depth. Once a tree of size $n$ is compacted by keeping only one occurrence of all fringe subtrees appearing in the tree the resulting graph contains only $O(n / \ln n)$ nodes. This result must be compared to classical results of compaction in the families of simply generated trees, where the analogous result states that the compacted structure is of size of order $n / \sqrt{\ln n}$. The result about the plane binary increasing trees has already been proved, but we propose a new and generic approach to get the result. Finally, an experimental study is presented, based on a prototype implementation of compacted binary search trees that are modeled by plane binary increasing trees.
