堆與互不相交集課件(文件)
【正文】 (x)。 秩運(yùn)算規(guī)則： 若 rank(x) rank(y)，則 x為 y的父節(jié)點(diǎn)； 若 rank(x) rank(y)，則 y 為 x的父節(jié)點(diǎn)； 若 rank(x)= rank(y)，則 y為 x的父節(jié)點(diǎn)， rank(y)增 1； 這樣，克服 UNION退化為線性的缺點(diǎn)，在 n次尋找運(yùn)算的代價(jià)為 。在 Union(rank(x)， rank(y))運(yùn)算 下，分三種情況討論： 1. 若 rank(x)rank(y)，則 y 為樹根節(jié)點(diǎn)， 節(jié)點(diǎn)，而 rank(y)不變。 )(2 xrank02)(2 yrank)(2 xrank不相交集 2. 若 rank(x)rank(y)，則 x為樹根節(jié)點(diǎn)， 節(jié)點(diǎn)，而 rank(x)不變。 T是以 x為根，且有 n個(gè)結(jié)點(diǎn)，其高度至多為 。y=x 6 while p(y)?null 7 w=p(y)。 推論 ：任何節(jié)點(diǎn)的秩最大是 。所以，它所需要的執(zhí)行時(shí)間實(shí)際上將是 。 其中， 定義為： )(mO0?r r rn2? ?nlogm)()lo g( * mOnmO ?n*log?n*log ?0 1,0?n}1l o gl o gl o g0m i n { ?? ni ? 2?n52l o g,42l o g,32l o g,22l o g,12l o g 65536*16*4*2** ????? 。y=w。 算法 UNION 輸入：兩個(gè)元素 x和 y 輸出：包含 x和 y的兩樹的合并，原來的樹被破壞 1 u=FIND(x)。 3. 若 rank(x)=rank(y)，則 y為樹根節(jié)點(diǎn)， + = 節(jié)點(diǎn)，引理成立。一旦 x變成了其他節(jié)點(diǎn)的 一個(gè)子節(jié)點(diǎn)，它的秩就不再改變了。 觀察結(jié)論 1： rank(p(x))?rank(x)+1 )(n?)log( nnO不相交集 證明 基礎(chǔ)： x本身是一棵樹，其秩為 rank(x)=0，節(jié)點(diǎn)數(shù)為 成立。 n1 n 1 2 ?不相交集 ? 合并措施 秩：節(jié)點(diǎn) x中存儲的一個(gè)非負(fù)整數(shù)，以表示樹的高度，記 為 rank(x)。 不相交集 0 3 0 8 2 2 1 0 0 1 1 1 2 3 4 5 6 7 8 9 10 11 1 7 10 11 3 2 5 6 8 4 9 顯然，運(yùn)算 UNION缺點(diǎn)是使樹退化為線性結(jié)構(gòu)。 樹根節(jié)點(diǎn)：無父節(jié)點(diǎn)，置為 0； 孩子節(jié)點(diǎn)：指向父節(jié)點(diǎn)，置為父節(jié)點(diǎn)下標(biāo)。如對集合 定義如下的等價(jià)關(guān)系：
法律信息相關(guān)推薦
鄂ICP備17016276號-1