數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價(jià)問題-資料下載頁(yè)
2025-06-21 08:45本頁(yè)面
【正文】 //查找，返回包含結(jié)點(diǎn) i的樹的根結(jié)點(diǎn)下標(biāo) while(F[i].parent=0) i=F[i].parent。 return i。 } 【 并查集合并算法 】 void Union(UFSTreeNode F[ ],int i, int j) /*合并，將根為 j的樹并到根為 i的樹上，即結(jié)點(diǎn) j的雙親指向結(jié)點(diǎn) i*/ { int rooti, rootj。 rooti=Find(F,i)。 //找到結(jié)點(diǎn) i的根 rootj=Find(F,j)。 //找到結(jié)點(diǎn) j的根 if (rooti!=rootj) { F[rootj].parent=rooti。/*將 rooti結(jié)點(diǎn)置為rootj結(jié)點(diǎn)的雙親 */ } } 森林法算法分析 操作 時(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)。 路徑壓縮不改變結(jié)點(diǎn)的秩 使用路徑壓縮策略處理等價(jià)對(duì)（ H,E）的結(jié)果： 森林法改進(jìn) 2示例 森林法改進(jìn) 2的算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(log2+m/nn) m Union O(1) n1 將所有元素合并到一個(gè)集合： O(n+mlog2+m/nn) 森林法改進(jìn) 1+改進(jìn) 2的算法分析 操作 時(shí)間效率 操作執(zhí)行次數(shù) Find O(l) m Union O(1) n1 將所有元素合并到一個(gè)集合： O(m+n) 作業(yè) 11 算法設(shè)計(jì)題 ? 實(shí)現(xiàn) FindPathCompress（）函數(shù)功能，該函數(shù)在查找的同時(shí)實(shí)現(xiàn)路徑壓縮，將深層結(jié)點(diǎn)移近根結(jié)點(diǎn)。 ? 實(shí)現(xiàn) UnionRank（）函數(shù)功能，該函數(shù)實(shí)現(xiàn)按秩進(jìn)行合并的算法，其中的查找操作調(diào)用第一步的函數(shù)。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1