n元树中多个节点的最低公共祖先

I am trying to implement LCA of multiple nodes in an n-ary tree in java. I am working with parse trees of sentences, So its reasonable to assume that number of children of a node <= 6. Multiple nodes here are two phrases(continuous word sequence) in a sentence. Let k be the number of nodes involved.

一种方法是找到k/2对的两个节点的LCA,我们将得到k/2个节点。现在递归这些k/2节点。顺序为O(nlog k),其中O(n)是线性LCA发现算法的复杂度。我可以更有效地做到吗?

0
额外 编辑
意见: 1
@VSOverFlow我会有log(k)个步骤,每个步骤都需要O(n),因此总体上它的O(nlog k)。计算中的O(k)是什么?
额外 作者 damned,
我认为复杂性是O(n。k)而不是O(n。log(k))。你将有k/2,k/4的log(k)步骤,它是O(k)。
额外 作者 VSOverFlow,
我假设LCA(2,n)是O(n)。当您构建二叉树时,LCA调用的总数为O(k)(k/2 + k/4 + ....)。所以总的运行时间复杂度是O(n * k)(即k次调用O(n))。每个log(k)步有许多O(n)级(k/2,k/4,k/8,...)
额外 作者 VSOverFlow,

1 答案

我使用这样的事实来解决问题,即短语的节点是连续的,即在分析树的叶节点列表中具有连续的索引。

segment1 具有从 start1end1 的索引。 segment2 =(start2,end2)也是如此。

(start1,end1)(start2,end2)所需的公共祖先是索引 min(start1,start2)max(end1,end2)

0
额外
这个想法是,如果所有节点都是连续的叶节点,所有这些节点的LCA将是第一个和最后一个节点的LCA。
额外 作者 damned,
你能给全面的方法吗?我无法将您的算法转换为实际的代码。
额外 作者 javafan,