如何找到具有某个标签的后代叶节点的最低祖先?

How does one find the lowest ancestor with a descendant leaf node with some label?

问题

给定一棵具有 n 个节点的有根树,其中所有叶子都由一组标签标记。构建一个数据结构,给定一个叶节点 a 和一个标签 l,可以找到最低的祖先 u[= a 的 50=],其中 u 至少有一个带有标签 l 的后代。

线性Space/线性时间方法

  • 从叶开始 a
  • 检查 a 的所有兄弟姐妹
    • 如果兄弟姐妹有标签 l 找到 a 和那个兄弟姐妹之间的 lowest-common-ancestor。
    • 否则继续parents
  • 如果所有 parents 的后代 leaf-nodes 都没有被标记为 l,请继续到 grandparents 并检查它们的 leaf-node后代。
  • 继续递归检查 greater-grandparents 及其所有后代 leaf-nodes,直到找到 l 标记的后代。

这具有时间复杂度 O(n) 和 space 复杂度 O(n).


有没有更快速的线性 space 复杂度的方法?也许通过某种方式预处理树? la 不是固定的,所以 pre-processing 必须是灵活的。

可以通过 Eulerian-Tour.

使用 RMQ 在常数时间内找到最低的共同祖先

请记住,树不是平衡的,也不是以任何方式排序的。

这是一个 O(log(n)^3) 时间复杂度和 O(n log(n)) 的解决方案space 复杂度。

L 为您在欧拉路径上遇到的标签列表。您使用此列表构建一个线段树,并在树的每个节点中存储出现在相应线段中的标签集。 然后你可以检查 O(log(n)^2) 时间,如果一个标签通过线段树中的范围查询出现在子树中。

要找到正确的父级,您可以进行二分查找。例如。类似于二进制提升的东西。这将增加 log(n).

的另一个因素

所以,现在我找到了更好的解决方案:

思路如下: 欧拉路径中出现的节点越多,它们的 LCA 就越高。 IE。 index(a) < index(b) < index(c) => dist_to_root(LCA(a, b)) >= dist_to_root(LCA(a, c))

这意味着你只需要计算 aa 之后的第一个节点的 LCA,标签为 [=24=路径中的]l,以及aa之前的最后一个节点的LCA,标签为 l在路径中.

其中一个会给出问题的最优解。

为了有效地找到这两个索引,为每个标签创建一个索引列表,并在 O(log n).

中执行二进制搜索

内存复杂度为 O(n)