论文标题
计算旋转距离问题的困难树对
Counting difficult tree pairs with respect to the rotation distance problem
论文作者
论文摘要
根二进制树之间的旋转距离是将一棵树转变为另一棵树所需的简单旋转的最小数量。在树木之间存在公共边缘或单个旋转引入共同边缘的情况下，可以快速减少一对根树之间的旋转距离。没有这样降低的树对是困难的树对，那里没有一般的第一步。在这里，我们描述了计算和估计这种困难树对数量的努力，并发现该分数逐步降低至零。我们还描述了如何了解旋转距离问题的不同实例的数量是使计算更可行的有用因素。
Rotation distance between rooted binary trees is the minimum number of simple rotations needed to transform one tree into the other. Computing the rotation distance between a pair of rooted trees can be quickly reduced in cases where there is a common edge between the trees, or where a single rotation introduces a common edge. Tree pairs which do not have such a reduction are difficult tree pairs, where there is no generally known first step. Here, we describe efforts to count and estimate the number of such difficult tree pairs, and find that the fraction decreases exponentially fast toward zero. We also describe how knowing the number of distinct instances of the rotation distance problem is a helpful factor in making the computations more feasible.
