应用
左子树 < 根 < 右子树。查找、插入、删除平均 。中序遍历 BST 得到有序序列。
任意结点左右子树高度差(平衡因子)不超过 1。插入、删除后通过旋转(LL、RR、LR、RL)恢复平衡,保证 的查找效率。
- 哈夫曼树(最优二叉树):带权路径长度(WPL)最小的二叉树
- 构造方法:每次选权值最小的两个结点合并,直到只剩一棵树
- 哈夫曼编码:左分支 0、右分支 1,用于数据压缩(前缀编码,无歧义)
习题 1
(2023 年 408 真题) 在由 6 个字符组成的字符集 S 中,各字符出现的频次分别为 3, 4, 5, 6, 8, 10,为 S 构造的哈夫曼编码的加权平均长度为( )。
A. 2.4 B. 2.5 C. 2.67 D. 2.75
解题思路:
本题要求计算哈夫曼编码的加权平均长度。思路是先按哈夫曼算法自底向上构造哈夫曼树,再由树的各字符编码长度算出加权路径长度 WPL,最后除以总频次得到加权平均长度。
详细步骤:
- 将频次从小到大排序:3, 4, 5, 6, 8, 10。
- 选取最小的两个频次 3 和 4,合并成新节点,权值为 7;剩余频次为 5, 6, 7, 8, 10。
- 选取最小的两个 5 和 6,合并成新节点,权值为 11;剩余频次为 7, 8, 10, 11。
- 选取最小的两个 7 和 8,合并成新节点,权值为 15;剩余频次为 10, 11, 15。
- 选取最小的两个 10 和 11,合并成新节点,权值为 21;剩余频次为 15, 21。
- 最后把 15 和 21 合并成根节点,权值为 36。
- 由树形读出各字符的编码长度:频次 10 与 8 的编码长度为 2,频次 6、5、4、3 的编码长度为 3。
- 计算加权路径长度 WPL = (10 × 2) + (8 × 2) + (6 × 3) + (5 × 3) + (4 × 3) + (3 × 3) = 20 + 16 + 18 + 15 + 12 + 9 = 90。
- 加权平均长度 = WPL / 总频次 = 90 / (3+4+5+6+8+10) = 90 / 36 = 2.5。
最终答案:
B(2.5)。
习题 2
哈夫曼树的主要应用是什么?
解题思路:
本题考查哈夫曼树的主要应用。答题时先点出核心应用是哈夫曼编码(最优前缀编码),再说明它为什么能压缩数据、为什么解码无歧义,最后补充它还可用于构造最优判定树。
详细步骤:
- 哈夫曼树的主要应用是哈夫曼编码,也就是最优前缀编码,用于数据压缩。
- 编码策略是让出现频率高的字符用短编码、频率低的用长编码,从而使总编码长度最短。
- 由于任何字符的编码都不是其他字符编码的前缀,解码过程没有歧义,可以唯一还原原文。
- 此外,哈夫曼树还可用于构造最优判定树。
最终答案:
哈夫曼树的主要应用是哈夫曼编码(最优前缀编码),用于数据压缩。出现频率高的字符用短编码,频率低的用长编码,使总编码长度最短。由于任何字符的编码都不是其他字符编码的前缀,解码无歧义。此外还可用于构造最优判定树。
