最低的共同祖先算法 [英] Lowest Common Ancestor Algorithm

问题描述

所以，我一直在寻找到实现最低的共同祖先算法。我看了很多不同的算法（图拉真解决方案，主要或变化的RMQ的变化）。

我使用的非二进制树。我的树会经常查询之间改变，因此pre-处理不一定是值得的。树不应该超过50-75节点。我想知道是否是我应该懒得用自己的算法或只是坚持我自己的。

我的算法

  myLC​​A（节点，节点2）{
    parentNode：= []
    而（节点！= NULL）{
         parentNode.push（节点）
         节点1：= node1.parent
    }
     而（节点2！= NULL）{
         因为我在parentNode.size {
             如果（parentNode（我）==节点2）{
                 返回节点2;
             }
         }
         节点2：= node2.parent
     }

}
 

解决方案

正如其他人所说，你的算法是目前二次。这可能不是小到50-75个节点的数据集的问题，但在任何情况下，它是简单的将其更改为线性时间不使用任何集或哈希表，只是记录的完整路径的根为每个节点，然后步行从根回落，并寻找第一个不同点。紧接preceding节点（其是这2个不同的节点的公共父）是则LCA：

  linearLCA（节点，节点2）{
    parentNode1：= []
    而（节点！= NULL）{
         parentNode1.push（节点）
         节点1：= node1.parent
    }
    parentNode2：= []
    而（节点2！= NULL）{
         parentNode2.push（节点2）
         节点2：= node2.parent
    }
    而（节点==节点2和放大器;＆安培;！的isEmpty（parentNode1）及和放大器;！的isEmpty（parentNode2））{
        oldNode：=节点1
        节点1：= parentNode1.pop（）
        节点2：= parentNode2.pop（）
    }
    如果（节点==节点2）返回节点1 //一个节点从另一个后裔
    否则返回oldNode //无论从其他的后代
}
 

修改27/5/2012：处理，其中一个节点从另一个下降的情况下，否则会导致试图弹出（）空堆栈。由于该死的指出这一点。 （我也意识到，这是足以跟踪单个 oldNode ）

So I have been looking into implementing a lowest common ancestor algorithm. I looked at many different algorithms (mainly variations of Trajan's solution or variations of the RMQ).

I am using a non-binary tree. My tree will often change between queries and therefore pre-processing wouldn't necessarily be worthwhile. The tree shouldn't have more than 50-75 nodes. What I am wondering is whether I should bother using their algorithms or just stick with my own.

My Algorithm

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
     }

}       

解决方案

As others have mentioned, your algorithm is currently quadratic. That may not be a problem for a dataset as small as 50-75 nodes, but in any case it's straightforward to change it to linear time without using any sets or hashtables, just by recording the complete path to the root for each node, then walking back down from the root and looking for the first different node. The immediately preceding node (which is the common parent of these 2 different nodes) is then the 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
}

EDIT 27/5/2012: Handle the case in which one node is descended from the other, which would otherwise result in attempting to pop() an empty stack. Thanks to damned for pointing this out. (I also realised that it's sufficient to track a single oldNode.)

这篇关于最低的共同祖先算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！