树的带权路径长度和哈夫曼树

发表于 | 更新于 | 分类于 |
热度 ℃   |   字数统计: 2,667(字)   |   阅读时长: 11(分) |

前言

树的所有叶子结点的带权路径长度之和，称为树的带权路径长度，英文缩写为 WPL，从百度百科中得到的信息为 “树的带权路径长度（weighted path length of tree）是2018年公布的计算机科学技术名词”，这就有点奇怪了，这个词印象中在大学课本里学过啊，怎么会是2018年的名词呢？难道我穿越了？

我赶紧找来严蔚敏、吴伟民老师编著的《数据结构》翻开来看，在2009年9月第30次印刷的图书的144页中，明确的用加粗字体描述了这样个概念：

树的带权路径长度为树中所有叶子结点的带权路径之和，通常记作 WPL = …

看来我没记错，不是这个百科弄错了，就是2018年重新公布了一次，并不是新的概念，它确实是一个古老的名词了，接下来可以复习一下了。

树的带权路径长度

前面虽然已经给出了定义，可什么是路径，为什么要带权，还要一步步来解释。

路径是指从树的一个结点到另一个结点所走过的部分，路径长度也可以理解为两个结点之间的距离，可以简单理解为路过的结点数，那为什么要带权呢？这和我们生活中的路径一样，并不是距离短的路所花费的时间就少，还要考虑路况、成本等多种因素，而权值就是在特定场景下我们赋予每条路的选择概率。

解释了这几个概念之后我们就可以理解文章开头的定义了，把树的每个叶子结点到根结点的带权路径长度加在一起，就是树的带权路径长度。

哈夫曼树

当使用已知结点作为叶子结点，用其构成的所有树中，带全路径长度最小的树被称为最优二叉树，也就是哈夫曼树。

我们先来计算一下一颗二叉树的带权路径长度，二叉树形态如下：

1
2
3
4
5
6
7
graph TB
    A((ROOT))-->B((P));
    A((ROOT))-->C[[2]];
    B((P))-->D[[4]];
    B((P))-->F((R));
    F((P))-->G[[7]];
    F((P))-->H[[5]];

计算二叉树的带权路径长度涉及到树的层数和权值，以上面这个图为例，ROOT 结点所在的层数为0层，往下数字2结点为1层，数字4结点为2层，数字7结点和5结点为3层，方块中的数字代表了该叶子结点的权值，那个这颗树的带权路径长度为：

7 3 + 5 3 + 4 2 + 2 1 = 46

那么这是一颗最优树吗？显然不是，因为它的带权路径长度不是最短，其实从计算公式也可以看出一点门道，计算带权路径长度时会用层数乘以权值，因为权值不会变，那么唯一能减小结果的就是调整层数，一个很直观的贪心思路就是把权值大的放在低层，权值小的放在高层，这样就可以减小最后的值，比如调整成这样：

1
2
3
4
5
6
7
graph TB
    A((ROOT))-->B((P));
    A((ROOT))-->C((P));
    B((P))-->D[[4]];
    B((P))-->F[[2]];
    C((P))-->G[[7]];
    C((P))-->H[[5]];

这颗树的带权路径长度计算结果为36，比之前的值小了很多：

4 2 + 2 2 + 7 2 + 5 2 = 36

其实这还不是一颗最优的树，最优的结构应该是这样：

1
2
3
4
5
6
7
graph TB
    A((ROOT))-->B[[7]];
    A((ROOT))-->C((P));
    C((P))-->D[[5]];
    C((P))-->F((P));
    F((P))-->G[[2]];
    F((P))-->H[[4]];

它的带权路径长度计算结果为5，从这可以看出，树的层数高的不一定计算成的带权路径长度就大。

作用

前面说了这么多，那么哈夫曼树有什么作用呢？你应该听说过哈夫曼编码吧，这其实就是哈夫曼树的一个应用，用来找到存放一串字符所需的最少的二进制编码。存放二进制还要单独编码吗？也许你想说什么英文字母不都是编好的吗？

单纯用字母来传递信息有一个问题，那就是会造成浪费，因为每个字母在日常交流中出现的次数并不一样，比如字母 e 是英文中出现频率最高的字母，而字母 z 却出现的很少，所以可以用较短的编码来表示 e 用较长的编码来表示字母 z，这样很直观的就能感觉到同样的信息采取这种方式处理之后会占用更小的空间。

构建哈夫曼树

假设有一段英文文件，我们先统计这个文件中每个字母的出现得到次数，统计如下（别问我这个文件写的什么，我胡诌的(#^.^#)）：

a:19
b:6
c:7
d:3
e:32
f:10
g:21
h:2

因为哈夫曼树使用叶子结点来推导最终的编码，所有我们先用这些数字作为叶子结点：

1
2
3
4
5
6
7
8
9
graph TB
    A[[19]]
    B[[6]]
    C[[7]]
    D[[3]]
    E[[32]]
    F[[10]]
    G[[21]]
    H[[2]]

接下来记住一个原则，那就是找当前树的根结点和剩余叶子结点的最小的两个值，然后组成新的树杈。

首先，从19、6、7、3、32、10、21、2 中选择频数最小的两个叶子结点，分别为2和3，计算两个结点的和5作为根：

1
2
3
4
5
6
7
8
9
10
11
12
graph TB

    A[[19]]
    B[[6]]
    C[[7]]

    R((5))-->D[[3]]
    R((5))-->H[[2]]

    E[[32]]
    F[[10]]
    G[[21]]

接着，从19、6、7、5、32、10、21 中选择两个最小的结点，分别是根结点5和叶子结点6，计算两个结点的和11作为新的树根：

1
2
3
4
5
6
7
8
9
10
11
12
13
graph TB

    A[[19]]
    C[[7]]

    R2((11))-->R((5))
    R2((11))-->B[[6]]
    R((5))-->D[[3]]
    R((5))-->H[[2]]

    E[[32]]
    F[[10]]
    G[[21]]

然后，从19、7、11、32、10、21 中选择两个最小的结点，这次都是叶子结点，分别为7和10，计算两个结点的和17形成一颗新的树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph TB

    A[[19]]

    R2((11))-->R((5))
    R2((11))-->B[[6]]
    R((5))-->D[[3]]
    R((5))-->H[[2]]

    E[[32]]

    R3((17))-->C[[7]]
    R3((17))-->F[[10]]

    G[[21]]

继续，从 19、11、32、17、21 中选择最小的 11 和 17 这两个树的根结点，计算两个结点的和 28 作为组合树的根结点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
graph TB

    A[[19]]

    R2((11))-->R((5))
    R2((11))-->B[[6]]
    R((5))-->D[[3]]
    R((5))-->H[[2]]

    E[[32]]

    R3((17))-->C[[7]]
    R3((17))-->F[[10]]

    R4((28))-->R2((11))
    R4((28))-->R3((17))

    G[[21]]

然后，从 19、32、28、21 中选择最小的 19 和 21 这两个叶子结点，计算两个结点的和 40 形成一棵新的树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
graph TB

    R2((11))-->R((5))
    R2((11))-->B[[6]]
    R((5))-->D[[3]]
    R((5))-->H[[2]]

    E[[32]]

    R3((17))-->C[[7]]
    R3((17))-->F[[10]]

    R4((28))-->R2((11))
    R4((28))-->R3((17))


    R5((40))-->A[[19]]
    R5((40))-->G[[21]]

接下来，从 32、28、 40 中选择最小的 32 和 28 这两个结点，求和 60 构成一棵树，根结点为60：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
graph TB

    R2((11))-->R((5))
    R2((11))-->B[[6]]
    R((5))-->D[[3]]
    R((5))-->H[[2]]

    R3((17))-->C[[7]]
    R3((17))-->F[[10]]

    R4((28))-->R2((11))
    R4((28))-->R3((17))

    R6((60))-->E[[32]]
    R6((60))-->R4((28))


    R5((40))-->A[[19]]
    R5((40))-->G[[21]]

最后把剩下的 40 和 60 两个结点连在一起，和为100就得到了一颗哈夫曼树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
graph TB

    R2((11))-->R((5))
    R2((11))-->B[[6]]
    R((5))-->D[[3]]
    R((5))-->H[[2]]

    R3((17))-->C[[7]]
    R3((17))-->F[[10]]

    R4((28))-->R2((11))
    R4((28))-->R3((17))

    R6((60))-->E[[32]]
    R6((60))-->R4((28))


    R5((40))-->A[[19]]
    R5((40))-->G[[21]]

    R7((100))-->R6((60))
    R7((100))-->R5((40))

按照上面的定义来算，这颗二叉树的带权路径长度为：

WPL = 2 (32 + 19 + 21) + 4 (6 + 7 + 10) + 5 * (3 + 2) = 261

其实还有另一种计算带权路径长度的方法，那就是把除根结点以外的所有数字都加起来：

WPL = 60 + 40 + 28 + 32 + 19 + 21 + 11 + 17 + 5 + 6 + 7 + 10 + 3 + 2 = 261

编码

我们用统计数量的字母来替换频数，然后在树的左右指针上分别标上数字就可以得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
graph TB

    R2((11))--0-->R((5))
    R2((11))--1-->B[[b]]
    R((5))--0-->D[[d]]
    R((5))--1-->H[[h]]

    R3((17))--0-->C[[c]]
    R3((17))--1-->F[[f]]

    R4((28))--0-->R2((11))
    R4((28))--1-->R3((17))

    R6((60))--1-->E[[e]]
    R6((60))--0-->R4((28))

    R5((40))--0-->A[[a]]
    R5((40))--1-->G[[g]]

    R7((100))--0-->R6((60))
    R7((100))--1-->R5((40))

至此我们就可以给出编码了呀，从根结点走到每个叶子结点路径上经过的0和1就是编码内容，编码表如下：

a–>10
b–>0001
c–>0010
d–>00000
e–>01
f–>0011
g–>11
h–>00001

要想等长编码这8个字母最少需要4个bit，采用哈夫曼编码以后最少用2bit，最多用5bit，这是考虑了出现频率以后的结果，在传输大量数据的时候，采用哈夫曼编码会是一个更优的解决方案。

总结

  • 树的带权路径长度是指树的所有叶子结点的带权路径长度之和，简称WPL
  • 当使用已知结点作为叶子结点，用其构造的所有树中，带全路径长度最小的树被称为最优二叉树，也就是哈夫曼树
  • 哈夫曼树可以用来编码，采用哈夫曼编码后的信息可以可以使空间利用更加高效
  • 哈夫曼树的构造并不是唯一的，相同的权值结点完全可以构造出不同形态的哈夫曼树，甚至连高度都不同
  • 哈夫曼编码还保证了长编码不与短编码冲突的的特点，这个后续有时间我们再聊
==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==

埋下高昂的头颅，为一飞冲天的壮举积蓄力量，我就在这静静的等，期待你的绽放~

2021-11-12 00:42:33

Albert Shi wechat
欢迎您扫一扫上面的微信公众号，订阅我的博客