检查2树节点在O相关（祖先/后代）（1）用前处理

检查2树节点是相关的（即祖先子孙）检查2树节点在O相关（祖先/后代）（1）用前处理

解决它在O（1）时间，与O（N）的空间（N =节点＃）
预处理允许

就是这样。我将在下面讨论我的解决方案（方法）。如果你想先想好自己，请停止。

对于前处理，我决定做一个预购（递归通过根先走，然后儿童），给一个标签到每个节点。

让我详细解释标签。每个标签由逗号分隔的自然数组成，如“1,2,1,4,5” - 该序列的长度等于（节点的深度+1）。例如。根的标签是“1”，根的孩子将有标签“1,1”，“1,2”，“1,3”等。下一级节点将有标签，如“1,1,1” ，“1,1,2”，...，“1,2,1”，“1,2,2”，...

假设节点的“订单号”是“该节点的基于1的索引”在其父项的子项目列表中。

常用规则：节点的标签由其父标签后跟逗号和“订单号”组成。因此，为了回答O（1）中两个节点是否相关（即祖先 - 后代），我将检查其中一个标签的标签是否为其他标签的“”前缀“。虽然我不确定这些标签是否可以被认为占用O（N）空间。

任何批评者都有修正或替代方法。

来源

2012-04-25 Alec

这是在最坏的情况下每个节点都有一个孩子（面条）的O（N^2）空间。 – WeaselFox 2012-04-25 07:09:25

如果您存储每个顶点的预订号和后序号并使用此事实，则可以在O（n）预处理时间和O（n）空间中执行O（1）查询时间：

对于树T的两个给定节点x和y，x是y的祖先，只有当x在前序遍历T中出现在y之前，并且在后序遍历中出现在y 之后时。

（在此页：http://www.cs.arizona.edu/xiss/numbering.htm）

你在最坏的情况下所做的是西塔（d）其中d是上级节点的深度，所以是不是O（1）。空间也不是O（n）。

来源

2012-04-25 07:21:58

那么面条情景呢？有序的前序和后序完全一样，所以没有节点是另一个的祖先？ – WeaselFox 2012-04-25 07:41:34

@ WeaselFox：你的意思是像一个链表？这些遍历不会互相颠倒吗？ – 2012-04-25 07:52:13

你是绝对正确..我的坏 – WeaselFox 2012-04-25 07:57:46

有线性时间最低的共同祖先算法（至少离线）。例如看看here。你也可以看看tarjan's offline LCA algorithm。请注意，这些文章要求您事先知道您将执行LCA的配对。我认为也有在线线性时间预计算时间算法，但它们非常复杂。例如，对于范围最小查询问题，存在线性预计算时间算法。据我记得这个解决方案两次通过LCA问题。该算法的问题在于它具有如此大的常数，以至于实际上比O（n * log（n））算法更快地需要大量输入。

有更简单的方法需要O（n * log（n））额外的内存，并在同一时间再次回答。

希望这会有所帮助。

来源

2012-04-25 07:23:38

生命周期分析对此是过度的。 – 2012-04-25 07:23:56

如果您考虑一棵树，树中有一个节点有n/2个孩子（比如说），设置标签的运行时间将会高达O（n * n）。所以这个标签方案不会工作....

来源

2013-09-26 14:33:11 pypep278

检查2树节点在O相关（祖先/后代）（1）用前处理

回答

相关问题