數(shù)據(jù)結(jié)構(gòu)chapter樹和二叉樹等價問題學(xué)習(xí)教案

1、會計學(xué)1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)chapter樹和二樹和二叉樹等價問題叉樹等價問題第一頁，共34頁。第1頁/共34頁第二頁，共34頁。二叉樹二叉樹數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(sh j ji u)的應(yīng)用的應(yīng)用第2頁/共34頁第三頁，共34頁。8.7 8.7 等價等價(dngji)(dngji)問題（并問題（并查集）查集）基本概念基本概念1、等價關(guān)系、等價關(guān)系(equivalence relation)：假定有一具有：假定有一具有n個元素個元素(yun s)的非空集合的非空集合S=1，2，n，另，另有一個具有有一個具有r個關(guān)系的集合個關(guān)系的集合R=(i1,j1),(i2,j2),(ir,jr)

2、，若，若R滿足：滿足：對所有的對所有的iS，有，有(i,i)R時，即關(guān)系是自反的時，即關(guān)系是自反的對所有的對所有的i，jS，當且僅當，當且僅當(i,j)R時時(j,i)R，即，即關(guān)系是對稱的關(guān)系是對稱的對所有的對所有的i，j S，若，若(i,j)R且且(j,k)R，則有，則有(i,j)R，即關(guān)系是傳遞的，即關(guān)系是傳遞的則稱關(guān)系則稱關(guān)系R是定義在是定義在S上的一個等價關(guān)系，其中，上的一個等價關(guān)系，其中，i1等價于等價于j1，i2等價于等價于j2，ir等價于等價于jr。第3頁/共34頁第四頁，共34頁。l2、等價類、等價類(equivalence classes)：設(shè)：設(shè)R是定義在非空是定義在非空

3、集合集合S上的一個的等價關(guān)系，上的一個的等價關(guān)系，l稱稱 是是x的等價類。的等價類。R可產(chǎn)生集合可產(chǎn)生集合S的唯一劃分，的唯一劃分，即可以按即可以按R將將S劃分為若干不相交的子集劃分為若干不相交的子集S1，S2，這些子集這些子集Si稱為稱為(chn wi)S的的R等價類。簡言之，等價類。簡言之，等價類是集合中相互等價的元素的最大子集合。等價類是集合中相互等價的元素的最大子集合。| ,xRySyyxSxRRx第4頁/共34頁第五頁，共34頁。第5頁/共34頁第六頁，共34頁。例如：親戚例如：親戚 或許你并不知道，你的某個朋友是你或許你并不知道，你的某個朋友是你的親戚。他可能是你的曾祖父的外公的的

4、親戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孫子女婿的外甥女的表姐的孫子(sn zi)。如。如果能得到完整的家譜，判斷兩個人是否果能得到完整的家譜，判斷兩個人是否是親戚應(yīng)該是可行的，但如果兩個人的是親戚應(yīng)該是可行的，但如果兩個人的最近公共祖先與他們相隔好幾代，使得最近公共祖先與他們相隔好幾代，使得家譜十分龐大，那么檢驗親戚關(guān)系實非家譜十分龐大，那么檢驗親戚關(guān)系實非人力所能及。在這種情況下，最好的幫人力所能及。在這種情況下，最好的幫手是計算機。手是計算機。 為了將問題簡化，你將得到一些親戚為了將問題簡化，你將得到一些親戚關(guān)系的信息，如同關(guān)系的信息，如同Xuebin和和Grant是親戚是親

5、戚，Grant和和Tension是親戚等，從這些信息是親戚等，從這些信息中，你可以推出中，你可以推出Xuebin和和Tension是親戚是親戚。請寫一個程序，對于我們的關(guān)于親戚。請寫一個程序，對于我們的關(guān)于親戚關(guān)系的提問，以最快的速度給出答案。關(guān)系的提問，以最快的速度給出答案。 第6頁/共34頁第七頁，共34頁。0,4,1,2,3,5,6,7,8,9,10,11n3 1 0,4, 1,3,2,5,6,7,8,9,10,11n6 10 0,4,1,3,2,5,6,10,7,8,9,11 n8 9 0,4,1,3,2,5,6,10,7,8,9,11n7 4 0,4,7,1,3,2,5,6,10,8

6、,9,11n6 8 0,4,7,1,3,2,5,6,8,9,10,11n3 5 0,4,7,1,3,5,2,6,8,9,10,11n2 110,4,7,1,3,5,2,11,6,8,9,10n11 00,2,4,7,11,1,3,5,6,8,9,10第7頁/共34頁第八頁，共34頁。=find(S,y)，則把分別含有，則把分別含有x和和y的的兩個等價類合并兩個等價類合并(hbng)成到一個成到一個等價類。每一次等價類。每一次union操作使得集操作使得集合的個數(shù)減少合的個數(shù)減少1)(jisetsetji第8頁/共34頁第九頁，共34頁。第9頁/共34頁第十頁，共34頁。0 1 2 3 4 5

7、6 7 8 9 10 11下標下標0 1 2 3 4 5 6 7 8 9 10 11等價類名等價類名, union(x,y):把所有的把所有的Find(x)改為改為Find(y)4 1 2 3 4 5 6 7 8 9 10 11 Union(0,4)：把所有的把所有的0改為改為44 1 2 1 4 5 6 7 8 9 10 11 Union(3,1)：把所有的把所有的3改為改為14 1 2 1 4 5 10 7 8 9 10 11 Union(6,10)：把所有的把所有的6改為改為104 1 2 1 4 5 10 7 9 9 10 11 Union(8,9)：把所有的把所有的8改為改為94 1

8、 2 1 4 5 10 4 9 9 10 11 Union(7,4)：把所有的把所有的7改為改為44 1 2 1 4 5 9 4 9 9 9 11 Union(6,8)：把所有的把所有的10改為改為94 5 2 5 4 5 9 4 9 9 9 11 Union(3,5)：把所有的把所有的1改為改為54 5 11 5 4 5 9 4 9 9 9 11 Union(2,11)：把所有的把所有的2改為改為114 5 4 5 4 5 9 4 9 9 9 4 Union(11,0)：把所有的把所有的11改為改為4第10頁/共34頁第十一頁，共34頁。操作操作 時間效率時間效率 操作執(zhí)行次數(shù)操作執(zhí)行次數(shù)F

9、indO(1)mUnionO(n)n-1將所有元素合并將所有元素合并(hbng)到一個集合：到一個集合：O(m+n2)第11頁/共34頁第十二頁，共34頁。(a)兩個集合兩個集合(jh)的鏈表表示，其中一個集合的鏈表表示，其中一個集合(jh)cb,c,e,h，另一個集合，另一個集合(jh)fd,f,g。鏈表中每個結(jié)點包含一個集合。鏈表中每個結(jié)點包含一個集合(jh)成員、一個指向下一個集合成員、一個指向下一個集合(jh)元素結(jié)點的指針以及一個指向表中第一個結(jié)點的指針。每一個鏈表都有頭指針和尾指針，分別指向第一個和最后一個元素結(jié)點元素結(jié)點的指針以及一個指向表中第一個結(jié)點的指針。每一個鏈表都有頭指針

10、和尾指針，分別指向第一個和最后一個元素結(jié)點(b)(b) union(c,f)的結(jié)果，代表為的結(jié)果，代表為f。將第。將第2個鏈表拼接在第一個鏈表表尾，原第個鏈表拼接在第一個鏈表表尾，原第2個鏈表的每個結(jié)點都需更新指向代表的指針個鏈表的每個結(jié)點都需更新指向代表的指針第12頁/共34頁第十三頁，共34頁。操作操作 時間效率時間效率 操作執(zhí)行次數(shù)操作執(zhí)行次數(shù)FindO(1)mUnionO(n)n-1將所有元素合并到一個將所有元素合并到一個(y )集合：集合：O(m+n2)第13頁/共34頁第十四頁，共34頁。第14頁/共34頁第十五頁，共34頁。操作操作 時間效率時間效率 操作執(zhí)行次數(shù)操作執(zhí)行次數(shù)Fi

11、ndO(1)mUnionO(logn)n-1將所有元素合并將所有元素合并(hbng)到一個集合：到一個集合：O(m+nlogn)第15頁/共34頁第十六頁，共34頁。Find操作實現(xiàn)：沿著雙親結(jié)點指針操作實現(xiàn)：沿著雙親結(jié)點指針一直向上找直至根結(jié)點一直向上找直至根結(jié)點Union操作實現(xiàn)：將一棵樹的根指操作實現(xiàn)：將一棵樹的根指向向(zh xin)另一棵樹的根另一棵樹的根(a)兩個集合的樹表示，其中一個集合兩個集合的樹表示，其中一個集合cb,c,e,h，另一個集合，另一個集合fd,f,g。鏈表中每個結(jié)點包含一個集合成員、一個指向。鏈表中每個結(jié)點包含一個集合成員、一個指向(zh xin)雙親結(jié)點的指針

12、。雙親結(jié)點的指針。(b)(b) union(c,f)的結(jié)果，代表為的結(jié)果，代表為f。第16頁/共34頁第十七頁，共34頁。BCDEFGHI序號序號01234567 B -1 E 0 F 0 C -1 D -1 G 4 H 5 I 5 data parent采用采用(ciyng)雙親表示法實現(xiàn)森林雙親表示法實現(xiàn)森林例：例：第17頁/共34頁第十八頁，共34頁。10個結(jié)點個結(jié)點(ji din)A、B、C、D、E、F、G、H、J、K和它們的等價關(guān)系（和它們的等價關(guān)系（A,B）、）、(C,K) 、(F,J) 、(E, H) 、(D,G) 、(A, K) 、(G, E) 、(H,J)初始狀態(tài)：初始狀態(tài)：

13、 第18頁/共34頁第十九頁，共34頁。對（對（A,B）、）、(C,K) 、(F, J) 、(E,H) 、(D,G)這這5個等價個等價(dngji)對的處理結(jié)果對的處理結(jié)果第19頁/共34頁第二十頁，共34頁。對兩個對兩個(lin )等價對（等價對（A, K）和（）和（G, E ）的處理結(jié)）的處理結(jié)果：果： 第20頁/共34頁第二十一頁，共34頁。第21頁/共34頁第二十二頁，共34頁。Fi.parent=-1; 第22頁/共34頁第二十三頁，共34頁。第23頁/共34頁第二十四頁，共34頁。結(jié)點置為結(jié)點置為rootj結(jié)點的雙親結(jié)點的雙親(shungqn)*第24頁/共34頁第二十五頁，共34

14、頁。操作操作 時間效率時間效率 操作執(zhí)行次數(shù)操作執(zhí)行次數(shù)FindO(n)mUnionO(1)n-1將所有元素合并到一個將所有元素合并到一個(y )集合：集合：O(mn)第25頁/共34頁第二十六頁，共34頁。第26頁/共34頁第二十七頁，共34頁。操作操作 時間效率時間效率 操作執(zhí)行次數(shù)操作執(zhí)行次數(shù)FindO(logn)mUnionO(1)n-1將所有將所有(suyu)元素合并到一個集合：元素合并到一個集合：O(mlogn+n)第27頁/共34頁第二十八頁，共34頁。使用按秩合并使用按秩合并(hbng)策略處理等價對（策略處理等價對（J,H）的）的結(jié)果：結(jié)果：第28頁/共34頁第二十九頁，共34頁。第29頁/共34頁第三十頁，共34頁。使用路徑壓縮策略處理等價使用路徑壓縮策略處理等價(dngji)對（對（H,E）的）的結(jié)果：結(jié)果：森林法改進森林法改進(gijn)2示例示例 第30頁/共34頁第三十一頁，共34頁。操作操作時間效率時間效率操作執(zhí)行次