第 9 讲 · 搜索树、堆与哈夫曼编码

二叉树本身只规定形态。我在这一讲给树增加不同的不变量，让它分别服务于有序查找、优先级处理、表达式求值和最短前缀编码。

二叉搜索树

二叉搜索树（BST）满足：任一结点左子树所有关键字小于该结点，右子树所有关键字大于该结点，左右子树也分别满足同样性质。

查找时每次比较后只需进入一棵子树，代价为 $O(h)$。树平衡时 $h=O(\log n)$；若按递增顺序逐点插入，树可能退化成链，$h=O(n)$。

插入

沿查找路径走到空位置，把新结点接入。插入后中序遍历仍按关键字有序，这就是需要保持的不变量。重复关键字是计数、忽略还是另放一侧，应在接口中明确。

删除

1. 叶结点：直接断开；
2. 只有一个孩子：让双亲直接接向该孩子；
3. 有两个孩子：用中序前驱或后继替换当前关键字，再删除那个至多只有一个孩子的替代结点。

AVL 树

AVL 树要求每个结点左右子树高度差的绝对值不超过 1。插入或删除破坏平衡后，通过单旋或双旋恢复，同时保持 BST 的中序次序。

课程材料主要用它说明：BST 操作快不快，取决于高度；平衡条件把高度限制在 $O(\log n)$。旋转的核心不是背四张图，而是让失衡处的中间关键字成为新的局部根。

线索二叉树

普通二叉链表有许多空指针。线索二叉树利用这些空域指向某种遍历次序下的前驱或后继，并用标志位区分“孩子链接”和“线索”。

以中序线索树为例，若某结点无左孩子，可让左指针指向中序前驱；无右孩子时让右指针指向中序后继。这样可以不借助递归栈沿中序次序移动。

堆

堆是完全二叉树，并满足堆序：大顶堆任一结点不小于孩子，小顶堆任一结点不大于孩子。它只保证父子关系，不保证整棵树从左到右有序。

完全二叉树让堆可以直接存数组。插入时先放到末尾，再沿父结点向上调整；删除堆顶时用末元素补到根，再向下选择合适孩子调整。两者都是 $O(\log n)$。

自底向上建堆从最后一个分支结点开始逐个下沉，整体为 $O(n)$，不是简单地把每次 $O(\log n)$ 相乘。

表达式树

表达式树让叶结点保存操作数，分支结点保存运算符。前序遍历得到前缀形式，中序加必要括号得到中缀形式，后序得到后缀形式。后序求值会先得到左右子表达式的值，再应用根运算符。

哈夫曼树

给定叶结点权值 $w_i$ 和深度 $l_i$，带权路径长度为

$$WPL=\sum_i w_i l_i.$$

哈夫曼算法每次选择权值最小的两棵树，合成一棵权值为二者之和的新树，再放回候选集合，直到只剩一棵。它得到的树使 $WPL$ 最小。

将左边标 0、右边标 1，从根到叶的路径就是该字符编码。只有叶结点表示字符，因此任何编码都不是另一个编码的前缀，可以连续解码而没有分隔符。

哈夫曼压缩流程

源课件进一步给出文件压缩思路：

1. 统计各字符频率；
2. 以频率为权构造哈夫曼树；
3. 生成字符到比特串的码表；
4. 把原文件按码表编码并按位写入字节；
5. 在压缩文件中保存足够的码表或树信息；
6. 解压时重建树，逐位沿树走到叶结点并输出字符。

最后不足一个字节的比特、相同频率时的确定性规则、空文件和只有一种字符，都是实现时必须明确的边界。

五种树不要混

结构	保持的性质	主要目的
普通二叉树	每结点最多两个孩子	表达层级、递归遍历
BST	左小右大	动态有序查找
AVL	BST + 高度平衡	保证对数级高度
堆	完全二叉树 + 父子堆序	快速取极值
哈夫曼树	按最小权值反复合并	最小带权路径长度

只要先说出不变量，就不会把“堆”和“二叉搜索树”误当成同一种有序树。