QuickUnion优化及Huffman树

一、QuickUnion的优化

1.使用路径压缩进行优化

由于每次合并、查找都需要得到元素的根节点，而当我们的树路径过长效率不高，因此我们可以将每个元素的父节点都指向根节点

代码逻辑：

当我们进行根节点的查找，可以将每个经过的节点放入一个栈，找到根节点后再把栈的所有节点一一出栈并把这些节点的父节点改为根节点

2.代码实现

typedef struct _node{
	int index;
	struct _node*next;
}setNode_t;

static setNode_t* push(setNode_t*strack,int index) {
	setNode_t*node=malloc(sizeof(setNode_t));
	node->index=index;
	node->next=strack;
	strack=node;
	return strack;
}

static setNode_t* pop(setNode_t*strack,int*index) {
	setNode_t*temp=strack;
	*index=strack->index;
	strack=strack->next;
	free(temp);
	return strack;
}

static int findRootV2(QUSet_t*set,Element_t*e) {
	int i=findIndex(set,*e);
	if (i==-1) {
		return -1;
	}
	setNode_t*strack=NULL;
	while (i!=set->parentID[i]) {
		strack=push(strack,i);
		i=set->parentID[i];
	}
	int pos=0;
	while (strack) {
		strack=pop(strack,&pos);
		set->parentID[pos]=i;
	}
	return i;
}

 二、哈夫曼树(Huffman)

1. 哈夫曼树相关的几个名词

a.路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。 从根结点到结点 a 之间的通路就是一条路径。

b.路径长度：在一条路径中，每经过一个结点，路径长度都要加 1。 例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第i层结点的路径长度为从根结点到结点 c 的路径长度为 3。

c.节点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。 例如，结点al17，结点b 的权为5。

d.节点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。 例如,结点b 的带权路径长度为2*5= 10。 树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作"WPL”。 例如图中所示的这颗树的带权路径长度为： WPL=7*1+5*2+2*3+4*3

2.使用场景及实现逻辑

根据上图实现哈夫曼树后我们发现，元素都在叶子结点，频次都在主干上。

假如左边结点用一个bit位0表示，右边结点用一个bit位1表示，那么这些字符的权值编码如下

A0 C10 E110 B1110 D1111 ，总共1*5+2*3+3*2+4*2+4*1=29bit，也就是等长编码需要39bit，而权值编码需要29bit，省出来10bit

3.前缀码，指的是一个字符的编码可能是其他编码的前缀

比如：A01 B0101 C0 C的编码0是A的前缀，A的编码是B的前缀，这样一串编码在接收端没有分隔符就很难区分是哪个字符，比如0101就无法区分是AA还是B

我们的哈夫曼树采用的是非前缀码，不需要使用分隔符就可以区分字符

比如我们上面提到的A0 C10 E110 B1110 D1111，任意一个字符编码都不是另一个字符编码的前缀