11

想象一下下面的树：

    A
   / \
  B   C
 / \   \
D   E   F

我正在寻找一种方法来查询例如 F 是否是 A 的后代（注意：F 不需要是 A 的直接后代），在这种特殊情况下是正确的。只有有限数量的潜在父节点需要针对更大的潜在后代节点池进行测试。

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

这是一个想出的：

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

     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 = 最大前缀长度 = 最大树深度，所以它的最坏情况完全等于直接上树并比较节点的明显方法。但是，如果测试的节点靠近树的底部并且潜在的父节点位于顶部的某个地方，则此方法的性能要好得多。结合这两种算法将减轻两种最坏的情况。但是，内存开销是一个问题。

还有另一种方法吗？任何指针都非常感谢！

4

8 回答 8

8

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

这个Topcoder 算法教程对问题进行了彻底的讨论，并提供了不同级别的代码复杂性/效率的一些解决方案。

于 2011-05-16T17:51:51.780 回答
4

我不知道这是否适合您的问题，但是将层次结构存储在数据库中的一种方法是存储“路径”，该方法具有快速的“从该节点向下提供所有内容”功能。

例如，对于一个看起来像这样的树：

    +-- b
    |
a --+       +-- d
    |       |
    +-- c --+
            |
            +-- e

您将按如下方式存储行，假设上面树中的字母是每行的“id”：

id    path
a     a
b     a*b
c     a*c
d     a*c*d
e     a*c*e

要查找特定节点的所有后代，您将对路径列执行“STARTSWITH”查询，即。路径以开头的所有节点a*c*

要确定一个特定节点是否是另一个节点的后代，您将查看最长路径是否以最短路径开始。

例如：

  • e 是 a 的后代，因为a*c*e以a
  • d 是 c 的后代，因为a*c*d以a*c

这对你的例子有用吗？

于 2011-05-16T16:34:48.490 回答
3

遍历任何树都需要“深度树”步骤。因此，如果您保持平衡的树结构，则可以证明您将需要O(log n)操作来进行查找操作。据我了解，您的树看起来很特别，您无法以平衡的方式维护它，对吗？所以O(n)是可能的。但这无论如何在树的创建过程中都是不好的，所以你可能会在你使用查找之前死掉......

根据与insert相比您需要该查找操作的频率，您可以决定在insert期间付费以维护额外的数据结构。如果您真的需要摊销O(1) ，我会建议使用散列。在每次插入操作中，您都将节点的所有父节点放入哈希表中。根据您的描述，这可能是给定insert上的O(n)个项目。如果你不插入这听起来很糟糕（接近O( n ^2)），但实际上你的树不能降级那么糟糕，所以你可能会得到O(n log n)的摊销整体 hastable 大小 . （实际上，log n部分取决于树的退化程度。如果您希望它最大程度地退化，请不要这样做。）

因此，您将在每次insert上支付大约O(log n)并获得 hashtable 效率O(1)进行查找。

于 2011-05-16T16:48:15.777 回答
2

对于 M 路树，而​​不是您的位数组，为什么不将二进制“trie id” （每级使用 M 位）存储在每个节点中？对于您的示例（假设 M==2）： A=0b01, B=0b0101, C=0b1001, ...

然后你可以在 O(1) 中进行测试：

bool IsParent(node* child, node* parent)
{ 
   return ((child->id & parent->id) == parent->id)
}

如果您有一个快速FindMSB()函数返回最高有效位集的位置，则可以将存储压缩到每个级别的 ceil(lg2(M)) 位：

mask = (1<<( FindMSB(parent->id)+1) ) -1;
retunr (child->id&mask == parent->id);
于 2011-05-16T16:38:53.813 回答
1

在前序遍历中，每组后代都是连续的。对于你的例子，

A B D E C F
+---------+ A
  +---+ B
    + D
      + E
        +-+ C
          + F

如果您可以预处理，那么您需要做的就是为每个节点编号并计算后代间隔。

如果您无法进行预处理，那么链接/切割树为更新和查询提供 O(log n) 性能。

于 2011-05-16T17:11:09.850 回答
0

您可以回答“节点 A 是节点 B 的后代吗？”形式的查询。在恒定时间内，仅使用两个辅助数组。

通过以深度优先顺序访问来预处理树，并且对于每个节点 A 将其在访问中的开始和结束时间存储在两个数组 Start[] 和 End[] 中。

所以，假设End[u]和Start[u]分别是节点u访问的结束时间和开始时间。

那么节点 u 是节点 v 的后代当且仅当：

开始[v] <= 开始[u] 和结束[u] <= 结束[v]。

你就完成了，检查这个条件只需要在数组 Start 和 End 中进行两次查找

于 2012-11-24T15:49:32.253 回答
0

看看Nested set model选择很有效但是更新太慢

于 2018-04-11T09:24:54.743 回答
0

对于它的价值，您在这里要求的等同于测试一个类是否是类层次结构中另一个类的子类型，并且在像 CPython 这样的实现中，这只是完成了老式的“迭代父母寻找父母”的方式。

于 2021-08-10T17:15:17.637 回答