首页 > 试题广场 >

假设对UNION过程做一个简单的改动,在采用链表表示中拿掉让

[问答题]
假设对UNION过程做一个简单的改动,在采用链表表示中拿掉让集合对象的tail指针总指向每个表的最后一个对象的要求。无论是使用还是不使用加权合并启发式策略,这个修改不应该改变UNION过程的渐近运行时间(提示:而不是把一个表链接到另一个表后面,将它们拼接到一起)
UNION(u,v){
    LINK(FIND-SET(u),== FIND-SET(v))
}
LINK(x,y){
    if x.rank > y.rank
        y.p = x
    else
        x.p = y
        if x.rank == y.rank
            y.rank++
}

这道题你会答吗?花几分钟告诉大家答案吧!