algorithm - 最低共同祖先算法

Question

所以我一直在研究实现最低公共(public)祖先算法。我研究了许多不同的算法(主要是 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
     }

}       

Answer 1

正如其他人所提到的，您的算法目前是二次算法。对于像 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
}

2012 年 5 月 27 日编辑: 处理一个节点从另一个节点继承下来的情况，否则会导致尝试 pop() 一个空堆栈.感谢该死的指出这一点。 (我还意识到跟踪单个 oldNode 就足够了。)