3

我正在尝试找到一种快速算法来识别包含相同数据的节点（A，B）对，这些节点（A，B）以这样的方式定位在树上，即节点 A 作为祖先，节点 B OR B 是A 的祖先。

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

示例树

  • n6并且n1是匹配的，因为n1是 的祖先n6。
  • n5并且n3是匹配的，因为n3是 的兄弟n2，它是 的祖先n5。
  • n3并且n7出于同样的原因是匹配的。
  • n5并且n7不是匹配项，因为n7既不是 的祖先n5，也不是 的祖先之一的兄弟姐妹n5。
  • n2并且n4出于同样的原因不匹配。

“规则检查器”的幼稚实现是微不足道的，但它需要多次遍历树（检查每个节点一次），但是我觉得我可以利用树的两个特殊属性来实现一些更好的解决方案. 有问题的两个属性是：

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

...但是尽管我坚信必须有一种快速的方法来找到匹配的节点，但我到目前为止还没有找到它。

我目前正在使用 python，但也欢迎使用其他不太开放的语言的伪代码或示例。

4

1 回答 1

2

我相信这是解决方案。在预先计算 dfs-visiting-time 成本 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 的兄弟姐妹的后代，当且仅当A 是 B 的直系父亲的后代。而且（感谢@mac）A 不是 B 的兄弟姐妹之一。而且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 是 B 的兄弟姐妹的后代，当且仅当A 是 B 的直系父亲的后代。而且（感谢@mac）A 不是 B 的兄弟姐妹之一。而且A也不是B的后代。

自从：

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

  1. B.fa
  2. 乙
  3. B的兄弟姐妹
  4. B的后代
  5. B的兄弟姐妹的后代

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

如果 A 不是 B 的直系父亲的后代，则 A 不在子树中。很明显，A 永远不可能是 B 的兄弟姐妹的后代，因为 B 的所有兄弟姐妹都在子树中。

于 2012-08-17T02:49:40.497 回答