【正文】 親 */ } } 森林法算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(n) m Union O(1) n1 將所有元素合并到一個(gè)集合： O(mn) 森林表示法的改進(jìn) 1： —— 按秩求并啟發(fā)式策略 假設(shè)每個(gè)等價(jià)類的樹中增加樹中結(jié)點(diǎn)個(gè)數(shù)的信息 在執(zhí)行 union操作 時(shí)總是把包含較少結(jié)點(diǎn)的樹的根指向包含較多結(jié)點(diǎn)的樹的根，這可以把樹的整體深度限制在Ｏ (log n) 因此， Find操作的效率 O(logn) 森林法改進(jìn) 1的算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(logn) m Union O(1) n1 將所有元素合并到一個(gè)集合： O(mlogn+n) 森林法改進(jìn) 1示例 使用按秩合并策略處理等價(jià)對(duì)（ J,H）的結(jié)果： 森林表示法的改進(jìn) 2： —— 路徑壓縮啟發(fā)式策略 一種可以產(chǎn)生極淺樹的聰明而簡(jiǎn)單的方法 在執(zhí)行 Find操作 時(shí)將查找路徑上的每個(gè)結(jié)點(diǎn)都直接指向根結(jié)點(diǎn)。i++) { F[i].data=i。其中 ai∈ {0,1,2,……,n} 結(jié)構(gòu)： 邏輯操作：設(shè) S為 UnionFindSet型 ? Initiate(S,n)：建立 n個(gè)新集合，每個(gè)集合有唯一元素。 R可產(chǎn)生集合 S的唯一劃分 ，即可以按 R將 S劃分為若干不相交的子集 S1， S2， … ，這些子集 Si稱為 S的 R等價(jià)類 。將第 2個(gè)鏈表拼接在第一個(gè)鏈表表尾，原第 2個(gè)鏈表的每個(gè)結(jié)點(diǎn)都需更新指向代表的指針 鏈表法算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(1) m Union O(n) n1 將所有元素合并到一個(gè)集合： O(m+n2) 鏈表表示法的改進(jìn)： —— 按秩合并啟發(fā)式策略 假設(shè)每個(gè)等價(jià)類的鏈表中增加表的長(zhǎng)度信息 在執(zhí)行 union操作時(shí)總是把較短的表拼接到較長(zhǎng)的表上去，這可以把結(jié)點(diǎn)更新的次數(shù)限制在 O(log n)，因此 Union操作時(shí)間效率 O(logn) 改進(jìn)后的鏈表法算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(1) m Union O(logn) n1 將所有元素合并到一個(gè)集合： O(m+nlogn) 并查集實(shí)現(xiàn)方法 3： 森林表示法 每一個(gè)等價(jià)類用一棵樹表示，樹中每個(gè)結(jié)點(diǎn)是集合的一個(gè)成員，根是代表。 rooti=Find(F,i)。 return i。鏈表中每個(gè)結(jié)點(diǎn)包含一個(gè)集合成員、一個(gè)指向下一個(gè)集合元素結(jié)點(diǎn)的指針以及一個(gè)指向表中第一個(gè)結(jié)點(diǎn)的指針。上堂課要點(diǎn)回顧 森林與二叉樹的轉(zhuǎn)換 ? 樹轉(zhuǎn)換為二叉