數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價問題-資料下載頁
2025-06-21 08:45本頁面
【正文】 //查找，返回包含結(jié)點 i的樹的根結(jié)點下標(biāo) while(F[i].parent=0) i=F[i].parent。 return i。 } 【 并查集合并算法 】 void Union(UFSTreeNode F[ ],int i, int j) /*合并，將根為 j的樹并到根為 i的樹上，即結(jié)點 j的雙親指向結(jié)點 i*/ { int rooti, rootj。 rooti=Find(F,i)。 //找到結(jié)點 i的根 rootj=Find(F,j)。 //找到結(jié)點 j的根 if (rooti!=rootj) { F[rootj].parent=rooti。/*將 rooti結(jié)點置為rootj結(jié)點的雙親 */ } } 森林法算法分析 操作 時間效率 操作執(zhí)行次數(shù) Find O(n) m Union O(1) n1 將所有元素合并到一個集合： O(mn) 森林表示法的改進(jìn) 1： —— 按秩求并啟發(fā)式策略 假設(shè)每個等價類的樹中增加樹中結(jié)點個數(shù)的信息 在執(zhí)行 union操作 時總是把包含較少結(jié)點的樹的根指向包含較多結(jié)點的樹的根，這可以把樹的整體深度限制在Ｏ (log n) 因此， Find操作的效率 O(logn) 森林法改進(jìn) 1的算法分析 操作 時間效率 操作執(zhí)行次數(shù) Find O(logn) m Union O(1) n1 將所有元素合并到一個集合： O(mlogn+n) 森林法改進(jìn) 1示例 使用按秩合并策略處理等價對（ J,H）的結(jié)果： 森林表示法的改進(jìn) 2： —— 路徑壓縮啟發(fā)式策略 一種可以產(chǎn)生極淺樹的聰明而簡單的方法 在執(zhí)行 Find操作 時將查找路徑上的每個結(jié)點都直接指向根結(jié)點。 路徑壓縮不改變結(jié)點的秩 使用路徑壓縮策略處理等價對（ H,E）的結(jié)果： 森林法改進(jìn) 2示例 森林法改進(jìn) 2的算法分析 操作 時間效率 操作執(zhí)行次數(shù) Find O(log2+m/nn) m Union O(1) n1 將所有元素合并到一個集合： O(n+mlog2+m/nn) 森林法改進(jìn) 1+改進(jìn) 2的算法分析 操作 時間效率 操作執(zhí)行次數(shù) Find O(l) m Union O(1) n1 將所有元素合并到一個集合： O(m+n) 作業(yè) 11 算法設(shè)計題 ? 實現(xiàn) FindPathCompress（）函數(shù)功能，該函數(shù)在查找的同時實現(xiàn)路徑壓縮，將深層結(jié)點移近根結(jié)點。 ? 實現(xiàn) UnionRank（）函數(shù)功能，該函數(shù)實現(xiàn)按秩進(jìn)行合并的算法，其中的查找操作調(diào)用第一步的函數(shù)。
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1