我有一棵树和3个节点ABC。问题是找到AB在它们到C的最短路径上共享的路径的大小。
有三种情况:
CAB的祖先时在这种情况下,答案是min(depth(A), depth(B)) - depth(C)
CA的祖先,但不是B或vice-vs时在这种情况下,答案是1,只是nodeC
这是一个我搞不清AB都不是C的后代的情况。
我有很多问题,所以我需要一个有效的方法不管我们可以在O(logN)中获取每个lca,每个查询都应该是O(1)

最佳答案

树修正算法
我能想到的最简单的算法可能需要修改源树,这取决于它的初始表示。
我们需要把树根变成树根。所以我们需要改变树中的父子关系。
找到CAlowest common ancestor (LCA)。LCA是最大深度的节点,是BA(和B)的祖先。
答案是LCA(A, A) = A
无树修改算法
如果我们不能转换树,那么:
如果depth(LCA(A,B))CA的祖先,那么答案是B(你在这个问题上犯了个错误。)
algorithm - 树中的共享路径-LMLPHP
如果depth(LCA(A, B)) - depth(C) + 1C的祖先而不是A,那么答案是B。(反之亦然)
algorithm - 树中的共享路径-LMLPHP
如果1C的后代而不是A,那么答案是B。(反之亦然)
algorithm - 树中的共享路径-LMLPHP
如果depth(C) - depth(A) + 1CA的后代,那么答案是B
algorithm - 树中的共享路径-LMLPHP
如果depth(C) -max(depth(A), depth(B)) + 1不是CA的祖先或后代,答案将是B和顶点C之间的距离,该距离等于D = LCA(A, B)
algorithm - 树中的共享路径-LMLPHP
更新:现在问题中出现了每个操作的depth(C) + depth(D) - 2*depth(LCA(C, D)) + 1要求。我认为只有这样才能保证O(1)时间复杂度是预先计算所有O(1)。例如,这可以通过Tarjan's off-line LCA algorithm来实现。

10-05 20:52
查看更多