数据结构 哈夫曼树.ppt

Each element of S forms a equivalence subset of their own. S1,S2,…,Sn Read an equivalence pair x ≡ y, determine which subset that x and y are belong to. If they are different, then the two sets are to be replaced by their union. After processing all equivalence relations, these non-empty subsets are equivalence classes of R on S. Equivalence Classes Generation Algorithm The Algorithm Initialize N disjoint sets; /* read in all the relations */ while ( read in a ≡ b ) { if ( ! (Find(a) == Find(b)) ) Union the two sets; } /* output the result */ output all remaining sets; 0 1 2 3 4 5 6 data parent Representation :Parent linked list A B C D E F 〖Example〗 S1 = { 6, 7, 8, 10 }, S2 = { 1, 4, 9 }, S3 = { 2, 3, 5 } 10 6 8 7 4 1 9 2 3 5 A possible forest representation of these sets Note: Pointers are from children to parents ? Operations : (1) Union( i, j ) ::= Replace Si and Sj by S = Si ? Sj (2) Find( i ) ::= Find the set Sk which contains the element i. Representation :Parent linked list ? Union ( i, j ) Idea: Make Si a subtree of Sj , or vice versa. That is, we can set the parent pointer of one root to the other’s root. 10 6 8 7 4 1 9 4 1 9 10 6 8 7 S1 ? S2 S2 ? S1 Note: the parent of root is -1. The root’s index represents the set name. 10 6 8 7 4 1 9 2 3 5 〖Example〗The array representation of the three sets are: ( S1 ? S2 ? S1 ) ? S [ 4 ] = 10 [1] 4 [2] -1 [10] -1 [9] 4 [8] 10 [7] 10 [6] 10 [5] 2 [4] -1 [3] 2 S ? Union ( i, j ) 10 6 8 7 4 1 9 2 3 5 [1] 4 [2] -1 [10] -1 [9] 4 [8] 10 [7] 10 [6] 10 [5] 2 [4] 10 [3] 2 S int find( MFSet S, int i){ if( i1 || iS.n) return -1; for( j=i; S.nodes[j].parent=0; j=S.nodes[j].parent); return j; } int Union( MFSet s, int i, int j){ if( i1||iS.n||j1||jS.n) return ERROR; S.nodes[i].parent=j; return j; } O(tree height) O( 1) Smart Union Strategies 4 2 9 30 5 13 11 1 7 8 3 22 6 10 20 16 14 12 union(7,13) Which tree should become a subtree of the other? Height Rule M