应用

二叉搜索树(BST)

左子树 < 根 < 右子树。查找、插入、删除平均 O(log⁡n)O(\log n)。中序遍历 BST 得到有序序列。

平衡二叉树(AVL)

任意结点左右子树高度差(平衡因子)不超过 1。插入、删除后通过旋转(LL、RR、LR、RL)恢复平衡,保证 O(log⁡n)O(\log n) 的查找效率。

哈夫曼树与哈夫曼编码

  • 哈夫曼树(最优二叉树):带权路径长度(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,最后除以总频次得到加权平均长度。

详细步骤:

  1. 将频次从小到大排序:3, 4, 5, 6, 8, 10。
  2. 选取最小的两个频次 3 和 4,合并成新节点,权值为 7;剩余频次为 5, 6, 7, 8, 10。
  3. 选取最小的两个 5 和 6,合并成新节点,权值为 11;剩余频次为 7, 8, 10, 11。
  4. 选取最小的两个 7 和 8,合并成新节点,权值为 15;剩余频次为 10, 11, 15。
  5. 选取最小的两个 10 和 11,合并成新节点,权值为 21;剩余频次为 15, 21。
  6. 最后把 15 和 21 合并成根节点,权值为 36。
  7. 由树形读出各字符的编码长度:频次 10 与 8 的编码长度为 2,频次 6、5、4、3 的编码长度为 3。
  8. 计算加权路径长度 WPL = (10 × 2) + (8 × 2) + (6 × 3) + (5 × 3) + (4 × 3) + (3 × 3) = 20 + 16 + 18 + 15 + 12 + 9 = 90。
  9. 加权平均长度 = WPL / 总频次 = 90 / (3+4+5+6+8+10) = 90 / 36 = 2.5。

最终答案:

B(2.5)。

习题 2

哈夫曼树的主要应用是什么?

哈夫曼树哈夫曼编码最优前缀编码数据压缩

解题思路:

本题考查哈夫曼树的主要应用。答题时先点出核心应用是哈夫曼编码(最优前缀编码),再说明它为什么能压缩数据、为什么解码无歧义,最后补充它还可用于构造最优判定树。

详细步骤:

  1. 哈夫曼树的主要应用是哈夫曼编码,也就是最优前缀编码,用于数据压缩。
  2. 编码策略是让出现频率高的字符用短编码、频率低的用长编码,从而使总编码长度最短。
  3. 由于任何字符的编码都不是其他字符编码的前缀,解码过程没有歧义,可以唯一还原原文。
  4. 此外,哈夫曼树还可用于构造最优判定树。

最终答案:

哈夫曼树的主要应用是哈夫曼编码(最优前缀编码),用于数据压缩。出现频率高的字符用短编码,频率低的用长编码,使总编码长度最短。由于任何字符的编码都不是其他字符编码的前缀,解码无歧义。此外还可用于构造最优判定树。

发现内容有问题?

告诉我们哪里需要改进。