4

问题

给定具有n 个节点的有根树，其中所有叶子都从一组标签中标记出来。构建一个数据结构，给定叶节点a和标签l，可以找到 a 的最低祖先u，其中u至少有一个标签为l的后代。

线性空间/线性时间方法

  • 从叶a开始
  • 检查a 的所有兄弟姐妹
    • 如果一个兄弟姐妹有标签l找到a和那个兄弟姐妹之间的最低共同祖先。
    • 否则继续父母
  • 如果所有从父母下来的叶节点都没有标记为l，则继续到祖父母并检查它们的叶节点后代。
  • 继续递归检查大祖父母及其所有后代叶节点，直到找到带有l标记的后代。

这具有时间复杂度O(n)和空间复杂度O(n)。

有没有更快的方法来处理线性空间复杂度？也许通过某种方式对树进行预处理？l和a不是固定的，因此预处理必须灵活。

可以通过 Eulerian-Tour 使用 RMQ 在恒定时间内找到最低的共同祖先。

请记住，树不平衡或以任何方式排序。

4

2 回答 2

1

所以，现在我找到了一个更好的解决方案：

这个想法如下：欧拉路径中出现的两个节点越多，它们的 LCA 就越高。即index(a) < index(b) < index(c)=> dist_to_root(LCA(a, b)) >= dist_to_root(LCA(a, c))。

这意味着您只需计算路径中带有标签 l 的a和 a之后的第一个节点的 LCA，以及路径中带有标签 l 的a和a之前的最后一个节点的 LCA 。

其中之一将给出问题的最佳解决方案。

为了有效地找到这两个索引，为每个标签创建一个索引列表，并在O(log n)中执行二进制搜索。

内存复杂度为O(n)。

于 2018-07-26T14:42:00.943 回答
0

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

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

要找到正确的父级，您可以进行二分搜索。例如类似于二元提升的东西。这将增加log(n)的另一个因素。

于 2018-07-26T12:30:18.183 回答