12

所以我一直在研究实现最低共同祖先算法。我查看了许多不同的算法（主要是 Trajan 解决方案的变体或 RMQ 的变体）。

我正在使用非二叉树。我的树经常会在查询之间发生变化，因此预处理不一定是值得的。树的节点不应超过 50-75 个。我想知道是我应该打扰使用他们的算法还是坚持我自己的算法。

我的算法

myLCA(node1, node2) {
    parentNode := [ ]
    while (node1!=NULL) {
         parentNode.push(node1)
         node1 := node1.parent
    }
     while (node2!=NULL) {
         for i in parentNode.size {
             if (parentNode(i) == node2) {
                 return node2; 
             }
         }
         node2 := node2.parent
     }

}
4

6 回答 6

17

正如其他人所提到的，您的算法目前是二次的。对于像 50-75 个节点这样小的数据集，这可能不是问题，但无论如何，无需使用任何集合或哈希表即可将其更改为线性时间，只需记录每个节点到根的完整路径，然后从根返回并寻找第一个不同的节点。紧接在前面的节点（这是这两个不同节点的共同父节点）是 LCA：

linearLCA(node1, node2) {
    parentNode1 := [ ]
    while (node1!=NULL) {
         parentNode1.push(node1)
         node1 := node1.parent
    }
    parentNode2 := [ ]
    while (node2!=NULL) {
         parentNode2.push(node2)
         node2 := node2.parent
    }
    while (node1 == node2 && !isEmpty(parentNode1) && !isEmpty(parentNode2)) {
        oldNode := node1
        node1 := parentNode1.pop()
        node2 := parentNode2.pop()
    }
    if (node1 == node2) return node1    // One node is descended from the other
    else return oldNode                 // Neither is descended from the other
}

编辑 27/5/2012：处理一个节点从另一个节点下降的情况，否则会导致尝试pop()空堆栈。感谢该死的指出这一点。（我也意识到跟踪单个oldNode.）就足够了。）

于 2011-06-14T11:06:02.233 回答
4

对于这么小的树，我不会费心去实现更复杂的东西。您的解决方案看起来不错，尽管时间复杂度是根据树的高度平方的。如果您可以轻松实现Set（大多数语言都内置了它），那么可以将算法调整为，

  1. 从第一个节点遍历到根节点并收集集合中的所有节点
  2. 从第二个节点向上遍历到根节点并检查当前节点是否存在于该集合中。如果是这样，那就是共同的祖先。

此外，该算法假设一个节点可以是它自己的祖先。否则，您将不得不稍微调整算法。考虑这个例子，

A
|
B
|
C

当试图找到 B 和 C 的最低共同祖先时，该算法将报告 B，这可能是也可能不是，具体取决于您如何定义祖先。

于 2011-06-14T02:48:21.043 回答
3

在不查看任一算法的细节的情况下，我建议查看此算法的效率对您的整体应用程序的重要性，以及实现另一种算法需要多少努力。

该算法将在您的应用程序的正常（或压力）操作中运行多少次？它会导致用户等待比必要的时间更长吗？其他不同数量级的算法是否比你的更快？（熟悉算法的人可以给你更详细的答案。）

我认为不值得优化一点代码，除非你会看到相当大的结果（有些人强烈认为过早的优化是万恶之源）

于 2011-06-14T02:49:10.673 回答
2

我刚刚写了一篇关于我必须如何为这个问题实现自己的算法但扩展到一组任意长度的节点的博客文章。你可以在这里找到它（通过逐步图形说明它是如何工作的）

http://bio4j.com/blog/2012/02/finding-the-lowest-common-ancestor-of-a-set-of-ncbi-taxonomy-nodes-with-bio4j/

干杯，

巴勃罗

于 2012-02-09T09:17:09.400 回答
2

你的算法是二次的，但它很容易变成线性的。

只需使用哈希表（即设置）parentNode，而不是列表。因此，检查一个节点是否在parentNode将O(1)代替O(n).

于 2011-06-14T06:07:08.980 回答
1

我有一个简单的解决方案对两个元素进行排序，最低的是左边，最高的是右边访问 root def recurse(root) 如果 root.empty 返回 nil？if left <= root && right >= root return root elsif left <= root && right <= root recurse(root.left) else recurse(root.right) end

所以这将检查每次遍历问题在 O(log n) 时间内解决平均和最差以及 O(log

于 2012-07-07T05:45:43.577 回答