algorithm - 快速检测与祖先同级的相同节点

Question

I am trying to find a fast algorithm to identify couples of nodes (A, B) that contains the same data and that are positioned on a tree in such way that a node A has as an ancestor the node B OR B is the sibling of an ancestor of A.

以下面的树为例，其中的颜色标识了内容:

• n6 和 n1 匹配 因为 n1 是 n6 的祖先>.
• n5 和 n3 匹配 因为 n3 是 n2 的兄弟>，它是 n5 的祖先。
• n3 和 n7 是一个匹配项，原因相同。
• n5 和 n7 不匹配 因为 n7 既不是 n5< 的祖先，也不是 n5 的祖先之一的 sibling 。
出于同样的原因，
• n2 和 n4 不匹配。

“规则检查器”的简单实现是微不足道的，但它需要多次遍历树(对每个被检查的节点一次)，但是我觉得我可以利用我的树的两个特殊属性来实现一些更好的解决方案。有问题的两个属性是:

• 我可以获得具有相同内容的所有节点的平面列表(在上面的示例中我会得到:(n5, n3, n7), (n1, n6), (n2, n4).
• 我的每个节点都存储对其父节点及其所有子节点的引用(可以递归地利用此属性，就像链表一样)。

...但是尽管我坚信必须有一种快速的方法来找到匹配的节点，但我至今未能找到它。

我目前在 python 中工作，但也欢迎使用其他不太通俗易懂的语言编写的伪代码或示例。

Answer 1

我相信这是解决方案。在预先计算 dfs 访问时间成本 O(n) 之后，该解决方案需要 O(1) 来回答每个查询。

dfs 看起来像:

nowtime=0
def dfs(node):
    global nowtime
    nowtime+=1
    node.come_time=nowtime
    for i in node.sons:
        dfs(i)
    nowtime+=1
    node.leave_time=nowtime
dfs(root)

然后，我们有:

B 是 A 的祖先，当且仅当我们有

B.come_time < A.come_time 和B.leave_time > A.leave_time

我认为这是真的:

A 是 B sibling 的后代，当且仅当 A 是 B 直系父亲的后代。并且(感谢@mac)A 不是 B 的 sibling 之一。而且 A 也不是 B 的后代。

所以我们可以检查:

B.fa.come_time < A.come_time 和B.fa.leave_time > A.leave_time

和

B.fa != A.fa

总而言之，要回答一个问题，我们有:

def check(A,B):
    if B.come_time<A.come_time and B.leave_time>A.leave_time:
        return True
    if B.has_father() and A.has_father():
        if A.fa==B.fa:
            return False
        if B.fa.come_time<A.come_time and B.fa.leave_time>A.leave_time:
            return True
    return False

此解决方案的关键思想是使用 dfs() 中的访问时间来检查节点 B 是否是另一个节点 A 的祖先。 [come_time, leave_time] 间隔正是节点保留在堆栈中的时间间隔。很容易验证在 dfs 过程中，祖先的访问时间间隔将包含它所有后代的时间间隔，因为当 dfs() 访问它的后代时它总是在堆栈中。

添加:

我们可以证明:

A is a descendant of B's siblings, if and only if A is a descendant of B's direct father. And (thanks to @mac) A is not one of B's siblings. And also A is not a descendant of B.

自:

如果A是B的直接父亲的后代，那么A在以B.fa为根的子树中子树包含且仅包含:

1. B.fa
2. B
3. B的 sibling
4. B的后代
5. B sibling 的后代

所以，如果 A 不在 1、不在 2、不在 3、不在 4，那么 A 一定在 5。

如果A不是B的直接父亲的后代，那么A不在子树中。很明显，A 永远不可能是 B 的 sibling 的后代，因为 B 的所有 sibling 都在子树中。