我试图找到一种快速算法来识别节点对(A,
b)包含相同数据并位于
一个节点A有一个祖先节点B或B是
A的祖先的兄弟姐妹。
以下面的树为例,其中颜色标识内容:
n6n1是匹配的,因为n1n6的祖先。
n5n3是匹配项,因为n3n2的兄弟,而n5n3的祖先。
n7n5出于同样的原因是匹配的。
n7n7不是匹配项,因为n5既不是n5的祖先,也不是n2的祖先之一的兄弟姐妹。
n4(n5, n3, n7)不匹配的原因是相同的。
“规则检查器”的天真实现是微不足道的,但是它需要多次遍历树(每个被检查的节点一次),但是我感觉我可以利用树的两个特殊属性来实现一些更好的解决方案。所讨论的两个属性是:
我可以得到具有相同内容的所有节点的简单列表(在上面的示例中,我将得到:(n1, n6)(n2, n4),。
我的每个节点都存储对其父节点和所有子节点的引用(可以递归地利用此属性,如链表)。
……但尽管我坚信一定有一种快速找到匹配节点的方法,但我至今未能找到它。
我目前在python中工作,但也欢迎使用伪代码或其他不太开放的语言中的示例。

最佳答案

我相信这是解决办法。在预先计算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.请假时间A.请假时间
我想这是真的:
A是B的兄弟姐妹的后代,如果且仅当A是B的直系父亲的后代。而且(多亏了@mac)a不是b的兄弟姐妹之一。而且A也不是B的后代。
所以我们可以检查:
b.fa.come_timea.leave_time

B.FA!=α.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的子树中。
子树包含且仅包含:
B.FA公司

B的兄弟姐妹
B的后代
B的兄弟姐妹的后代
所以,如果a不是1,不是2,不是3,不是4,那么a必须是5。
如果a不是b的直系父的后代,那么a不在子树中。很明显,a不可能是b的兄弟姐妹的后代,因为b的所有兄弟姐妹都在子树中。

关于algorithm - 快速检测作为祖先兄弟的相同节点,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/11996547/

10-11 06:26
查看更多