algorithm - O(1)算法确定节点是否是多路树中另一个节点的后代？

Question

想象一下下面的树:

    A
   / \
  B   C
 / \   \
D   E   F

我正在寻找一种方法来查询例如 F 是否是 A 的后代(注意:F 不需要是 A 的直接后代)，在这个特定的情况会是真的。仅需要针对更大的潜在后代节点池测试有限数量的潜在父节点。

在测试一个节点是否是潜在父池中某个节点的后代时，需要针对所有潜在父节点进行测试。

这是一个想出的:

• 将多路树转换为 trie，即为上述树中的每个节点分配以下前缀:

   A = 1
   B = 11
   C = 12
   D = 111
   E = 112
   F = 121
  

• 然后，为每个可能的前缀大小保留一个位数组，并添加要测试的父节点，即如果将 C 添加到潜在的父节点池中，则执行:

    1    2    3  <- Prefix length
  
  *[1]  [1]  ...
   [2] *[2]  ...
   [3]  [3]  ...
   [4]  [4]  ...
   ...  ...
  

• 当测试一个节点是否是潜在父节点的后代时，获取它的 trie 前缀，查找第一个“前缀数组”(见上文)中的第一个字符，如果存在，查找第二个前缀第二个“前缀数组”中的字符等等，即测试 F 导致:

   F = 1    2    1
  
     *[1]  [1]  ...
      [2] *[2]  ...
      [3]  [3]  ...
      [4]  [4]  ...
      ...  ...
  

  所以是的，F 是 C 的后代。

这个测试似乎是 O(n) 的最坏情况，其中 n = 最大前缀长度 = 最大树深度，因此它的最坏情况恰好等于只上树并比较节点的明显方式。然而，如果被测试的节点靠近树的底部并且潜在的父节点在顶部某处，这会表现得更好。结合这两种算法将减轻两种最坏的情况。但是，内存开销是一个问题。

还有其他方法吗？非常感谢任何指点!

Answer 1

你的输入树总是静态的吗？如果是这样，那么您可以使用最低公共(public)祖先算法在 O(1) 时间内用 O(n) 时间/空间构造回答后代问题。 LCA 查询有两个节点，并询问哪个是树中最低的节点，其子树包含这两个节点。然后，您可以使用单个 LCA 查询来回答 IsDescendent 查询，如果 LCA(A, B) == A 或 LCA(A, B) == B，则一个是另一个的后代。

这Topcoder algorithm tuorial对问题进行了全面讨论，并在代码复杂性/效率的各个级别提供了一些解决方案。