树系列第 20 篇：哈夫曼树、选型指南与系列总结

这是“树系列”的最后一篇，也是收束全系列的一篇。我们先用贪心造出一棵“最优编码树”——哈夫曼树，把它当作本系列的最后一个新主角；随后拿出整篇的篇幅，做一张覆盖全系列 19 种树形结构的选型指南；最后回顾 20 篇文章的路线图，聊聊“树”这个主题教给我们的思维方式。如果你从第 1 篇一路读到今天，这篇是给你的毕业礼；如果你只读过其中几篇，也没有关系，第六节那张总表可以作为你随时回来查阅的“树形结构军火库”。

在正式开场之前，先用一段话把整个系列串起来。树系列的第一站是“为什么要学树”：现实世界里的目录、组织架构、基因谱系、编译器语法，全都天然带着层级；第二站我们学树的基本术语——根、叶子、高度、深度、祖先、后代；第三、四站把二叉树讲透，并回答了“树在内存里怎么放”的问题——链式存储直观，数组存储紧凑；第五、六站是深度优先遍历与广度优先遍历，前者天然贴合递归，后者天然贴合队列；第七、八站迎来第一个“平衡问题”，二叉搜索树在退化时会变成链表，于是有了 AVL 树与红黑树；第十三、十四站跳出内存，讲数据库磁盘上的 B 树与 B+ 树；第十五站用概率让链表拥有 log 的跳表；第十六站是取极值之王——堆；第十七站是字符串前缀的 Trie；第十八站是动态连通的并查集；第十九站是区间问题的线段树与树状数组；今天，第二十站，我们用贪心与二叉树完成一次漂亮的“压缩”，再为全系列画上句号。

这张图是我们这一路走来的地图。你会发现，前面的十九站几乎每一站都在回答同一类问题：把什么信息放进树的节点，树就能帮我们更快地完成什么操作。 今天也不例外——只不过这次放进节点的是“字符出现的频率”，而树要帮我们完成的任务是“用最短的总长度给每个字符编码”。

本篇的阅读路线建议如下：如果你对压缩和编码完全没有概念，请从第 1 节慢慢读，它会把“定长、变长、前缀码”三个词彻底讲透；如果你已经知道哈夫曼算法“每次合并最小两棵”，可以直接跳到第 2.3 节的完整走查和第 4 节的代码，看看实现细节；如果你其实更关心“学完 20 篇到底有什么用”，第 6 节的选型指南和第 7 节的系列回顾是为你准备的，它们不依赖前文的数学推导。当然，最推荐的读法还是从头到尾：哈夫曼树是系列收官的完美主角——它既有树的结构，又有贪心的灵魂，还有信息论的远方。

1 编码问题：定长编码与变长编码

1.1 一个具体的存储场景

假设你有一份文本，里面只有六个字符：A、B、C、D、E、F。它们出现的次数分别是 45 次、13 次、12 次、16 次、9 次、5 次，总共 100 个字符。现在要把这份文本存进文件或者通过网络发出去，希望占用的比特总数最少。

这是压缩最原始的形态：文本的内容一个字都不能变，但我们可以决定用什么样的“记号”去表示它。计算机世界里，一切文本最终都要变成二进制；问题只在于“哪个字符对应哪一串 0/1”。

最朴素的想法是定长编码：因为只有 6 种字符，2 位可以表示 4 种，不够；3 位可以表示 8 种，够用。于是可以给每个字符分配一个固定的 3 位码：

A = 000   B = 001   C = 010
D = 011   E = 100   F = 101

这样每个字符都是 3 比特，100 个字符总共 300 比特。解码的时候非常省心：每读 3 位，查一次表，就还原出一个字符。定长编码的优点是无歧义、可随机定位——因为码长固定，即使不从文本开头读，只要知道位置，也能立刻取出第 k 个字符的编码。它的缺点是完全无视频率：出现 45 次的 A 和只出现 5 次的 F 占用一样多的比特，这显然不公平。

1.2 变长编码的诱惑

直觉告诉我们：出现次数越多的字符，应该给它越短的编码；出现次数越少的字符，可以容忍较长的编码。 这就是变长编码的基本思想。比如可以给 A 一个最短的编码“0”，给 E、F 这样的小角色分配长一点的编码。100 个字符，如果高频字符平均只花 1 到 2 比特，总长度会显著低于 300。

但变长编码立刻带来一个新问题：解码时怎么知道每一位属于哪个字符？ 定长编码下不存在这个问题，因为码长固定；变长编码下，如果两个字符的编码一个是另一个的前缀，解码就会产生歧义。比如 A = 0、B = 01，收到“01”时，到底应该解成“A 后面跟一个 1 开头的字符”，还是直接解成 B？

试一个具体的歧义例子。假设：

A = 0   B = 1   C = 01

二进制串“01”既可以解释为 A、B 两个字符，也可以解释为 C 一个字符。接收方没有任何信息能判断发送方原本想表达什么——这是灾难性的，因为压缩的前提是无损，解码必须唯一。为了防止这种歧义，我们必须要求：任何字符的编码都不能是另一个字符编码的前缀。 满足这个性质的编码叫前缀码（prefix code），也叫无前缀码（prefix-free code）。

为什么“无前缀”就能保证唯一解码？因为解码器每次从二进制串的开头，从最短的候选编码开始尝试，一旦发现某个字符的编码与当前前缀完全匹配，就立刻确认这个字符，然后从下一个比特继续。如果没有前缀冲突，这个过程在任何位置都只会匹配到一个字符——不可能出现“再读一位又匹配到别的字符”的情况。这正是哈夫曼树将要为我们解决的核心约束。

1.3 频率与总编码长度

给定每个字符的频率和编码长度，总编码长度的计算公式非常简单：

总长度 = 字符A频率 × 码长A + 字符B频率 × 码长B + …… + 字符F频率 × 码长F

用符号写就是：设字符 c 的出现次数为 f(c)，编码长度为 l(c)，则总长度为 Σ f(c)·l(c)。我们的目标，是在“编码是无前缀码”的约束下，找到一组码长分配，使这个总和最小。

如果只看这个公式，最优策略似乎一目了然：频率最高的字符码长最短，频率次高的码长次短……但码长不是随意指定的整数，它们必须来自一棵合法的前缀码树。比如我们不能给六个字符分配 1、2、2、3、3、3 的码长吗？可以，但码长集合要满足特定的组合约束（对应到一棵二叉树的叶节点深度）。与其在“码长组合”的空间里瞎猜，不如换个思路：把前缀码直接看成树。

1.4 码长的约束：克拉夫特不等式

这里值得停下来认识一条美丽的数学结论：克拉夫特不等式（Kraft inequality）。它说，对任意一组互不为前缀的二进制编码，若码长分别为 l₁、l₂、……、lₙ，则必然满足：

2^(-l₁) + 2^(-l₂) + …… + 2^(-lₙ) ≤ 1

反过来，只要码长满足这个不等式，就存在一棵二叉树能把这些码长全部实现为叶子的深度。为什么会这样？想象一棵“理想二叉树”：深度 d 处有 2^d 个位置，每个位置容纳一个长度为 d 的编码；占用一个位置，等于占据了一棵子树，而子树会挤掉它下面 2^(k-d) 个更深的位置。把每个编码“占用的位置份额”加起来，正好是 2^(-l)，所有份额总和不能超过根节点的全部份额 1。

克拉夫特不等式给了我们一个非常实用的直觉：码长集合是有预算的。给某个字符分配 1 比特，要花掉一半的“预算”；再分配另一个 1 比特，预算就只剩零——所以两个 1 比特码加两个 2 比特码（份额 1/2 + 1/2 + 1/4 + 1/4 = 1.5）根本无法同时存在。哈夫曼算法做的事，可以重新表述为：在“预算不超过 1”的约束下，把码长按频率加权求最小。因为哈夫曼树是满二叉树，它的份额和恰好等于 1，说明它把预算用到了极致，没有浪费。

这条不等式还解释了为什么“先给最高频字符最短码”不能贪过头：如果两个字符都想要 1 比特，预算立刻爆表，其中一个必须让位到 2 比特甚至更长。树的结构（也就是“编码必须来自二叉树叶子”这个约束），正是预算的物理化身。理解这一点后，再看哈夫曼的合并过程，你会更清楚它到底在“节省”什么：它不是在节省比特本身，而是在节省前缀树上的位置预算。

2 哈夫曼树构建：每次合并最小的两棵

2.1 编码问题如何变成树问题

前缀码和二叉树之间有一个绝妙的对应：把编码过程想象成从根出发走一棵二叉树，向左走记 0，向右走记 1；每个字符放在某个叶子节点上；从根到该叶子的路径上的 0/1 序列，就是它的编码。因为字符都在叶子上，任何字符的编码路径都不会是另一个字符编码路径的前缀——路径在叶子上就结束了，不会继续延伸。反过来，任意一棵“叶子都挂着字符”的二叉树，都自然定义了一个前缀码。

在这个对应关系下，字符的码长就等于它所在叶子的深度（根深度为 0）。总编码长度就变成：

总长度 = Σ（字符频率 × 叶子深度）

这个量有一个形象的名字：树的带权路径长度（Weighted Path Length, WPL）。于是，压缩问题被转化成一个纯粹的树问题：

给定 n 个带权叶子，构造一棵二叉树，使得所有叶子“权 × 深度”之和最小。

这样的树就是哈夫曼树，也叫最优二叉树。它的发明者戴维·哈夫曼（David Huffman）在 1952 年给出了一个极简的贪心算法，据说那是他在麻省理工学院的一门课程作业中想出来的。六十年后，这个算法依然活在 ZIP、GZIP、PNG、JPEG 里。

2.2 贪心策略：每次合并最小的两棵

哈夫曼算法的表述短到可以印在 T 恤上：

1. 把每个字符看作一棵只有一个节点的树，节点权值等于字符频率，所有树组成一个森林；
2. 从森林中取出权值最小的两棵树，合并成一棵新树：新树的根权值等于两棵子树权值之和，原来的两棵树分别作为新根的左孩子和右孩子；
3. 把新树放回森林；
4. 重复步骤 2 和 3，直到森林里只剩一棵树。

这棵树就是哈夫曼树。注意两个细节：第一，合并时谁当左孩子、谁当右孩子并不影响总长度，只影响 0/1 的具体分配（左 0 右 1 的约定下，左右互换等于交换两个字符的编码，总长度不变）；第二，“每次取最小的两棵”是局部最优的贪心选择，而哈夫曼证明了它同时是全局最优——这一点我们稍后专门讨论。

每合并一次，森林里的树就减少一棵，所以循环必然在 n−1 轮后终止，不会出现“永远合并不完”的情况。

2.3 完整走查：A–F 带权合并

用前面那组频率来做完整走查。六个字符及其权值：

A:45   B:13   C:12   D:16   E:9   F:5

第一轮：森林里有六棵树，权值分别为 45、13、12、16、9、5。最小的两棵是 E(9) 和 F(5)，合并出新节点 X，权值 14。合并后森林为：A(45)、B(13)、C(12)、D(16)、X(14)。

第二轮：现在最小的是 C(12) 和 B(13)，合并出 Y，权值 25。森林变为：A(45)、D(16)、X(14)、Y(25)。

第三轮：最小的是 X(14) 和 D(16)，合并出 Z，权值 30。森林变为：A(45)、Y(25)、Z(30)。

第四轮：最小的是 Y(25) 和 Z(30)，合并出 W，权值 55。森林变为：A(45)、W(55)。

第五轮：只剩 A(45) 和 W(55)，合并成根 R，权值 100。森林里只剩这一棵树，算法结束。

把合并过程画成流程图，每一步的“最小两棵”都标出来：

对应的哈夫曼树结构如下（X、Y、Z、W 是内部节点，不是字符）：

现在算一下这棵树的带权路径长度：

A 深度 1：45 × 1 = 45
B 深度 3：13 × 3 = 39
C 深度 3：12 × 3 = 36
D 深度 3：16 × 3 = 48
E 深度 4：9 × 4 = 36
F 深度 4：5 × 4 = 20
WPL = 45 + 39 + 36 + 48 + 36 + 20 = 224

而等长 3 位编码的总长度是 300，哈夫曼编码把存储省掉了 76 比特，压缩率约为 224/300 ≈ 74.7%。请注意，这里省下来的每一比特都来自“让 A 浅一点、让 E 和 F 深一点”，这正是频率信息换来的收益。

2.4 为什么贪心是对的：交换论证与“大权近根”直觉

贪心算法经常让人不放心：“每次只做局部最优，凭什么最后全局最优？”哈夫曼树的正确性可以用标准的交换论证证明，这里先用直觉，再给出论证骨架。

直觉非常朴素：总长度等于 Σ（频率 × 深度）。频率大的字符如果被放在深处，乘积就大；频率小的字符如果被放在浅处，就浪费了“浅位置”的稀缺资源。树越深的位置越“贵”，所以越重的权越应该靠近根。哈夫曼算法把最小两个权不断合并，相当于自底向上建树：最先合并的两个叶子（当前最小权）被放在最深处，而最大权（如 A=45）总会在最后一轮才被合并，于是它被放在最浅处。整个过程与“重者近根”完全吻合。

论证骨架分三步：

第一步，最优树里，深度最大的两个叶子一定对应权值最小的两个字符。 反证：如果有一个更重的字符在更深的位置、而一个更轻的字符在较浅的位置，把两者互换，总长度会减少（因为“权 × 深度”的配对被优化了）。反复交换后，最重的字符一定占据最浅的可用深度。所以，把最小两个权作为最深的两个兄弟，没有违背最优性。

第二步，最小两个权可以是兄弟。 在最优树中，深度最大的一层至少有两个叶子；如果权值最小的两个叶子不是兄弟，可以调整树的结构让它们成为兄弟而不增加总长度（具体调整是把它们各自与最深层的一对叶子互换）。因此，我们总可以假设存在一棵最优树，其中最小两个权是兄弟。

第三步，合并最小两个权不改变问题的本质。 把这两个兄弟合并成一个权值为两者之和的新节点后，总长度公式里“这两个叶子的贡献之和”恰好等价于“新节点的贡献 + 一次合并常数”。具体来说，设两个最小权为 x、y，它们在最优树中的深度为 d（最深一层），贡献是 (x+y)·d；合并成权值 x+y 的内部节点后，这个节点如果位于深度 d-1，它的贡献是 (x+y)·(d-1)，两者相差 (x+y)，与合并顺序无关。于是，原问题的最优解和“先合并 x、y 再求新问题最优解”之间只差一个常数，贪心合并不会丢掉全局最优。对合并后的新问题重复同样论证，直到只剩一棵树。归纳完成。

这三步合起来，就证明了哈夫曼算法的正确性：每一步的“最小两棵”都保证存在一个包含这次合并的全局最优解，所以沿着贪心路径走到底，得到的树一定是最优的。

顺带一提，哈夫曼树并不唯一：两个权值相等的字符先合并谁、左右孩子怎么摆，都会产生不同形状的树，但它们的带权路径长度相同。在编码场景里，不同形状只意味着不同的编码表，压缩率一样，解码同样唯一。

2.5 哈夫曼树的结构性质

趁热打铁，把哈夫曼树的结构性质总结一遍，这些性质在做题和证明时都会用到。

第一，哈夫曼树是满二叉树（正则二叉树）：每个内部节点恰好有两个孩子。这是算法本身保证的——每次合并都拿两棵树拼成一棵，新节点永远带着两个孩子，所以不存在“只有一个孩子”的节点。满二叉树带来一个漂亮的计数关系：n 个叶子对应 n-1 个内部节点，整棵树一共有 2n-1 个节点。你可以用归纳法验证：初始森林有 n 棵树，每合并一次，树的数目减一、节点总数加一；合并 n-1 次后只剩一棵树，节点总数从 n 变成 n + (n-1) = 2n-1。

第二，哈夫曼树不一定平衡。这里的“平衡”指 AVL 那种高度差约束。看我们的例子，A 的深度只有 1，E、F 的深度达到 4，左右子树高度差很大，却依然是“最优”的。原因在于哈夫曼树优化的目标是带权路径长度，不是高度；为了把 45 的大权放在浅处，牺牲一点平衡完全值得。这一点常被初学者误解，值得单独强调：最优二叉树不是高度最小的二叉树。

第三，深度与权值负相关。权值最大的叶子深度最小，权值最小的叶子深度最大；更精确地说，如果把所有叶子按权值升序排列，它们在树中的深度按非增顺序排列（允许并列）。这不是巧合，而是 2.4 节交换论证的直接推论。

第四，相同频率产生多棵最优树。例如两个字符频率都是 5，合并时谁先谁后、谁在左边，都会生成不同的树，但 WPL 相同。写代码时不必纠结确定性：只要“取最小两棵”这一步没有选错对象，最终一定最优。

第五，哈夫曼树与哈夫曼编码是同一棵树的两种说法。树论视角关心“带权路径长度最小”，编码视角关心“前缀码总长最小”，两者通过“码长 = 叶子深度”一一对应。你既可以把哈夫曼算法归入贪心算法，也可以把它归入数据结构里的“树”家族——本篇选择后者，因为系列的主角始终是树。

2.6 常见误区与边界情况

把最常见的四个误区一次说清，避免以后踩坑。

误区一：“频率最高的字符一定要编码为 0。”不一定。0 只是一个符号，只有当根的一侧恰好只有这个叶子时，它才能独享单比特编码。如果最高频率字符与另一个字符在最后一轮合并时被分到根的两侧，它可能得到“10”或“11”这样的两比特编码。关键是它拥有最短的码长，而不是某个具体的比特串。

误区二：“哈夫曼树越平衡压缩率越高。”恰恰相反，强行平衡会破坏“重者近根”的原则。比如 A 的频率占 90%，理想编码是 A=0、其余字符共享 1 开头的子树；一棵 AVL 式的平衡树会让 A 也站在第二层，总长度反而变长。所以千万不要把“平衡”当作所有树的万能药——AVL 优化的是查找高度，哈夫曼优化的是带权深度。

误区三：“哈夫曼编码一定达到信息论下界。”达不到。码长必须是整数比特，而熵允许小数比特。只有当所有频率都恰好是 2 的负整数次幂时，哈夫曼码才与熵界重合；一般情况会差一点（但不会超过 1 比特/符号）。想要逼近熵界，需要算术编码、范围编码或 ANS。

误区四：“只有一种字符的文本没法编码。”可以编码，但不需要任何比特：n=1 时建树函数直接返回唯一的叶子，编码表里该字符对应空串，编码结果也是空串，解码函数返回这个字符本身。这个边界在真实压缩器里通常单独处理（比如记录“单符号块”标志），但理解算法时要知道它并不崩溃。

另外还有一个工程上的边界：字符种类很多时，低频字符的编码会很长。如果 100 万个不同字符各出现一次，某些编码会长达近 20 比特，编码表本身可能比正文还大。此时哈夫曼编码并不划算，需要先做字典合并（比如把字符按高字节分组）或者改用其他方案。这个观察也解释了为什么 DEFLATE 只对“符号流”而不是任意字节流直接建树——符号集太大时，先通过 LZ77 把符号集压缩下来。

3 编码与解码：左 0 右 1，沿着树走

3 编码与解码：左 0 右 1，沿着树走

3.1 从树到编码表

树已经建好了，编码规则只有一个：从根出发，向左走记 0，向右走记 1，走到字符所在的叶子时，沿途记下的 0/1 串就是它的编码。

以上一节的哈夫曼树为例，把每条边标上方向：

按图中的路径数一遍：A 深度 1，C、B、D 深度 3，E、F 深度 4，代入频率加权后正好得到 WPL = 224。

沿着树走，得到编码表：

A = 0
B = 111
C = 110
D = 101
E = 1000
F = 1001

验证一下总长度：45×1 + 13×3 + 12×3 + 16×3 + 9×4 + 5×4 = 45 + 39 + 36 + 48 + 36 + 20 = 224，和上节算的 WPL 一致。注意，没有任何一个编码是另一个编码的前缀：比如 B = 111、C = 110、D = 101 都以 1 开头，但彼此不同且没有一个继续延伸出“更长且同前缀”的兄弟码——这正是“字符都在叶子”带来的保证。

有一个很有意思的观察：在这棵树上，B、C、D 三个字符的深度都是 3，但编码前缀彼此不同；E 和 F 深度都是 4。高频的 A 独享最短码 0。如果某些字符的频率恰好相等，编码表可能长得不一样，但总长度不变。

还有一个值得记住的细节：编码表里没有任何一个码以 0 开头、也没有两个码共享过长前缀的规律——它看起来“杂乱无章”，但这恰恰是最优性的表现。定长编码的表可以按字符顺序排列，哈夫曼表则必须跟着树走；所以在真实压缩文件里，哈夫曼表通常以“字符 + 码长”的形式存储，而不是以“字符 + 完整比特串”的形式存储。这个工程细节在 3.7 节还会展开。

另外，请特别留意“叶子和内部节点数量”的对应：树上有 6 片叶子、5 个内部节点，一共 11 个节点。如果你把内部节点也编上号，会发现它们组成了另一棵“结构骨架”——叶子是字符，内部节点是合并历史的见证。后面第 5.5 节的最优归并问题，会把这份“合并历史”直接翻译成合并代价。

3.2 由树生成编码表：一次深度优先遍历

从树生成编码表的过程，本质上是第 5 篇讲过的深度优先遍历：从根出发，每往左走一步就追加一个 0，每往右走一步就追加一个 1；到达叶子时，把当前累积的 0/1 串登记为该字符的编码；然后回溯，继续走另一条分支。因为树上的每条边都只属于一条根到叶路径，而每片叶子只被访问一次，所以整个遍历是 O(n) 的——n 是字符数。

3.3 解码：沿着树走，遇到叶子输出字符

解码是编码的逆过程，也完全由树完成：

1. 从根开始；
2. 读入一个比特：0 向左走，1 向右走；
3. 每到达一个叶子，输出该叶子对应的字符，然后回到根，继续读下一个比特。

举个例子，解码串 1001110：

第 1 位 1 → 根向右到 W
第 2 位 0 → W 向左到 Y
第 3 位 0 → Y 向左到 C（叶子）→ 输出 C，回到根
第 4 位 1 → 根向右到 W
第 5 位 1 → W 向右到 Z
第 6 位 1 → Z 向右到 D（叶子）→ 输出 D，回到根
第 7 位 0 → 根向右到 A（叶子）→ 输出 A
结果：C D A

解码的时间复杂度是 O(总比特数 × 树高)？不——更准确地说，是 O(总比特数)，因为每一个比特只对应树上的一步移动，整个解码过程走过的边数恰好等于比特数。不过，如果要按“每个字符”来算，每个字符的解码成本是它的码长，也就是它的叶子深度。对于这份频率分布，平均每个字符的解码步数是 224/100 = 2.24 步，远低于定长编码的 3 步。

3.4 与 ASCII、UTF-8 的对比

ASCII 是定长编码的代表：每个字符固定 8 比特（1 字节），一共能表示 128 个字符。它的优点是极其简单、支持随机访问——想读第 k 个字符，直接跳到第 k 个字节；缺点是浪费：一篇英文文章里，e 和 z 占用同样多的比特，而且所有非 ASCII 字符完全无法表示。

UTF-8 是另一种思路：它是变长编码，但不是按“频率”变长，而是按“字符范围”变长——ASCII 字符 1 字节，欧洲语言字符 2 字节，中日韩文字 3 字节，扩展符号 4 字节。UTF-8 能覆盖整个 Unicode 字符集，并且通过首字节的前缀模式（比如 110xxxxx 表示两字节字符）保证解码无歧义。但它同样不关心某个字符在特定文本里的实际频率：在纯中文文档里，每个汉字都要花 3 字节，即使某个汉字出现了十万次。

哈夫曼编码的定位与这两者都不同：它不是一套“固定的字符集编码”，而是针对特定文本的统计编码——编码表由文本自身的频率分布生成，所以同一字符在不同文本里可能有不同编码。它也不追求随机访问，只追求整体长度最小。可以这样理解三者：

3.5 压缩率直觉：熵与冗余

为什么哈夫曼编码能省空间？信息论给出了深刻解释。香农告诉我们，一个概率为 p 的符号，理想情况下应该用大约 log₂(1/p) 比特来表示；所有符号的加权平均理想长度就是信息熵：

H = Σ p(c) · log₂(1 / p(c))

用我们的频率估算概率：p(A) = 0.45、p(B) = 0.13、p(C) = 0.12、p(D) = 0.16、p(E) = 0.09、p(F) = 0.05，可以算出 H ≈ 2.17 比特/字符。哈夫曼编码的平均码长是 2.24 比特，比熵高一点点，这是因为码长必须是整数，而熵允许“小数比特”。定长 3 比特则比熵高出 0.83 比特/字符，这 0.83 就是冗余。

换一个极端例子会更有体感：如果一份文本只有 A 和 B 两个字符，频率各占一半，理想长度是每字符 1 比特，哈夫曼树恰好给出 0 和 1，完美。如果 A 占 99%、B 占 1%，熵大约是 0.08 比特/字符，但哈夫曼编码被迫给 A 用 1 比特、B 用 1 比特，平均 1 比特——压缩率远不如熵界。要逼近熵界，需要算术编码或范围编码这类允许“小数比特”的方案，这也是为什么 DEFLATE 之后的现代压缩器（如 zstd、LZMA）不再只用哈夫曼。但作为数据结构教材里的主角，哈夫曼树依然是把“树”与“信息论”连接起来的最美桥梁。

3.6 完整手算：把一句话压一遍

为了把“建树 → 编码表 → 编码 → 压缩率”这条链完整走一遍，选一句大家都很熟悉的英文：to be or not to be。先统计字符频率（空格也算一个字符）：

空格:5   o:4   t:3   b:2   e:2   r:1   n:1

一共 7 种符号、18 个字符。如果按 ASCII 存储，每个字符 8 比特，总长度 18 × 8 = 144 比特。现在建哈夫曼树：

第一轮，合并 n(1) 与 r(1)，得 X=2； 第二轮，合并 X(2) 与 b(2)，得 Y=4； 第三轮，合并 e(2) 与 t(3)，得 Z=5； 第四轮，合并 Y(4) 与 o(4)，得 W=8； 第五轮，合并 Z(5) 与空格(5)，得 V=10； 第六轮，合并 W(8) 与 V(10)，得根 R=18。

对应深度：空格在 V 的孩子位，深度 2；o 在 W 的孩子位，深度 2；t、e 在 Z 的孩子位，深度 3；b 在 Y 的孩子位，深度 3；n、r 在 X 的孩子位，深度 4。总长度：

5×2 + 4×2 + 3×3 + 2×3 + 2×3 + 1×4 + 1×4
= 10 + 8 + 9 + 6 + 6 + 4 + 4 = 47 比特

47 对比 144，压缩率约 32.6%，省下超过三分之二的比特。这个例子没有动用任何“魔法”，仅仅是把频率信息翻译成了树的形状。你甚至可以把编码表写出来验证前缀性质：比如空格 = 01、o = 00、t = 111、e = 110、b = 101、n = 1000、r = 1001（具体分配取决于左右摆放），任意两个码都不是彼此的前缀。

如果你愿意，再试试把同一句话交给 UTF-8：这些字符全部落在 ASCII 区，UTF-8 编码后仍是 144 比特。对比之下，哈夫曼编码的“统计自适应”优势一目了然：它不关心字符的“官方编号”，只关心这份文本里的真实频率。

3.7 编码表怎么传输：规范哈夫曼编码

前面的讨论默认接收方已经拥有一棵完整的树，但这在真实压缩里不成立——压缩包必须自包含。一个直接的办法是：把整棵树的形状和每个叶子的字符都写进文件头。树有 2n-1 个节点，每个节点要区分“内部/叶子、左/右孩子、字符”，开销不小。DEFLATE 采用了一个更聪明的办法：规范哈夫曼编码。

规范哈夫曼编码的思路是：接收方其实不需要完整编码表，只需要知道每个符号的码长。给定一组码长后，按两条规则重建编码：第一，码长短的符号编码值小；第二，码长相同的符号按符号值（或约定顺序）从小到大排列，编码值依次递增。只要遵守这两条规则，重建出的编码就和发送方一致，而且依然满足前缀性质。

为什么能省？因为码长集合可以用紧凑的游程编码表示——DEFLATE 里，16 比特的码长数组经过“重复长度 + 零游程”编码后往往只有几十比特，比存整棵树小一个数量级。解码端按码长分层重建：先统计每种码长的符号数，再逐层分配编码值，最后生成查找表。这套机制让哈夫曼从“理论最优”变成了“工程可用”。

工程上还有两个常见优化。第一是分块动态建表：DEFLATE 把数据切成块，每块单独统计频率、单独传表，块内用动态哈夫曼，块间可以切换；短块用固定表更省。第二是查找表解码：逐比特沿树走正确但慢，实际解码器会预生成“一次吞 8 比特”的查找表（如 zlib 的 inflate_table），牺牲少量内存换几十倍速度。这些细节说明：数据结构到产品之间，还隔着“编码、分块、表压缩、缓存”四道工程工序。

4 代码实现：用优先队列建树与生成编码表

4.1 为什么用优先队列

哈夫曼算法的每一步都需要“取出当前权值最小的两棵树”。如果每次都在森林里线性扫描找最小，总共要合并 n-1 次，每次扫描 O(n)，总时间 O(n²)。n 是字符种类数，一般只有几十到几百，O(n²) 也能跑，但第 16 篇的堆告诉我们：“反复取最小”正是优先队列的主场。把每棵树按权值放进小顶堆，取最小是 O(1)，删除后重新堆化是 O(log n)，插入新树也是 O(log n)。n 次取最小、n-1 次插入，总时间 O(n log n)。

这可能是全系列最顺理成章的一次“技术呼应”：第 16 篇我们辛苦实现堆，今天直接复用它的抽象——PriorityQueue。堆在哈夫曼树里不是主角，但少了它，主角的登场就少了几分优雅。

4.2 数据结构设计

我们需要两类节点：叶子节点（保存字符和频率）和内部节点（只保存频率，以及左右孩子指针）。在 JavaScript/TypeScript 里，可以定义一个统一的节点类型：

interface HuffmanNode {
  char: string | null;   // 叶子存字符，内部节点为 null
  freq: number;          // 频率（叶子）或子树频率之和（内部节点）
  left: HuffmanNode | null;
  right: HuffmanNode | null;
}

建树用的优先队列需要按 freq 排序，频率相同时随便（为了可复现，可以再按 char 或创建顺序比较）。优先队列可以手写一个基于数组的小顶堆，也可以直接用现成库；为了让代码自洽可跑，这里实现一个极简的小顶堆类。

class MinHeap<T> {
  private items: T[] = [];
  constructor(private compare: (a: T, b: T) => number) {}

  push(item: T): void {
    this.items.push(item);
    this.bubbleUp(this.items.length - 1);
  }

  pop(): T | undefined {
    if (this.items.length === 0) return undefined;
    const top = this.items[0];
    const last = this.items.pop()!;
    if (this.items.length > 0) {
      this.items[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  get size(): number {
    return this.items.length;
  }

  private bubbleUp(index: number): void {
    while (index > 0) {
      const parent = (index - 1) >> 1;
      if (this.compare(this.items[index], this.items[parent]) >= 0) break;
      [this.items[index], this.items[parent]] =
        [this.items[parent], this.items[index]];
      index = parent;
    }
  }

  private bubbleDown(index: number): void {
    while (true) {
      const left = index * 2 + 1;
      const right = left + 1;
      let smallest = index;
      if (left < this.items.length &&
          this.compare(this.items[left], this.items[smallest]) < 0) {
        smallest = left;
      }
      if (right < this.items.length &&
          this.compare(this.items[right], this.items[smallest]) < 0) {
        smallest = right;
      }
      if (smallest === index) break;
      [this.items[index], this.items[smallest]] =
        [this.items[smallest], this.items[index]];
      index = smallest;
    }
  }
}

这段堆代码和“树系列第 16 篇：堆”里的实现几乎一模一样：bubbleUp 是插入后上浮，bubbleDown 是弹出堆顶后下沉；唯一的新东西是传入一个 compare 函数，让同一个类既能当小顶堆又能当大顶堆用。(index - 1) >> 1 求父亲、index * 2 + 1 求左孩子，都是 0 基数组里完全二叉树的编号公式——第 4 篇的“数组存树”在这里第三次出场。

4.3 建树函数逐行解释

function buildHuffmanTree(freqMap: Map<string, number>): HuffmanNode {
  const heap = new MinHeap<HuffmanNode>((a, b) => a.freq - b.freq);

  // 1. 每个字符变成一棵单节点树，全部放入小顶堆
  for (const [char, freq] of freqMap) {
    heap.push({ char, freq, left: null, right: null });
  }

  // 2. 反复合并最小的两棵，直到只剩一棵
  while (heap.size > 1) {
    const left = heap.pop()!;   // 权值最小的树
    const right = heap.pop()!;  // 权值次小的树
    const merged: HuffmanNode = {
      char: null,
      freq: left.freq + right.freq,
      left,
      right,
    };
    heap.push(merged);          // 合并后的新树放回堆
  }

  return heap.pop()!;           // 最后一棵就是哈夫曼树
}

逐行解释：

第一行创建小顶堆，比较函数 a.freq - b.freq 保证权值小的树永远在堆顶。如果两个节点频率相等，比较函数返回 0，谁在堆顶由堆的实现细节决定——不影响结果正确性。

第一个循环把每个字符包成叶子节点：char 记录字符、freq 记录频率、左右孩子置空。注意 freqMap 是 Map<string, number>，遍历得到的是字符与频率的键值对。此时堆里有多少个键，森林里就有多少棵树。

第二个循环是算法的核心，条件是 heap.size > 1——森林里至少有两棵树才需要合并。循环体里先 pop() 两次，第一次拿到最小，第二次拿到次小；然后创建内部节点，权值相加，左右孩子分别指向这两棵树；最后把新节点放回堆。循环结束时堆里只剩一棵树，return heap.pop() 把它取出来。

这里有三个值得注意的细节。第一，pop 两次的先后顺序：第一次 pop 出的作为左孩子，第二次作为右孩子；左右互换只影响 0/1 分配，不影响总长度。第二，内部节点的 char 是 null，这是区分“叶子”和“内部节点”的哨兵，生成编码表时靠它判断是否应该停止递归。第三，如果输入只有一种字符（n = 1），循环一次都不执行，直接返回唯一的叶子；此时编码表里这个字符的编码是空串——严格来说，只含一种字符的文本不需要任何比特来区分字符，这是边界情况的正确处理。

4.4 生成编码表：DFS 逐行解释

function buildCodeTable(root: HuffmanNode): Map<string, string> {
  const table = new Map<string, string>();

  function dfs(node: HuffmanNode, code: string): void {
    // 1. 叶子：登记编码
    if (node.char !== null) {
      table.set(node.char, code);
      return;
    }
    // 2. 内部节点：向左加 0，向右加 1
    if (node.left) dfs(node.left, code + "0");
    if (node.right) dfs(node.right, code + "1");
  }

  dfs(root, "");
  return table;
}

这个函数就是第 5 篇 DFS 的直接应用。dfs 接收当前节点和“从根走到这里积累的编码”。如果 node.char 不是 null，说明当前节点是叶子，把编码写进表里返回；否则递归左子树（编码追加 0）和右子树（编码追加 1）。code + "0" 的写法让每个分支拥有独立的编码副本，回溯时不会互相污染——这是递归函数里“路径参数”的标准用法。

注意 code 是字符串拼接，每层 O(码长)，整体生成编码表的复杂度是 O(总码长) = O(n log n) 量级。如果追求极致性能，可以改用数组记录 0/1 并在回溯时 pop，效果一样；字符串版本胜在清晰。

4.5 编码与解码函数

编码函数极其简单：遍历文本，查表，把每个字符的编码拼接起来。

function encode(text: string, table: Map<string, string>): string {
  let bits = "";
  for (const ch of text) {
    bits += table.get(ch) ?? "";
  }
  return bits;
}

解码函数则需要沿着树走：

function decode(bits: string, root: HuffmanNode): string {
  let result = "";
  let node = root;
  for (const bit of bits) {
    // 1. 按比特移动
    node = bit === "0" ? node.left! : node.right!;
    // 2. 到达叶子就输出并回到根
    if (node.char !== null) {
      result += node.char;
      node = root;
    }
  }
  return result;
}

解码的循环体每次只做两件事：读一个比特，决定往左还是往右；检查当前节点是不是叶子，如果是就输出字符并回到根。因为编码是前缀码，解码过程永远不会遇到“走到 null”的情况——只要输入的比特串来自同一棵树的合法编码。最后的 return result 把拼好的文本还回去。

4.6 串起来跑一遍

const freqMap = new Map<string, number>([
  ["A", 45], ["B", 13], ["C", 12], ["D", 16], ["E", 9], ["F", 5],
]);

const root = buildHuffmanTree(freqMap);
const table = buildCodeTable(root);

const text = "ABCADEF";
const bits = encode(text, table);
console.log(bits);          // 例如 011110010001011
console.log(decode(bits, root) === text);  // true

decode(encode(text)) === text 成立，就说明这套“压缩—解压”闭环是无损的。你可以把这段代码放进任何支持 TypeScript 的环境跑一遍，再把频率改成真实英文文本的字母频率表，看看压缩率。实践是检验树的最快方式。

5 复杂度与应用

5.1 复杂度分析

哈夫曼算法的复杂度可以从三个层面看：

• 建树：n 个字符，堆初始化 O(n)（如果逐个 push 则是 O(n log n)），合并循环执行 n-1 次，每次两次 pop + 一次 push，每次 O(log n)，总计 O(n log n)。
• 生成编码表：深度优先遍历整棵树，每个节点访问一次，总时间 O(n)；加上编码字符串拼接，O(n log n) 量级。
• 编码：每个字符查表 O(1)，总时间 O(文本长度)。
• 解码：每个比特走一步，总时间 O(比特总数)，也等于 O(文本长度 × 平均码长)。
• 空间：树上有 2n-1 个节点（n 个叶子 + n-1 个内部节点），加上编码表，O(n)。

一个常被忽视的细节是：解码需要编码表。压缩后的比特串自己无法还原成文本，必须把“字符 → 编码”的映射一起发送或存储。编码表本身也有体积，字符种类越多、编码越长，表的开销越大。这就是“统计编码”和“固定编码”的本质区别：哈夫曼用“额外携带一张表”换来了更短的正文。在真实压缩格式里，编码表要么随数据一起存储，要么用固定规则重建（DEFLATE 的固定哈夫曼表），要么只存频率再由解码端重建（动态哈夫曼表）。

5.2 ZIP 与 GZIP 中的哈夫曼

ZIP 和 GZIP 的核心压缩算法是 DEFLATE，它由两步组成：第一步是 LZ77 字典压缩，把重复出现的字符串替换成“距离 + 长度”的指针；第二步就是哈夫曼编码，把指针和剩余字符进一步压缩。哈夫曼在这套流水线里扮演“最后一公里”的角色：LZ77 负责消除长程重复，哈夫曼负责把残差符号的频率差异榨干。

DEFLATE 里的哈夫曼编码有两点特别之处。第一，它使用规范哈夫曼编码（canonical Huffman code）：只传输每个符号的码长，不传输整棵树或完整编码表，解码端按“短码在前、同级按符号序排列”的规则重建编码，这样表开销小得多。第二，压缩块可以选择“固定哈夫曼表”或“动态哈夫曼表”：动态表根据当前数据重新统计，压缩率更好，但需要额外存储表信息；块非常小时，固定表反而更划算。这些工程细节让哈夫曼从“课堂算法”变成了“工业算法”。

浏览器里的网页、npm 包的下载、Git 仓库的传输，几乎都经过 gzip 或类似算法。可以说，你在互联网上看到的每一次“小一点”的响应体，背后都有一棵哈夫曼树在工作。

5.3 图像编码中的哈夫曼

图像压缩是哈夫曼的另一大主场。PNG 使用 DEFLATE 压缩像素数据，因此内置了哈夫曼编码；JPEG 在基线模式下，对量化后的 DCT 系数使用哈夫曼编码（可选的算术编码在 JPEG 标准中同样存在，但因专利与复杂度问题使用较少）。JPEG 的哈夫曼表有两个：一个用于 DC 系数，一个用于 AC 系数，而且标准允许编码器根据图像内容自定义表——这正是“频率驱动”思想在图像域的复现。

在 JPEG 里，哈夫曼编码的对象不是原始像素，而是经过变换和量化的系数。高频系数大量变成 0，游程编码（RLE）把它们打包成“连续零的个数 + 非零值”的符号，哈夫曼再对这些符号编码。这个链条展示了压缩的通用哲学：先变换去相关，再量化砍精度，最后统计编码榨冗余。哈夫曼是链条的最后一环，却常常是最被人记住的一环。

5.4 其他应用一览

哈夫曼编码的应用远不止文件和图像：传真机使用修改后的哈夫曼编码（MH 编码，基于游程）压缩黑白文档；HTTP 的 Content-Encoding: gzip、SSH 的压缩、数据库的压缩存储都离不开它；甚至在某些网络协议里，哈夫曼被用来压缩头部字段。它也是许多“熵编码”教材的起点——理解了哈夫曼，再学算术编码、ANS（非对称数字系统）会顺畅很多。

从数据结构的角度看，哈夫曼树还贡献了一个通用技巧：给 n 个带权对象构造最优前缀树。这个技巧不限于字符编码——它可以用于最优归并（合并 n 个有序文件，代价是文件大小之和，哈夫曼合并方案代价最小）、用于决策树优化、用于构造最优二分检索树的近似启发。当然，最优二分检索树（OBST）是另一类更复杂的问题（允许内部节点也存键），它和哈夫曼树常常被混淆，区别在于：哈夫曼树的键全在叶子、权重只属于键；OBST 的键分布在所有节点、还要考虑查询失败的概率。如果以后遇到“带权搜索”问题，记住它们是两回事。

5.5 广义哈夫曼：最优归并问题

把“字符”换成“有序文件”，哈夫曼算法立刻变成另一个经典问题的解法。假设磁盘上有 n 个已经排好序的小文件，大小分别为 5、13、12、16、9、45 MB，想把它们两两合并成一个有序大文件。合并两个大小为 x、y 的文件，代价是 x + y（因为要读 x + y 条记录、写出 x + y 条记录）。问：按什么顺序合并，总代价最小？

这个问题叫最优归并。它的数学结构和哈夫曼树完全同构：每个文件是一片带权叶子，每次合并选择两个，代价等于两个文件大小之和，合并出的新文件成为一棵新树；总代价等于所有“叶子权 × 该叶子被合并的次数”，而“被合并的次数”正好等于叶子在合并树里的深度。于是，总代价就是树的带权路径长度，最优方案就是哈夫曼树。

用我们熟悉的那组数：5、9、12、13、16、45，最优合并顺序与 A–F 的建树过程一模一样，最小总代价也是 224。如果换个顺序——比如先合并 45 和 5——大文件就会被反复搬动，代价显著上升。这个例子的工程含义很直接：大块数据不要参与早期合并，尽量让小块先互相消化，这正是“重者近根”在归并场景里的翻版。

哈夫曼思想还能延伸到 k 叉合并：每次取最小的 k 棵合并，对应 k 叉哈夫曼树。这时需要先补“虚拟零权叶子”，让叶子总数满足 (n-1) mod (k-1) = 0，才能保证每次合并都有 k 棵树可选。细节这里不展开，但你知道了“哈夫曼 = 带权合并树”这个模板，遇到同类问题就能一眼认出来。

5.6 哈夫曼的边界与演化

诚实地说，哈夫曼编码不是压缩的终点，而是一个美丽的起点。它的主要缺点是统计粒度太粗：对每个符号独立编码，看不到符号之间的相关性。英文里“th”出现的频率远超“t”“h”单独出现的乘积，哈夫曼编码完全忽略了这种二阶统计量。要利用相关性，要么把相邻符号打包成超符号再建树（n 的阶乘般扩展），要么改用能建模上下文的算术编码。这也是现代压缩器的主流路线：LZ77 系列处理重复串，熵编码阶段再用更精细的模型。

另一个缺点是需要两趟扫描：第一遍统计频率，第二遍才能编码。流式传输时数据不能缓存到文件结尾，于是有了自适应哈夫曼编码（动态哈夫曼）：边读边更新树，编码端和解码端同步演化，不需要单独传输表。FGK 算法和 Vitter 算法是它的两个经典实现，思路都是“每处理一个字符就调整树，保持最优结构”，代价是常数因子较高。

那么哈夫曼树在今天过时了吗？没有。DEFLATE 至今仍是 gzip、ZIP、PNG 的默认算法，HTTP 压缩和 Git 的传输层都建立在它之上；JPEG 基线模式也以哈夫曼为主。zstd 的 FSE 和 Brotli 的上下文建模虽然更先进，但理解它们之前，哈夫曼树仍然是绕不开的第一课——正如我们学习排序必须先理解插入排序和归并排序，学习熵编码必须先理解哈夫曼。

6 全系列选型指南：19 种树形结构，一张图定乾坤

从第 3 篇的二叉树到今天的哈夫曼树，这个系列一共登场了 19 种树形结构（我把“链式/数组两种存储形态”与“递归树”也各算一张牌，凑成整齐的 19 张；第 1、2 篇是概念地基，不算结构）。学完容易忘，忘完容易混：AVL 和红黑树什么区别？B 树和 B+ 树谁管范围查询？堆能查第 k 小吗？Trie 能查前缀吗？……本节的目标，是给你一张可以贴在显示器旁边的决策图和一张总对比表。以后做设计、刷题、面试，先想清楚五件事，再查表。

6.1 选型前先问五个问题

面对任何“要不要用树、用哪种树”的问题，先按顺序问自己这五个问题：

第一问：数据在内存还是磁盘？ 内存里可以随意用指针、链表、递归，常数大一点也没关系；磁盘上每次随机读都是一次昂贵的 IO，必须让一个节点塞下尽量多的键、把树高压到两层三层，于是 B 树家族出场。这一问直接淘汰掉一大半选手。

第二问：要不要范围查询？ “找 key 等于 42”是单点查询；“列出 key 在 30 到 60 之间的所有记录”是范围查询。二叉搜索树、B 树能支持范围查询但要中序遍历；B+ 树把数据集中在叶子并用链表串起来，范围查询变成一次叶子链表的顺序扫描；跳表也有天然的有序链表。如果只需要单点，BST、AVL、红黑树、哈希表都行。

第三问：要不要前缀匹配？ “查以 abc 开头的所有单词”不是普通范围查询（虽然字典序下它也可以看作一个范围），而是字符串前缀查询。Trie 把公共前缀合并成共享路径，前缀查询的时间只取决于前缀长度，而不是候选词数量；后缀树、压缩 Trie 是它的变体。

第四问：要不要动态有序？ 数据是建好就不变的静态集合，还是边插入边查询的动态集合？静态数据可以用排序数组 + 二分，甚至一次性建好线段树；动态插入删除则要求树能自我调整——AVL、红黑树、跳表、B 树都行。堆比较特殊：它只保证“根是极值”，不保证全局有序。

第五问：要不要区间统计？ “把第 3 个元素加 5，再问第 2 到第 7 个元素的和”这类问题，普通搜索树无能为力，需要把“区间”作为节点的职责——线段树、树状数组是标准答案。如果查询是全体的（问总和、问最大值），堆和维护前缀和的数组就够用了。

每条“是”分支都直接给出答案；只有当七个问题全部答“否”时，才会落到“二叉搜索树 / 排序数组”这类静态有序查找方案。

这张决策图不是绝对的——真实工程里数据库索引可能同时是“磁盘 + 范围查询 + 动态”，答案自然是 B+ 树；搜索引擎的倒排索引里既有哈希又有跳表。但先把五个问题问完，90% 的场景都能锁定候选，剩下的 10% 就是组合拳。

6.2 总对比表：19 张牌一次摊开

下面这张表是本节的核心。每行的“典型操作复杂度”写的是该结构最有代表性的操作；空间列给的是大 O 记号；最后一列“什么时候用它”是整张表的精华，考试和面试都可以只背这一列。

结构	核心思想	典型操作复杂度	空间	什么时候用它
普通二叉树	每个节点最多两个孩子，形状自由	查找 O(h)，h 是树高	O(n)	学习树的概念、表达层级结构、作为其他树的“底座”时
满二叉树	所有非叶节点都有两个孩子	概念性质，无特有操作	O(n)	讨论“每层节点数翻倍”和递归定义时
完全二叉树	除最后一层外全满，最后一层左对齐	父子关系用下标 O(1) 算	O(n)（可数组存储）	堆、线段树的形状基础，适合数组存储
二叉搜索树 BST	左小右大，中序有序	平均 O(log n)，最坏 O(n)	O(n)	有序集合的入门实现；数据恰好有序时会退化，需谨慎
AVL 树	严格平衡：左右子树高度差 ≤ 1	查/插/删 O(log n)	O(n)	查找远多于插入删除、要求最坏情况严格有界时
红黑树	颜色约束保证最长路径不超过最短路径 2 倍	查/插/删 O(log n)	O(n)	插入删除频繁、需要稳健 log 上界时；语言标准库的默认选择
2-3 树	节点可含 1-2 个键、2-3 个孩子，完美平衡	查/插/删 O(log n)	O(n)	理解 B 树前身与“多路平衡”思想时
B 树	多路平衡搜索树，节点存多个键	查/插/删 O(log_m n)，m 为阶	O(n)	磁盘/数据库索引，单点查找为主的存储引擎
B+ 树	键只在叶子，叶子链表串联	单点 O(log n)，范围 O(log n + k)	O(n)	数据库与文件系统索引，范围查询、全表扫描友好
跳表	多层链表 + 随机提升，概率平衡	查/插/删 O(log n) 期望	O(n)	并发环境的有序集合、Redis 有序集合、工程实现简单时
大顶堆	父 ≥ 子，根最大	取最大 O(1)，插/删 O(log n)	O(n)	需要反复取最大值的场景：优先队列、Top-K
小顶堆	父 ≤ 子，根最小	取最小 O(1)，插/删 O(log n)	O(n)	求最小、合并有序流、Dijkstra 的候选集
Trie	按字符分层的多叉树，共享前缀	插入/查找 O(字符长度)	O(总字符数)	字典、自动补全、拼写检查、IP 路由前缀匹配
并查集	森林 + 路径压缩 + 按秩合并	合并/查询 O(α(n)) 近似 O(1)	O(n)	动态连通性：朋友圈、网格连通、Kruskal 最小生成树
线段树	区间对半劈，节点存区间汇总	区间查询/单点改 O(log n)	O(4n)	区间最值、区间和、带懒标记的区间修改
树状数组	lowbit 分段，前缀统计	前缀和/单点改 O(log n)	O(n)	逆序对、前缀统计、能差分的区间查询
哈夫曼树	按频率贪心合并，重者近根	建树 O(n log n)，编解码 O(长度)	O(n)	无损压缩、最优前缀码、最优归并
链式存储的树	节点带孩子/兄弟指针	指针操作 O(1)，缓存较差	O(n)	形状动态变化、需要任意插入删除子树的树
数组存储的树（隐式树）	下标公式代替指针	找父/子 O(1)，缓存友好	O(n)	完全二叉树、堆、线段树等形状固定的树

这张表的信息量很大，读的时候不需要一次背完。建议把它当成“查表”：遇到具体需求，先回到 6.1 的决策图缩小范围，再在这一行确认复杂度与场景。下面我把 19 行浓缩成 19 句“什么时候用它”，每一句都能在 5 秒内念完。

读表时还有两个容易忽略的点。第一，“典型操作复杂度”不等于“所有操作复杂度”：比如堆取极值是 O(1)，但查任意元素是 O(n)；Trie 插入是 O(字符长度)，但内存开销可能高达总字符数的数倍。选型前务必把题目要求的每一种操作都列出来，再逐项核对。第二，空间列的单位不同：线段树的 4n 是“为了省时间而多开的常数”，Trie 的“总字符数”则可能比 n 大一个数量级；面试里讨论空间时，要说明是节点数还是字节数。

如果你正在准备面试，这张表还有一个妙用：把它当作“主动回忆卡”。遮住“核心思想”和“什么时候用它”两列，只看结构名，尝试自己说出适用场景；再遮住结构名，只看场景，尝试说出候选结构。反复三轮，19 张牌就会真正属于你。

6.3 每个结构一句话

1. 普通二叉树：只想表达“层级”或初学递归时用它；
2. 满二叉树：讨论每层容量翻倍、证明完全二叉树性质时用它；
3. 完全二叉树：想用数组装下一棵树时用它；
4. 二叉搜索树：数据大致随机、只需一个简单有序集合时用它；
5. AVL 树：查询比更新频繁得多、且不能忍受最坏情况退化时用它；
6. 红黑树：更新和查询都很频繁、需要稳健的 log 上界时用它；
7. 2-3 树：想理解“为什么节点可以装多个键”时用它；
8. B 树：数据在磁盘、以单点查找为主时用它；
9. B+ 树：磁盘数据还要支持范围扫描时，用它（大多数数据库的选择）；
10. 跳表：既要有序又要并发简单、还不想写旋转操作时用它；
11. 大顶堆：反复问“当前最大是谁”时用它；
12. 小顶堆：反复问“当前最小是谁”、或者做 Top-K 时用它；
13. Trie：按前缀批量操作字符串时用它；
14. 并查集：只关心“连不连得通”、不关心怎么连通时用它；
15. 线段树：要任意区间的可合并统计、还要支持修改时用它；
16. 树状数组：只要前缀/差分类统计、想写得最短最快时用它；
17. 哈夫曼树：要给带权符号造最优前缀编码时用它；
18. 链式存储：树的形状会频繁变动、每个节点都可能被移动时用它；
19. 数组存储：树的形状固定、想把缓存命中率拉满时用它。

6.4 三张“实战组合牌”

单张牌背完，再看真实系统是怎么组合出牌的，这样选型才不会纸上谈兵。

组合一：数据库索引 = B+ 树 + 跳表（或哈希）。InnoDB 的聚簇索引是 B+ 树，叶子页存整行数据，主键范围查询直接扫叶子链表；非主键索引是二级 B+ 树，先查到主键再回表。Redis 的有序集合用跳表而不是红黑树，因为跳表的范围查询和并发改造更容易。这一组合教会我们：同一系统里，不同操作可以选不同结构。

组合二：文本搜索引擎 = Trie + 倒排表。输入“树”字，Trie 在毫秒内给出所有以“树”开头的词条；每个词条背后挂一个倒排列表（文档 ID 的有序数组或跳表），多个词条的结果做归并求交。前缀匹配和文档交集由两种不同结构分担。

组合三：压缩流水线 = LZ77 + 哈夫曼。ZIP、GZIP、PNG 共用这条流水线：字典指针消除重复，哈夫曼榨干残差频率。这里没有“最强的树”，只有“配合起来最强的组合”。

6.5 高频面试与工程场景速查

理论落地的最后一步，是把“场景”翻译成“结构”。下面这十条是面试和日常开发里出现频率最高的对应关系，建议当作条件反射来记：

1. 求数组第 K 大元素：维护一个大小为 K 的小顶堆，堆顶就是答案；比“排序后取第 K 个”的 O(n log n) 通常更省内存。
2. 动态中位数：一个大顶堆放较小的一半、一个小顶堆放较大的一半，两个堆的堆顶就是中位数候选；插入后平衡两个堆的大小差不超过 1。
3. 合并 K 个有序链表：把所有链表头放进小顶堆，每次弹出一个节点并推入它的后继；这是“K 路归并”的标准姿势，和第 5.5 节的最优归并相映成趣。
4. 自动补全与拼写检查：Trie 按前缀共享路径，输入前缀后进入对应子树做深度优先遍历即可列出候选词；再加权值就能做热门词排序。
5. 动态连通性：社交网络“两人是否同组”、迷宫“两点是否连通”、Kruskal 算法里“加边会不会成环”，一律并查集，写起来不到二十行。
6. 区间求和 + 单点修改：树状数组五行代码解决；如果还要区间最大值或区间赋值，升级到线段树。
7. 数据库按主键范围扫描：B+ 树，叶子链表让范围查询退化为顺序扫描；InnoDB、SQLite、LevelDB 的索引都能印证这一点。
8. 操作系统定时器：用堆组织“最早到期”的任务，每次取堆顶；这也是 Java DelayQueue、Go timer 一类组件的基本形态。
9. 路由器最长前缀匹配：IP 路由表用 Trie 的变体（基数树/Patricia Trie）组织前缀，匹配长度即深度；这是“前缀码”思想在链路层的回响。
10. 表达式求值与编译器语法树：普通二叉树（表达式树）把运算符放内部节点、操作数放叶子，后序遍历就是后缀表达式的求值顺序；它提醒我们，二叉树不只是“搜索”的专利。

这十条不是要你背答案，而是帮你建立“场景 → 结构”的映射表。遇到没见过的题目，先别急着套模板，而是回到 6.1 的五个问题：数据在哪、要不要范围、要不要前缀、要不要动态、要不要区间统计。五个问题问完，候选往往只剩两三个，再对比复杂度表，答案就出来了。

6.6 复杂度的另一面：常数与工程现实

总对比表里写的都是大 O，但真实世界的选型不能只看大 O。两个同为 O(log n) 的结构，常数可能相差数倍；而大 O 之外，还有缓存局部性、内存分配频率、并发安全三个隐藏维度。

缓存局部性最好的树是“数组存储”的完全二叉树（堆、线段树），因为它们的数据在连续内存里，遍历时预取友好；链式存储的树每次访问都要跟随指针，缓存命中率差，但插入删除不搬动整块内存。跳表虽然每层都是链表，但每一层的节点可以按层分组存储，缓存表现比想象中好；红黑树每个节点带颜色位和三个指针，内存开销和指针追逐都比 AVL 略优。

并发是另一个决定性因素。红黑树的旋转操作需要精细的锁；跳表的“局部更新”天然适合无锁化改造（Redis、LevelDB 都因此偏爱跳表）；并查集在只读场景可以并行查询；线段树的分治结构很适合 GPU 并行归约。选型时如果明确“高并发读写”，大 O 相同的结构里，越容易局部化的越占优。

最后提醒一句：不要为了用树而用树。数据量几百、操作次数几千时，排序数组 + 二分查找往往是最优解；需要极值但从不删除时，一个普通变量就够了；只用单点查询时，哈希表的 O(1) 期望胜过一切平衡树。树的入场券是“有序、动态、范围、统计”这些词——没有它们，树只是增加复杂度。

7 全系列回顾：二十篇，一条主线

7.1 二十篇路线图

把整个系列摊开，会发现它其实沿着三条线索前进：形状 → 平衡 → 应用。

第一条线是形状：第 1 到第 6 篇建立“树是什么、怎么存、怎么走”的基础；第二条线是平衡：第 7 到第 15 篇从 BST 的退化出发，依次给出 AVL、红黑树、B 树、B+ 树、跳表这些“让 log 成立”的方案；第三条线是应用：第 16 到第 20 篇的堆、Trie、并查集、线段树、树状数组、哈夫曼树，每一棵都是为解决一类具体问题而生。

7.2 每篇核心一句话

给每一篇配一句“带走的话”，二十句串起来就是整个系列的压缩包：

1. 为什么学树：层级无处不在，树是表达“一对多关系”的天然结构；
2. 基本术语：根、叶子、深度、高度是描述树的共同语言，先统一词汇再谈算法；
3. 二叉树：每个节点至多两个孩子，是“分治”在结构上的化身；
4. 树的存储：链式存储灵活，数组存储紧凑，完全二叉树能用下标算亲戚；
5. DFS：先根、中根、后根三种顺序，递归天然匹配树的形状；
6. BFS：按层推进，用队列实现，最短路径问题的地基；
7. 二叉搜索树：左小右大，中序有序，查找从此有了 log 的可能；
8. BST 退化：有序插入会让 BST 变链表，平衡是 log 的前提；
9. AVL 插入：四种旋转修复高度差，把树高严格压在 log；
10. AVL 删除：删除比插入更复杂，可能需要一路回溯旋转；
11. 红黑树：用颜色约束代替严格平衡，更新更快、实现更巧；
12. 红黑树操作：变色与旋转的组合拳，让最长路径不超过最短的两倍；
13. 为什么 B 树：磁盘 IO 昂贵，多路节点把树高压到二三层；
14. B 树与 B+ 树：B+ 树数据集中在叶子、叶子串链表，范围查询称王；
15. 跳表：随机掷硬币建立多层链表，概率把 O(n) 变成 O(log n)；
16. 堆：完全二叉树住进数组，取极值 O(1)、插入删除 O(log n)；
17. Trie：字符串按字符分层共享前缀，前缀查询 O(长度)；
18. 并查集：森林 + 路径压缩 + 按秩合并，连通性问题接近 O(1)；
19. 线段树与树状数组：把区间变成节点，改一点、查一段都是 O(log n)；
20. 哈夫曼树与总结：贪心合并出最优前缀码，频率高的离根更近。

7.3 学习路径建议：按需重读

二十篇读完，不代表每篇都该一次吃透。数据结构的学习天然是“螺旋上升”的：第一遍知道“有什么”，第二遍弄清“为什么”，第三遍才能在题目和工程里“用得上”。给出三条按需重读的建议：

• 刷题前必读：第 7、9、11、16、17、18、19 篇。面试题里的二叉树遍历、Top-K、前缀统计、连通性、区间问题，全在这里；
• 做系统设计前必读：第 13、14、15、11 篇。数据库索引、缓存、消息队列的底层选型，都围绕 B+ 树、跳表、红黑树展开；
• 做压缩/信息处理前必读：第 20 篇全文，外加第 16 篇的堆。理解了优先队列和哈夫曼，才能继续读算术编码与 zstd。

重读时不要逐字读，而是先合上书回答三个问题：这棵树解决什么问题？它把什么信息放在节点上？它用哪种方式保证 log？答不上来再翻对应章节。这种“问题驱动的重读”比从头再看一遍有效得多。

7.4 与图系列、排序系列、字符串系列的衔接

树系列收官，不是终点而是枢纽。接下来有三条路，每一条都能接到今天的内容上：

• 图系列（即将开写）：树是“没有环的图”，图的遍历、最短路径、最小生成树，处处能看到树的影子——DFS/BFS 是第 5、6 篇的直接推广，并查集是 Kruskal 算法的核心，Dijkstra 的优先队列就是第 16 篇的堆，哈夫曼的贪心思想也会在 Prim 算法里重逢；
• 排序系列：堆排序依赖第 16 篇的堆；归并排序的递归树、快速排序的划分树，和第 5 篇的分治遍历是同一个灵魂；利用 BST 中序有序，还能做树形排序；
• 字符串系列：Trie 是字符串算法的起点，后缀树、AC 自动机、马拉车都建立在“把字符串结构化成树/图”的思想上。

7.5 树的足迹：在计算机系统里找树

系列快结束的时候，不妨抬起头看看身边：树其实无处不在，只是我们常常忘了它们的存在。

文件系统是树的头号代言人：目录套目录，天然就是一棵多叉树。Linux 的 ext4 用 HTree（哈希树）加速目录查找，Btrfs 用 B 树管理元数据，Windows 的 NTFS 用 B+ 树管理主文件表——你每天都在树里翻文件。浏览器的 DOM 是一棵节点树，CSS 的选择器匹配、React 的虚拟 DOM 协调，都是在这棵树上做遍历和对比。编译器把源代码解析成语法树，再生成中间表示；优化器在控制流图上做分析，最终指令调度还常常涉及树形依赖。网络里，IP 路由表用前缀树匹配最长前缀，DNS 的域名系统按点分层，本质上也是树。数据库的索引、搜索引擎的倒排表与查询计划、操作系统的进程树与定时器堆，全是树的舞台。

这张图想说明的其实是一句话：树的本质是“用层级组织信息”，而层级是人类和机器理解复杂性的共同方式。学数据结构不能只盯着考场，把这些现实对应关系记在心里，你才能在遇到新系统时一眼认出“这里藏着一棵树”。

7.6 学习的三层境界：会背、会证、会选

把二十篇的学法总结成三层，你可以对照一下自己站在哪一层。

第一层是会背：知道 AVL 有四种旋转、红黑树有五条性质、B+ 树叶子串链表、哈夫曼每次合并最小两棵。这是最容易被考试检验的一层，但也是最容易遗忘的一层——背下来的东西不经过思考，一个月后就还给了教材。

第二层是会证：能说清楚 AVL 为什么能保持 log 高度、红黑树为什么最长路径不超过最短的两倍、哈夫曼贪心为什么全局最优、线段树为什么开 4n。证明不是炫技，它逼你理解“约束从哪来”，而理解约束，才能判断结构在什么条件下会失效。

第三层是会选：面对真实问题，能先问“数据在哪、要什么操作、允许什么代价”，再决定用哪种树，甚至决定“这次根本不用树”。这一层无法靠读文章获得，只能在设计和刷题中反复练习。本系列的最后一篇之所以花大篇幅做选型指南，就是希望你离开的时候，至少站在第二层向第三层出发。

一个实用的练习方法是“逆向讲题”：随机抽一个数据结构，30 秒内说出它解决的问题、把什么放进节点、靠什么保证复杂度、一个它不擅长的场景。说不出来就回去重读对应篇章。把二十张牌全部过一遍，你对“树”的理解会真正内化。

8 结语：树的思维方式

8.1 递归：树是最诚实的递归教材

二十篇读下来，你一定反复遇见同一件事：树的定义是递归的——一棵树由根和若干子树组成，子树还是树。于是遍历是递归的，构建是递归的，平衡修复是递归的，编码表生成也是递归的。学会树，等于学会了“把大问题拆成同构的小问题”的本能；这份本能离开树依然有效，归并排序、动态规划、分治算法全是它的亲戚。

递归思维最迷人的地方在于“信任”：写 dfs(left) 时，不需要在脑子里展开整棵子树，只需要相信“如果子问题正确，父问题就正确”。哈夫曼建树的递归版本、线段树的 build、AVL 的插入后回溯，全都是这种信任的产物。很多初学者写递归容易慌，是因为总想“一步看到底”；树的练习恰恰教会我们反过来——先写好递归出口和合并规则，把剩下的交给数学归纳法。这份心态，比任何一棵具体的树都更值钱。

递归也有代价：每一层函数调用都有开销，深度过大可能栈溢出。所以工程实现里，树算法常常有迭代版本——堆的下沉用循环，线段树查询有迭代写法，遍历可以用显式栈。理解递归是为了掌握结构，写出迭代是为了拥抱现实，两者不是对立，而是同一理解的两副面孔。

8.2 分层：树把复杂度藏在高度里

树最迷人的性质是分层：每一层把规模缩小一个常数倍（二叉树是 2 倍，B 树是 m 倍，跳表是概率上的 2 倍），于是从根到叶只有 O(log n) 步。AVL 用旋转维持层数，红黑树用颜色维持层数，B+ 树用多路压缩层数，堆用完全二叉树锁死层数，线段树用对半劈制造层数，哈夫曼树让频率决定层数——二十篇，其实都在和“层数”打交道。以后分析任何数据结构，先问：它靠什么把层数控制在 log？

分层的价值不止在搜索。DFS 的递归深度是树高，BFS 的队列容量与最宽层相关，Trie 的高度是字符串长度，B+ 树的高度决定一次索引查询要读几页磁盘，哈夫曼树的深度决定最长码长——同一个“高度”概念，在遍历、存储、IO、压缩里反复扮演主角。学会从“高度”的角度看问题，等于拿到一把万能尺子。

更重要的是，分层思维能迁移到算法设计之外：模块化系统是分层，网络协议栈是分层，团队协作也讲究分层。树的每一层只和相邻层打交道，这种“局部接口 + 全局性质”的组织方式，是计算机科学送给所有领域的方法论。

8.3 权衡：没有最好的树，只有最合适的树

选型指南那一节已经充分展示：严格平衡换来的是更新代价，多路节点换来的是更复杂的节点结构，区间汇总换来的是 4n 的空间，压缩编码换来的是必须携带编码表。每一棵树都是一次权衡，没有一棵树同时赢下所有指标。真正的工程能力，不是记住“红黑树最好”，而是能说出“在这个场景下，红黑树的哪个优点值钱、哪个缺点可忍”。

这种权衡思维，其实从第 8 篇 BST 退化时就埋下了种子：数组查找 O(log n) 但插入 O(n)，链表插入 O(1) 但查找 O(n)，BST 想两头兼顾，结果被有序输入打回原形。此后每一篇都在“读快一点还是写快一点”“省内存还是省时间”“实现简单还是理论严格”之间选择。哈夫曼树也不例外：它为了总长最短，宁可牺牲平衡和随机访问。数据结构没有银弹，只有“为当前操作分布量身定制”——这可能是全系列最重要的一句话。

选型时还有一个常被忽略的权衡：实现的正确性成本。红黑树旋转容易写错，线段树边界条件容易越界，哈夫曼树如果忘了处理 n=1 会返回空串编码。工程上，“一个容易写错但快 20% 的结构”常常不如“一个慢一点但绝不出错的结构”。所以选型表最后一列“什么时候用它”，永远要结合团队能力和代码可维护性来读。

8.6 留给未来的四个树问题

收官之前，再留四个“以后值得专门写一篇”的树问题，作为你继续探索的锚点。

第一，可持久化线段树：每次修改不覆盖旧版本，而是新建一条路径上的节点，让“查询历史版本”成为可能；主席树（可持久化权值线段树）能回答“区间第 K 小”。它是第 19 篇线段树的自然延伸。

第二，左偏树/斜堆：可合并的堆。普通堆合并两个堆要 O(n)，左偏树通过“右边路径最短”的偏序性质把合并压到 O(log n)，在可并堆问题里是主角。

第三，后缀树与后缀自动机：把字符串的所有后缀组织成一棵树/自动机，单字符串的子串查询、最长重复子串、模式匹配都能在线性时间完成。它是第 17 篇 Trie 在“所有后缀”上的升级。

第四，基数树与 AC 自动机：基数树压缩 Trie 的单一孩子链，AC 自动机在 Trie 上补失配指针，让多模式匹配一次扫描完成。字符串系列会正式迎接它们。

这四个问题都建立在树系列的土壤上：线段树的“版本”、堆的“可合并”、Trie 的“后缀化”、前缀树的“压缩”，每一个都是你已经认识的结构的再生长。树系列今天毕业，但树的旅程没有终点。

8.4 给读者的下一步

如果你已经读到这里，请做三件事收尾：第一，回到第六节的决策图，给 19 种结构各找一个现实中的例子（比如：操作系统的进程调度用堆，浏览器的历史记录用双向链表 + 哈希，数据库主键用 B+ 树）；第二，把第 20 篇的代码跑起来，换一份真实英文文本，算一算哈夫曼编码相对 ASCII 的压缩率；第三，给“树系列”写一份你自己的三句话总结——只有能写出来，才是真的学会。

而系列的下一站已经呼之欲出：图系列第 1 篇《从树到图：当结构不再只有一条路径》。树是每个节点只有一条“来路”的连通结构，图则允许任意节点之间有多条路径；同样的 DFS/BFS 在图上会遇见环、遇见最短路、遇见连通分量。我们会在图系列里重逢：并查集帮 Kruskal 找最小生成树，堆帮 Dijkstra 加速最短路，哈夫曼的贪心精神会在 Prim 与 Dijkstra 中再次闪闪发光。树系列，今天正式收官；图系列，马上见。

8.5 综合自测题（含答案）

做完这五题，树系列的正文就全部结束了。感谢你一路读到第 20 篇；愿你手里的每一棵树，都长在合适的问题上。我们图系列第 1 篇见。