1、上堂課要點(diǎn)回顧森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)轉(zhuǎn)換為二叉樹(shù)二叉樹(shù)轉(zhuǎn)換為樹(shù)森林轉(zhuǎn)換為二叉樹(shù)二叉樹(shù)轉(zhuǎn)換為森林森林的遍歷先根深度優(yōu)先遍歷后根深度優(yōu)先遍歷二叉樹(shù)的應(yīng)用哈夫曼樹(shù)與哈夫曼編碼1第 十二 次 課閱讀： 朱戰(zhàn)立，第200-204頁(yè)習(xí)題： 作業(yè)112數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)的應(yīng)用38.7 等價(jià)問(wèn)題（并查集）基本概念1、等價(jià)關(guān)系(equivalence relation)：假定有一具有n個(gè)元素的非空集合S=1，2，n，另有一個(gè)具有r個(gè)關(guān)系的集合R=(i1,j1),(i2,j2),(ir,jr)，若R滿足：對(duì)所有的iS，有(i,i)R時(shí)，即關(guān)系是自反的對(duì)所有的i，jS，當(dāng)且僅當(dāng)(i,j)R時(shí)(j,i)R，

2、即關(guān)系是對(duì)稱的對(duì)所有的i，j S，若(i,j)R且(j,k)R，則有(i,j)R，即關(guān)系是傳遞的則稱關(guān)系R是定義在S上的一個(gè)等價(jià)關(guān)系，其中，i1等價(jià)于j1，i2等價(jià)于j2，ir等價(jià)于jr。42、等價(jià)類(equivalence classes)：設(shè)R是定義在非空集合S上的一個(gè)的等價(jià)關(guān)系，稱 是x的等價(jià)類。R可產(chǎn)生集合S的唯一劃分，即可以按R將S劃分為若干不相交的子集S1，S2，這些子集Si稱為S的R等價(jià)類。簡(jiǎn)言之，等價(jià)類是集合中相互等價(jià)的元素的最大子集合。5在一些應(yīng)用問(wèn)題中，給出各個(gè)元素之間的聯(lián)系，要求將這些元素分成幾個(gè)集合，每個(gè)集合中的元素直接或間接有聯(lián)系。在這類問(wèn)題中主要涉及的是對(duì)集合的合并

3、和查找，因此將這種集合稱為并查集。6例如：親戚 或許你并不知道，你的某個(gè)朋友是你的親戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子。如果能得到完整的家譜，判斷兩個(gè)人是否是親戚應(yīng)該是可行的，但如果兩個(gè)人的最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗(yàn)親戚關(guān)系實(shí)非人力所能及。在這種情況下，最好的幫手是計(jì)算機(jī)。 為了將問(wèn)題簡(jiǎn)化，你將得到一些親戚關(guān)系的信息，如同Xuebin和Grant是親戚，Grant和Tension是親戚等，從這些信息中，你可以推出Xuebin和Tension是親戚。請(qǐng)寫(xiě)一個(gè)程序，對(duì)于我們的關(guān)于親戚關(guān)系的提問(wèn)，以最快的速度給出答案。 7設(shè)初始有一集合S=0,1,2

4、,3,4,5,6,7,8,9,10,11，依次讀若干事先定義的等價(jià)對(duì)04,31,610,89,74,68,35,211,110.每次讀入一個(gè)等價(jià)對(duì)后，把等價(jià)集合union起來(lái)，則每讀入一個(gè)等價(jià)對(duì)后集合的狀態(tài)是:初始0,1,2,3,4,5,6,7,8,9,10,110 4 0,4,1,2,3,5,6,7,8,9,10,113 1 0,4, 1,3,2,5,6,7,8,9,10,116 10 0,4,1,3,2,5,6,10,7,8,9,11 8 9 0,4,1,3,2,5,6,10,7,8,9,117 4 0,4,7,1,3,2,5,6,10,8,9,116 8 0,4,7,1,3,2,5,6,

5、8,9,10,113 5 0,4,7,1,3,5,2,6,8,9,10,112 110,4,7,1,3,5,2,11,6,8,9,1011 00,2,4,7,11,1,3,5,6,8,9,108ADT UnionFindSet數(shù)據(jù)元素：seti=aj, i=0,1,n-1, j=0,1,ni-1 (n0, ni0)。其中ai0,1,2,n結(jié)構(gòu)：邏輯操作：設(shè)S為UnionFindSet型Initiate(S,n)：建立n個(gè)新集合，每個(gè)集合有唯一元素。要求各集合不相交的Find(S,x)：返回x的等價(jià)類名Union(S,x,y)：如果Find(S,x)！=find(S,y)，則把分別含有x和y的兩

6、個(gè)等價(jià)類合并成到一個(gè)等價(jià)類。每一次union操作使得集合的個(gè)數(shù)減少19算法性能參數(shù)nFind操作的次數(shù)mUnion操作的次數(shù)（至多n-1）10并查集實(shí)現(xiàn)方法1：數(shù)組表示法建立一大小為n的數(shù)組，其中每個(gè)元素是等價(jià)類名01234567891011下標(biāo)01234567891011等價(jià)類名, union(x,y):把所有的Find(x)改為Find(y)41234567891011 Union(0,4)：把所有的0改為441214567891011 Union(3,1)：把所有的3改為1412145107891011 Union(6,10)：把所有的6改為10412145107991011 Union

7、(8,9)：把所有的8改為9412145104991011 Union(7,4)：把所有的7改為44121459499911 Union(6,8)：把所有的10改為94525459499911 Union(3,5)：把所有的1改為545115459499911 Union(2,11)：把所有的2改為11454545949994 Union(11,0)：把所有的11改為411數(shù)組法算法分析操作時(shí)間效率操作執(zhí)行次數(shù)FindO(1)mUnionO(n)n-1將所有元素合并到一個(gè)集合：O(m+n2)12并查集實(shí)現(xiàn)方法2：鏈表表示法每個(gè)等價(jià)類用一個(gè)鏈表表示，第一個(gè)結(jié)點(diǎn)作其代表，初始n個(gè)鏈表兩個(gè)集合的鏈表

8、表示，其中一個(gè)集合cb,c,e,h，另一個(gè)集合fd,f,g。鏈表中每個(gè)結(jié)點(diǎn)包含一個(gè)集合成員、一個(gè)指向下一個(gè)集合元素結(jié)點(diǎn)的指針以及一個(gè)指向表中第一個(gè)結(jié)點(diǎn)的指針。每一個(gè)鏈表都有頭指針和尾指針，分別指向第一個(gè)和最后一個(gè)元素結(jié)點(diǎn)(b) union(c,f)的結(jié)果，代表為f。將第2個(gè)鏈表拼接在第一個(gè)鏈表表尾，原第2個(gè)鏈表的每個(gè)結(jié)點(diǎn)都需更新指向代表的指針13鏈表法算法分析操作時(shí)間效率操作執(zhí)行次數(shù)FindO(1)mUnionO(n)n-1將所有元素合并到一個(gè)集合：O(m+n2)14鏈表表示法的改進(jìn)：按秩合并啟發(fā)式策略假設(shè)每個(gè)等價(jià)類的鏈表中增加表的長(zhǎng)度信息在執(zhí)行union操作時(shí)總是把較短的表拼接到較長(zhǎng)的表上去

9、，這可以把結(jié)點(diǎn)更新的次數(shù)限制在O(log n)，因此Union操作時(shí)間效率O(logn)15改進(jìn)后的鏈表法算法分析操作時(shí)間效率操作執(zhí)行次數(shù)FindO(1)mUnionO(logn)n-1將所有元素合并到一個(gè)集合：O(m+nlogn)16并查集實(shí)現(xiàn)方法3：森林表示法每一個(gè)等價(jià)類用一棵樹(shù)表示，樹(shù)中每個(gè)結(jié)點(diǎn)是集合的一個(gè)成員，根是代表。如果兩個(gè)結(jié)點(diǎn)在同一棵樹(shù)中，則認(rèn)為它們?cè)谕粋€(gè)等價(jià)類中每個(gè)成員僅指向其父結(jié)點(diǎn)Find操作實(shí)現(xiàn)：沿著雙親結(jié)點(diǎn)指針一直向上找直至根結(jié)點(diǎn)Union操作實(shí)現(xiàn)：將一棵樹(shù)的根指向另一棵樹(shù)的根兩個(gè)集合的樹(shù)表示，其中一個(gè)集合cb,c,e,h，另一個(gè)集合fd,f,g。鏈表中每個(gè)結(jié)點(diǎn)包含一個(gè)

10、集合成員、一個(gè)指向雙親結(jié)點(diǎn)的指針。(b) union(c,f)的結(jié)果，代表為f。17BCDEFGHI序號(hào)01234567 B -1 E 0 F 0 C -1 D -1 G 4 H 5 I 5 data parent采用雙親表示法實(shí)現(xiàn)森林例：1810個(gè)結(jié)點(diǎn)A、B、C、D、E、F、G、H、J、K和它們的等價(jià)關(guān)系（A,B）、(C,K) 、(F,J) 、(E, H) 、(D,G) 、(A, K) 、(G, E) 、(H,J)初始狀態(tài)： 森林表示法示例 19對(duì)（A,B）、(C,K) 、(F, J) 、(E,H) 、(D,G)這5個(gè)等價(jià)對(duì)的處理結(jié)果森林表示法示例 20對(duì)兩個(gè)等價(jià)對(duì)（A, K）和（G, E

11、）的處理結(jié)果： 森林表示法示例 21并查集類型定義#define MaxTreeNode 20typedef struct int data; int parent;/雙親結(jié)點(diǎn)在數(shù)組的下標(biāo)，根的parent為-1 UFSTreeNode;UFSTreeNode ForestMaxTreeNode;/*存儲(chǔ)森林結(jié)點(diǎn)的數(shù)組*/22【并查集初始化算法】void Initiate(UFSTreeNode F ,int n)/*初始化并查集，并查集(森林)中最初有n個(gè)集合(樹(shù))，每個(gè)集合只有一個(gè)元素*/int i;for(i=0;i=0)i=Fi.parent;return i;24【并查集合并算法】v

12、oid Union(UFSTreeNode F ,int i, int j)/*合并，將根為j的樹(shù)并到根為i的樹(shù)上，即結(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)Frootj.parent=rooti;/*將rooti結(jié)點(diǎn)置為rootj結(jié)點(diǎn)的雙親*/25森林法算法分析操作時(shí)間效率操作執(zhí)行次數(shù)FindO(n)mUnionO(1)n-1將所有元素合并到一個(gè)集合：O(mn)26森林表示法的改進(jìn)1：按秩求并啟發(fā)式策略假設(shè)每個(gè)等價(jià)類的樹(shù)中增加樹(shù)中結(jié)點(diǎn)個(gè)數(shù)的

13、信息在執(zhí)行union操作時(shí)總是把包含較少結(jié)點(diǎn)的樹(shù)的根指向包含較多結(jié)點(diǎn)的樹(shù)的根，這可以把樹(shù)的整體深度限制在(log n)因此，F(xiàn)ind操作的效率O(logn)27森林法改進(jìn)1的算法分析操作時(shí)間效率操作執(zhí)行次數(shù)FindO(logn)mUnionO(1)n-1將所有元素合并到一個(gè)集合：O(mlogn+n)28森林法改進(jìn)1示例 使用按秩合并策略處理等價(jià)對(duì)（J,H）的結(jié)果：29森林表示法的改進(jìn)2：路徑壓縮啟發(fā)式策略一種可以產(chǎn)生極淺樹(shù)的聰明而簡(jiǎn)單的方法在執(zhí)行Find操作時(shí)將查找路徑上的每個(gè)結(jié)點(diǎn)都直接指向根結(jié)點(diǎn)。路徑壓縮不改變結(jié)點(diǎn)的秩30使用路徑壓縮策略處理等價(jià)對(duì)（H,E）的結(jié)果：森林法改進(jìn)2示例 31森林法改進(jìn)2的算法分析操作時(shí)間效率操作執(zhí)行次數(shù)FindO(log2+m/nn)mUnionO(1)n-1將所有元素合并