二叉树之赫夫曼树

二叉树之赫夫曼树

赫夫曼树

别名“哈夫曼树”、“最优树”以及“最优二叉树”。

赫夫曼树相关的几个名词

路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。

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

结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。

结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。

构建赫夫曼树的规则

n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;

在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;

重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是赫夫曼树。

undefined

解释

A)给定了四个结点a,b,c,d,权值分别为7,5,2,4;第一步如(B)所示,找出现有权值中最小的两个,2 和 4 ,相应的结点 c 和 d 构建一个新的二叉树,树根的权值为 2 + 4 = 6,同时将原有权值中的 2 和 4 删掉,将新的权值 6 加入;进入(C),重复之前的步骤。直到(D)中,所有的结点构建成了一个全新的二叉树,这就是哈夫曼树。
树的带权路径长度为树中所有叶子结点的带权路径长度之和(用权重*高度)。通常记作 “WPL” 。例如图中所示的这颗树的带权路径长度为:
WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

用途

赫夫曼树是为了解决远距离通信(主要是电报)数据传输的最优问题。

比如,在网络上传输「BADCADEEFD」字符串序列给其他人,每个字符占一个字节,如果要压缩的话可以通过二进制编码的方式进行传输,这个字符串包含了6个字符:ABCDEF,我们可以用对应的二进制表示如下:

字符 A B C D E F
二进制 000 001 010 011 100 101

这样,真正传输的数字编码就是「001000011010000011100100101011」,对方接收时按照3位一分来译码,如果文章很长,这个序列串也会非常长。

上述「BADCADEEFD」中不同字符的出现大致概率是这样的:

字符 A B C D E F
概率 20% 10% 10% 30% 20% 10%

按照赫夫曼树构建规则构建

undefined

然后将权值左分支改为0,右分支改为1,对应的赫夫曼树如下

undefined

按照这六个字母经过路径的权值对字母进行重新编码:

字符 A B C D E F
新编码 11 100 101 01 001 000

这样一来就得到了新的字符编码,这种编码方式就是赫夫曼编码,我们通过赫夫曼编码对字符串「BADCADEEFD」进行重新编码:

原编码二进制串:001000011010000011100100101011(30个字符)
新编码二进制串:1001101101110100100100001(25个字符)

可以看到数据被压缩了,节省了约17%的传输成本,随着字符串长度增加,重复字符增多,效果更明显,并且重复字符越多,压缩效果越好。