【1】灵巧求并算法——按集合大小求并1.1）大小求并法定义：上面的Union执行是相当任意的， 通过使第二棵树 成为第一棵树的子树而完成合并；对其的改进是借助任意的方法打破现有关系， 使得总让较小的树成为较大树的子树，我们把这种方法叫做 大小求并法；
1.2）可以看到， 如果Union 操作都是按照大小求并的话，那么任何节点的深度均不会超过 logN；
1.3）首先注意节点的深度为0， 然后它的深度随着一次 Union 的结果而增加的时候，该节点则被置于至少是 它以前所在树两倍大的一棵树上；因此，它的深度最多可以增加 logN次；
- 1.3.2） Find 操作 的运行时间为 O（logN）， 而连续M次操作则花费 O（MlogN）；
- 1.3.3） 下图指出在16次Union操作后可能得到这种最坏的树；而且如果所有的Union都对相等大小的树进行， 那么这样的树是会得到的；
1.4）为了实现这种方法， 我们需要记住每个树的大小。由于我们实际上只使用一个数组，因此可以让每个根的数组元素包含它 的树的大小的负值；
1.5）已经证明：若使用按大小求并则连续 M次运算需要 O（M）平均时间， 这是因为 当随机的Union执行时， 整个算法一般只有一些很小的集合（通常是一个元素）与 大 集合 合并；
1.6）souce code + printing
#include <stdio.h>#include <malloc.h>#define ElementType int#define Error(str) printf("\n error: %s \n",str) struct UnionSet;typedef struct UnionSet* UnionSet;// we adopt the child-sibling exprstruct UnionSet{ int parent; int size; ElementType value;};UnionSet makeEmpty(); UnionSet* initUnionSet(int size, ElementType* data);void printSet(UnionSet* set, int size);void printArray(ElementType data[], int size);int find(ElementType index, UnionSet* set);// initialize the union set UnionSet* initUnionSet(int size, ElementType* data){ UnionSet* set; int i; set = (UnionSet*)malloc(size * sizeof(UnionSet)); if(!set) { Error("out of space, from func initUnionSet"); return NULL; } for(i=0; i<size; i++) { set = makeEmpty(); if(!set) return NULL; set->value = data; } return set;}// allocate the memory for the single UnionSet and evaluate the parent and size -1UnionSet makeEmpty(){ UnionSet temp; temp = (UnionSet)malloc(sizeof(struct UnionSet)); if(!temp) { Error("out of space, from func makeEmpty!"); return NULL; } temp->parent = -1; temp->size = 1; return temp;}// merge set1 and set2 by sizevoid setUnion(UnionSet* set, int index1, int index2){ //judge whether the index1 or index2 equals to -1 ,also -1 represents the root if(index1 != -1) index1 = find(index1, set); if(index2 != -1) index2 = find(index2, set); if(set[index1]->size > set[index2]->size) { set[index2]->parent = index1; set[index1]->size += set[index2]->size; } else { set[index1]->parent = index2; set[index2]->size += set[index1]->size; }} //find the root of one set whose value equals to given valueint find(ElementType index, UnionSet* set) { UnionSet temp; while(1) { temp = set[index]; if(temp->parent == -1) break; index = temp->parent; } return index; } int main(){ int size; UnionSet* unionSet; ElementType data[] = {110, 245, 895, 658, 321, 852, 147, 458, 469, 159, 347, 28}; size = 12; printf("\n\t====== test for union set by size ======\n"); //printf("\n\t=== the initial array is as follows ===\n"); //printArray(data, size); printf("\n\t=== the init union set are as follows ===\n"); unionSet = initUnionSet(size, data); // initialize the union set over printSet(unionSet, size); printf("\n\t=== after union(1,5) + union(2,5) + union(3,4) + union(4,5) ===\n"); setUnion(unionSet, 1, 5); setUnion(unionSet, 2, 5); setUnion(unionSet, 3, 4); setUnion(unionSet, 4, 5); printSet(unionSet, size); printf("\n\t=== after union(9,8) + union(7,6) + union(3,6) ===\n"); setUnion(unionSet, 9, 8); setUnion(unionSet, 7, 6); setUnion(unionSet, 3, 6); printSet(unionSet, size); return 0;}void printArray(ElementType data[], int size){ int i; for(i = 0; i < size; i++) printf("\n\t data[%d] = %d", i, data); printf("\n\n");} void printSet(UnionSet* set, int size){ int i; UnionSet temp; for(i = 0; i < size; i++) { temp = set; printf("\n\t parent[%d] = %d", i, temp->parent); } printf("\n");}
|
