霍夫曼树

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。构造霍夫曼树主要运用于编码,称为霍夫曼编码。
举个例子:
用0和1编码表示AAAABBBCCD
2位编码的方案:

1
2
3
4
A:00
B:01
C:10
D:11

编码为:00 00 00 00 01 01 01 10 10 11
以上是定长的编码方式,用霍夫曼编码可以对编码压缩。使用多位编码方案,单个字符的的编码不能是其他编码的前缀,并且要使得编码总长度约越短,位数越少的编码出现的频次应越高。
在AAAAABBBCC中,A的频次为4,B的频次为3,C的频次为2,D的频次为1,构造霍夫曼树,频次越高的节点越靠近根节点。

1
2
3
4
5
6
7

0/ \1
A ❤
0/ \1
B ❤
0/ \1
C D

根据霍夫曼树,确定多位编码方案:

1
2
3
4
A:0
B:10
C:110
D:111

AAAABBBCCD可以表示为:0 0 0 0 10 10 10 110 110 111

霍夫曼树