树与堆

Illustrated by GAloDos（Pixiv），Source

在线性结构中，除了首尾之外，每个元素都只有一个前驱和一个后继；若要表达文件夹包含子目录、组织机构具有上下级、表达式由若干子表达式构成，这种单一路径便不够用了。树允许一个节点分出多个孩子，从而把整体问题递归地拆成若干子问题。

本章会反复出现“树”，但不同结构维护的不变量并不相同。二叉搜索树（BST）用左右子树维持全局次序；堆只保证父节点与孩子之间的局部优先级；哈夫曼树（Huffman tree）根据权重安排叶子深度，以最小化带权路径长度；AVL 树和红黑树在搜索树上进一步约束高度；B 树与 B+ 树则让一个节点容纳多个键，以适应缓存行、磁盘页和数据库范围扫描。理解每一种不变量解决了什么问题，比背诵树名更重要。

一、树的基础概念

从图论角度看，树是无环连通图。任意两节点之间恰有一条简单路径，含 $𝑛$ 个节点的树恰有 $𝑛 - 1$ 条边。为树选定一个根后，边便获得了方向：每个非根节点有唯一父节点，向下可以有零个或多个孩子；没有孩子的节点称为叶子。

节点的深度是根到该节点经过的边数，根深度为零；节点的高度是它到最深叶子的最长边数，叶子高度为零；整棵树的高度等于根的高度。教材有时把节点数而非边数作为高度单位，因此阅读复杂度公式前应先确认约定。无论采用哪一种，包含 $𝑛$ 个节点的链状树高度为 $Θ (𝑛)$ ，而分支均匀的树高度通常为 $Θ (log 𝑛)$ ，这正是平衡结构能够加速查找的根本原因。

#[derive(Debug)]
struct Tree<T> { value: T, children: Vec<Tree<T>> }

这个递归类型能成立，是因为 Vec 本身大小固定，子树内容在堆上。若字段直接写成 children: [Tree<T>; 2]，类型大小会无限递归；二叉树必须用 Box、索引或其他间接层。

注 1.（树不一定存成指针）

文件系统、DOM 常用对象引用；ECS、图算法和序列化系统常用“节点数组 + 子节点索引”。后一种布局紧凑，但删除时要处理索引失效。

二、二叉树

二叉树的每个节点至多有左、右两个子节点。左右是结构的一部分，不能随意交换；因此“只有左孩子”和“只有右孩子”的两个节点属于不同形态。二叉树并不一定用于搜索，它首先只是一种限制分支数的通用层次结构。

1. 二叉树的相关概念

满二叉树（full binary tree）：每个节点的孩子数为 0 或 2；
完全二叉树（complete binary tree）：除最后一层外都填满，最后一层从左到右连续填充；
完美二叉树（perfect binary tree）：所有内部节点都有两个孩子，且叶子处于同一深度。高度为 $ℎ$ 时节点数为 $2^{ℎ + 1} - 1$ ；
平衡二叉树：通常指各处子树高度差受到常数约束，但具体定义取决于结构。

“满”约束的是每个节点的孩子数，“完全”约束的是逐层填充次序，“完美”则同时要求内部节点都有两个孩子、叶子位于同一层。完美二叉树必然同时是满二叉树和完全二叉树，但反向推论并不成立。堆需要的是完全二叉树，因为只有这种形态才能无空洞地压进数组；AVL 树关心的是高度差，并不要求最后一层从左到右填满。

任意有根树都可用“左孩子—右兄弟”表示法转换为二叉树：节点的左指针指向第一个孩子，右指针指向下一个兄弟。原树中某节点的所有孩子，便成为二叉表示中从第一个孩子开始的一条右链。只要原树的孩子次序有意义，这个转换就是可逆的；它没有丢失节点，只是改变了两种指针的解释。

2. 二叉树的实现

type Link<T> = Option<Box<Node<T>>>;
#[derive(Debug)]
struct Node<T> { value: T, left: Link<T>, right: Link<T> }

impl<T> Node<T> {
    fn leaf(value: T) -> Box<Self> {
        Box::new(Self { value, left: None, right: None })
    }
}

每个父节点独占两个子树，所有权关系与从父到子的边完全一致。借用 &Node<T> 可以只读遍历，可变借用 &mut Node<T> 可以修改某一分支，取得 Box<Node<T>> 的所有权则能移动或删除整棵子树。Option 让空孩子成为显式状态，也使叶节点无需哨兵对象。

若节点还要反向访问父亲，结构就不再是单向所有权树。可以像双链表那样让孩子由 Rc 持有、父指针使用 Weak；也可以把全部节点放进 Vec，父子关系都保存为索引。后者在语法树、场景图和实体系统中很常见，因为它紧凑、便于序列化，也不会因为引用环泄漏。

3. 二叉树的遍历

定义 1.（树的遍历）

树的遍历，是按照某种确定的次序访问树中每个节点恰好一次。这里的“访问”可以是读取、输出、累计、修改或计算；遍历算法只负责决定节点被交给访问操作的先后次序。

面对一棵树，真正需要决定的不是“是否使用某个容器”，而是：已经发现、尚未处理的节点不止一个时，下一个应当选择谁。所有遍历都可以围绕这个“待处理集合”理解。深度优先要求先处理最新发现的分支，广度优先要求先处理最早发现的节点；栈和队列正是从这两个顺序要求推导出来的。

a. 为什么 DFS 自然使用栈

从根进入左孩子后，根的右子树并没有消失，只是要等左子树全部处理完再回来。继续进入左孩子的孩子时，又会产生一个更近的“返回点”。因此，尚未完成的任务按如下方式嵌套：最后进入的子树最先完成，最近记录的返回点最先恢复。这正是后进先出。

例如从根 A 先进入左孩子 B，又从 B 进入 D。此时等待以后处理的至少有 A 的右子树和 B 的右子树。完成 D 后必须先回到较近的 B，而不是直接回到 A；所以返回点要按 A, B 的顺序压入、按 B, A 的顺序取出。保存这种后进先出状态的结构就是栈。

递归 DFS 并没有避开栈。每次递归调用都会把“当前节点、局部执行位置以及返回后还要处理什么”保存在调用栈中；子调用结束时，运行时弹出最近一帧并继续执行。显式栈只是把这些隐藏状态改由程序自己保存，因此能避免过深递归耗尽线程栈。

定义 2.（深度优先遍历）

深度优先遍历（DFS）在存在未访问孩子时优先进入该孩子，直到当前分支不能继续，才回溯到最近仍有未处理分支的祖先。它的待处理顺序是后进先出，因而可由递归调用栈或显式栈实现。

b. 前序、中序和后序是根的三个访问时机

DFS 进入一个节点后，都要面对三件事：处理左子树、访问根、处理右子树。三种名称只是在规定“访问根”插入哪一个位置。

定义 3.（二叉树的三种深度优先次序）

对任意二叉树：前序遍历按“根—左子树—右子树”访问；中序遍历按“左子树—根—右子树”访问；后序遍历按“左子树—右子树—根”访问。对子树仍递归使用同一规则。

前序在深入孩子之前访问根，适合复制树、输出目录层级和序列化结构；中序把根夹在两棵子树之间，在二叉搜索树上得到有序键；后序等两个子问题都完成后才处理根，适合计算子树大小、高度、释放节点或求表达式树的值。

递归代码应当在上述次序明确之后阅读。下面是中序遍历：第一处递归完成左子树，visit 访问根，第二处递归完成右子树。若把 visit 移到第一处递归之前便得到前序，移到第二处递归之后便得到后序。

fn inorder<T>(root: &Link<T>, visit: &mut impl FnMut(&T)) {
    if let Some(node) = root {
        inorder(&node.left, visit);
        visit(&node.value);
        inorder(&node.right, visit);
    }
}

把 visit 写成 FnMut，允许闭包修改外部累加器或把结果压入 Vec；传入 &T 则表示遍历只借用节点值，不转移树的所有权。

c. 显式栈如何复现 DFS

前序的显式栈最直观：弹出一个节点后立即访问，再把右、左孩子依次压栈。由于栈后进先出，后压入的左孩子会先弹出，于是得到“根—左—右”。若把左右孩子按直觉顺序压入，访问次序反而会变成“根—右—左”。

fn preorder_iter<T>(root: &Link<T>, mut visit: impl FnMut(&T)) {
    let mut stack = Vec::new();
    if let Some(root) = root.as_deref() {
        stack.push(root);
    }

    while let Some(node) = stack.pop() {
        visit(&node.value);
        if let Some(right) = node.right.as_deref() {
            stack.push(right);
        }
        if let Some(left) = node.left.as_deref() {
            stack.push(left);
        }
    }
}

中序不能在节点第一次弹出时立即访问，因为左子树还必须排在根之前。实现通常把从当前节点到最左后代的整条路径压栈：栈顶就是左子树已经处理完、现在应访问的最近祖先。访问该祖先后，再把问题转向它的右子树。

fn inorder_iter<T>(root: &Link<T>, mut visit: impl FnMut(&T)) {
    let mut stack = Vec::new();
    let mut current = root.as_deref();

    while current.is_some() || !stack.is_empty() {
        while let Some(node) = current {
            stack.push(node);
            current = node.left.as_deref();
        }

        let node = stack.pop().unwrap();
        visit(&node.value);
        current = node.right.as_deref();
    }
}

中序循环的不变量是：栈中保存一条尚未访问根节点的祖先路径；每个栈中节点的左侧工作已经完成或正在由更靠上的栈元素处理。后序还必须区分“第一次到达节点”和“两个孩子均已完成后返回节点”，因此可在栈元素中额外保存 expanded: bool，或保存上一个访问节点判断右子树是否完成。

d. 为什么 BFS 必须使用队列

广度优先要求先访问深度 0 的根，再访问深度 1 的所有节点，然后才轮到深度 2。处理某个深度为 $𝑑$ 的节点时，新发现的孩子位于第 $𝑑 + 1$ 层；它们必须排在当前队列中所有第 $𝑑$ 层节点之后。与此同时，较早发现的孩子又应当比较晚发现的孩子先处理。这正是先进先出，所以需要队列。

假设先后处理同层节点 B、C。处理 B 时把其孩子 D、E 放到队尾；此时 C 已在队首之前等待，所以仍会先于 D、E 访问。处理 C 后再加入 F、G，队列自然形成 D, E, F, G，恰好是下一层从左到右的顺序。若改用栈，B 的孩子会立即压过尚未处理的 C，算法就会再次沿深度方向深入。

定义 4.（广度优先遍历）

广度优先遍历（BFS）按节点到根的边数从小到大访问，同一层内通常按发现顺序访问。新发现的孩子追加到待处理序列末尾，最早发现的节点从前端取出，因此其待处理结构是先进先出的队列。

fn level_order<T>(root: &Link<T>, mut visit: impl FnMut(&T)) {
    use std::collections::VecDeque;

    let mut queue = VecDeque::new();
    if let Some(root) = root.as_deref() {
        queue.push_back(root);
    }

    while let Some(node) = queue.pop_front() {
        visit(&node.value);
        if let Some(left) = node.left.as_deref() {
            queue.push_back(left);
        }
        if let Some(right) = node.right.as_deref() {
            queue.push_back(right);
        }
    }
}

定理 1.（层序遍历的层次不变量）

每次从队首取出节点前，队列中的深度从前到后单调不减，并且至多同时包含相邻两层。处理深度为

𝑑

的节点时，已有队列元素的深度为

𝑑

或

𝑑 + 1

；新加入的孩子深度恰为

𝑑 + 1

，放到队尾后不变量继续成立。因此任何第

𝑑 + 1

层节点都不会先于第

𝑑

层节点访问。

e. 复杂度与选择

无论前序、中序、后序还是层序，每个节点都只入结构、出结构和访问一次，所以时间均为 $Θ (𝑛)$ 。DFS 的递归栈或显式栈最多保存一条根到叶路径及少量待处理分支，空间为 $𝑂 (ℎ)$ ，其中 $ℎ$ 是树高；极端链状树可达到 $𝑂 (𝑛)$ 。BFS 的队列最多接近树的最大层宽 $𝑤$ ，空间为 $𝑂 (𝑤)$ ；完全二叉树最底层可含约一半节点，因此最坏同样为 $𝑂 (𝑛)$ 。

需要先获得子问题结果时选择后序，需要二叉搜索树有序输出时选择中序，需要尽早处理根或复制结构时选择前序，需要按层统计、寻找最浅满足条件的节点或计算无权层数时选择 BFS。栈与队列不是背诵搭配，而是由“下一步应优先处理最近发现还是最早发现的节点”推导出的实现。

4. 二叉搜索树

a. 性质

对任一节点，左子树所有键小于它，右子树所有键大于它；若允许重复键，必须统一规定放置方向或在节点内计数。中序遍历因而有序。

需要注意，“左孩子小、右孩子大”还不足以描述搜索树：要求针对的是整棵左、右子树。例如，右子树中的任何后代都必须大于当前根，而不只是右孩子大于根。实现递归验证时，可以为每个节点携带允许的上下界，而不能只比较父子两层。

b. 增删查改

fn insert(root: &mut Link<i32>, key: i32) -> bool {
    match root {
        None => { *root = Some(Node::leaf(key)); true }
        Some(n) if key < n.value => insert(&mut n.left, key),
        Some(n) if key > n.value => insert(&mut n.right, key),
        Some(_) => false,
    }
}
fn contains(root: &Link<i32>, key: i32) -> bool {
    match root {
        None => false,
        Some(n) if key < n.value => contains(&n.left, key),
        Some(n) if key > n.value => contains(&n.right, key),
        Some(_) => true,
    }
}

查找从根开始：目标较小就进入左子树，较大就进入右子树，相等则结束。插入重复同一路径，直到遇到空孩子。Rust 版本把 &mut Option<Box<Node<T>>> 作为“当前链接”传入递归；当链接为空时可以直接写入新节点，不需要另外保存父指针。

删除有三种情况。叶子可直接把当前链接设为 None；只有一个孩子时，用这个孩子接替当前位置；有两个孩子时，不能简单删除节点，否则两棵子树失去连接。常见做法是取右子树最小节点，也就是中序后继，用它的键值替换当前节点，再从原位置删除后继。后继不可能有左孩子，所以第二次删除会退化为前两种简单情况。

更新若不改变键，只修改关联值；若键本身改变，必须先删除再重新插入，否则节点可能落在不符合范围的位置。标准库映射通常不允许通过迭代器直接可变借用键，正是为了保护有序或哈希不变量。

c. 复杂度

所有基本操作都只沿一条根到叶路径进行，所以复杂度为 $𝑂 (ℎ)$ ，其中 $ℎ$ 是树高。若形态均匀， $ℎ = 𝑂 (log 𝑛)$ ；若依次插入已经排序的键，所有节点可能都落到同一侧，树退化为链， $ℎ = 𝑛 - 1$ ，查询便退化到 $𝑂 (𝑛)$ 。普通 BST 只维护次序，没有维护高度，这正是接下来各种平衡树要解决的问题。

三、堆

1. 堆的概念性质

二叉堆是一棵完全二叉树。大顶堆要求每个父节点不小于孩子，根即最大值；小顶堆则要求父节点不大于孩子，根为最小值。这个条件只建立父子之间的局部偏序：大顶堆的左孩子和右孩子谁更大并没有规定，更不能通过中序遍历得到排序序列。

完全树最后一层从左到右填充，因此按层序写入数组时不会留下空洞。以下标零为起点，节点 i 的左、右孩子分别是 2*i+1、2*i+2，非根节点的父亲是 (i-1)/2 的整数商。这样既省去每节点两个指针，又让同层节点大体连续，具有良好缓存局部性。

优先队列描述的是接口：插入带优先级元素、查看或移除最高优先级元素。二叉堆只是最常见实现。Rust BinaryHeap 是最大堆；需要最小堆时可存放 Reverse<T>，也可以为自定义任务类型实现与优先级一致的 Ord。若相同优先级还要求先进先出，则应把单调序号纳入比较键。

2. 堆的算法

a. 上浮与下沉

fn sift_up<T: Ord>(a: &mut [T], mut i: usize) {
    while i > 0 {
        let p = (i - 1) / 2;
        if a[p] >= a[i] { break; }
        a.swap(p, i); i = p;
    }
}
fn sift_down<T: Ord>(a: &mut [T], mut i: usize) {
    loop {
        let l = 2 * i + 1;
        if l >= a.len() { break; }
        let r = l + 1;
        let child = if r < a.len() && a[r] > a[l] { r } else { l };
        if a[i] >= a[child] { break; }
        a.swap(i, child); i = child;
    }
}

插入时先把新元素放在数组尾部，这一步保持完全树形状，却可能违反父子顺序；随后不断与父亲比较并交换，这就是上浮。删除堆顶时不能留下数组首部空洞，所以先把尾元素移到根，再反复与更合适的孩子交换，这就是下沉。每次交换至少跨越一层，因此二者为 $𝑂 (log 𝑛)$ ，查看根则是 $𝑂 (1)$ 。

选择下沉孩子时，大顶堆必须选择两个孩子中更大的一个。若只要发现左孩子更大就立即交换，可能让新父节点仍小于右孩子。边界上还要处理“只有左孩子”的最后一个内部节点。若元素入堆后通过 Cell、RefCell 或外部状态改变了比较键，堆无法感知并自动重排，因此标准库把这定义为逻辑错误。

b. 建堆

逐个插入是 $𝑂 (𝑛 log 𝑛)$ ；Floyd 建堆从最后一个非叶节点 n/2-1 倒序下沉：

fn heapify<T: Ord>(a: &mut [T]) {
    for i in (0..a.len() / 2).rev() { sift_down(a, i); }
}

虽然单次下沉的上界是 $𝑂 (log 𝑛)$ ，但建堆时多数节点靠近叶子，只能移动一两层；真正能移动到树底的节点非常少。把每个高度上的节点数与最大移动距离相乘并求和，可得到 $𝑂 (𝑛)$ ，而不是粗略相乘得到的 $𝑂 (𝑛 log 𝑛)$ 。

堆排序先在线性时间内建大顶堆，再反复交换根与当前末尾：最大元素被放到最终位置，堆区长度减一，新的根继续下沉。总时间始终为 $𝑂 (𝑛 log 𝑛)$ 、额外空间 $𝑂 (1)$ ，但相等元素可能跨越很远距离，因此通常不稳定；它的缓存行为也往往不如现代快速排序变体。

四、哈夫曼树

前一节的堆总是快速取出最大或最小元素，哈夫曼树恰好展示了这种能力怎样服务于一个完整的贪心算法。它并不是用于查找键的二叉搜索树，也不要求左右孩子满足大小关系；它关心的是叶子的权重与深度：权重越大的叶子越应该靠近根，权重越小的叶子可以位于更深处。

哈夫曼树也称最优二叉树。这里的“最优”有明确范围：在给定叶子及其非负权重的二叉树中，它使带权路径长度最小；把左右边分别解释为 0 和 1 时，又得到平均码长最短的二进制前缀编码。它并不意味着对任意压缩模型都绝对最优，因为实际效果仍取决于符号概率是否准确、是否独立以及是否只允许整数位长。[1]

1. 带权路径长度

a. 路径长度与权重

根到节点经过的边数称为该节点的路径长度。若第 $𝑖$ 个叶子的权重为 $𝑤_{𝑖}$ 、深度为 $𝑑_{𝑖}$ ，整棵树的带权路径长度记作

WPL = \sum_{𝑖} 𝑤_{𝑖} 𝑑_{𝑖} .

权重可以表示符号出现次数、出现概率或一次决策发生的频率。假设两个叶子的权重分别是 100 与 1：若把权重 100 的叶子向上移动一层，WPL 会减少 100；把权重 1 的叶子向上移动一层却只减少 1。因此，最优树倾向于让大权重叶子接近根、小权重叶子远离根。

WPL 只计算原始叶子，构造过程中产生的内部节点不代表待编码符号。内部节点的权重通常定义为其所有后代叶子权重之和，这样便于合并和证明，但不能再把内部节点作为一项重复计入最终公式。

b. 与前缀编码的对应

给每条左边标记 0、右边标记 1，从根到某个叶子的边标记依次连接，便得到该叶子代表的符号码字。由于符号只放在叶子，一个叶子的路径不可能是另一个叶子路径的前缀，所以这种编码天然满足前缀无歧义：解码时从根开始逐位下降，一旦到达叶子就得到一个完整符号，再回到根继续读取。

最优前缀树中不会出现只有一个孩子的内部节点。若某个内部节点只有一个孩子，删掉这个内部节点并让其孩子直接接到父节点，所有后代码字都会缩短一位，前缀性质却不受破坏，WPL 只会下降。因此，当符号数大于一时，只需考虑每个内部节点恰有两个孩子的满二叉树；这一点也保证最深叶子总能成对地作为兄弟出现。

若权重是出现次数，WPL 就等于把所有符号各编码一次所需的总位数；若权重是概率且总和为 1，WPL 就是每个符号的平均码长。于是“寻找 WPL 最小的树”和“寻找平均码长最短的二进制前缀码”成为同一个问题。

2. 贪心构造

a. 每次合并两个最小权重

构造开始时，每个符号各自形成一棵只有一个叶子的树，并按根权重放入最小堆。每轮从堆中取出权重最小的两棵树 $𝑥$ 与 $𝑦$ ，创建一个权重为 $𝑤 (𝑥) + 𝑤 (𝑦)$ 的新内部节点，把二者作为左右子树，再将新树放回堆中。重复到堆里只剩一棵树，它就是哈夫曼树。

heap ← 所有单叶节点组成的最小堆
while heap.size > 1:
    x ← heap.pop_min()
    y ← heap.pop_min()
    z ← new_node(weight = x.weight + y.weight,
                 left = x, right = y)
    heap.push(z)
return heap.pop_min()

不要把“取出两个最小值”误解成在原数组中把它们删除后就结束。合并节点代表这两个符号此后共同增加一层深度，其权重之和必须重新参与后续比较；若漏掉重新入堆这一步，得到的就不是一棵完整的哈夫曼树。

b. 一个完整的构造例子

设六个符号的权重为 A:5, B:9, C:12, D:13, E:16, F:45。最小堆依次产生以下合并：

轮次	取出的两个权重	新权重	重新入堆后的权重集合
1	`5, 9`	`14`	`12, 13, 14, 16, 45`
2	`12, 13`	`25`	`14, 16, 25, 45`
3	`14, 16`	`30`	`25, 30, 45`
4	`25, 30`	`55`	`45, 55`
5	`45, 55`	`100`	`100`

图中得到 F=0、C=100、D=101、A=1100、B=1101、E=111。这些码字不是唯一答案：权重相同的子树可以交换，任一节点的左右孩子也可以互换，码字的具体 0、1 会随之改变；只要各叶子深度不变，WPL 和平均码长就不变。

本例的 WPL 为

45 \times 1 + 12 \times 3 + 13 \times 3 + 16 \times 3 + 5 \times 4 + 9 \times 4 = 224 .

总权重为 100，因此平均码长为 2.24 位。另一个方便的核对方法是把每次合并产生的新权重相加： $14 + 25 + 30 + 55 + 100 = 224$ 。这是因为每合并一次，该新节点下的所有叶子都会多一层深度，其总增量恰好等于新节点权重。

c. 为什么贪心选择正确

证明分成“最小权重可以放在最深兄弟位置”和“合并后问题规模缩小”两步。首先，在任意满二叉前缀树中，最深层必有一对兄弟叶子。若这两个位置没有放置最小的两个权重，可以把较小权重与较浅位置的较大权重交换；深度差不变或减小，而较大权重不再承担更深路径，因此 WPL 不会增加。于是一定存在一棵最优树，使两个最小权重叶子处于最深层并互为兄弟。

接着把这对兄弟收缩成一个权重为二者之和的伪叶子。原树的 WPL 等于收缩后树的 WPL，再加上两个叶子各自多走一条边造成的固定增量 $𝑤_{𝑥} + 𝑤_{𝑦}$ 。如果收缩后的树不是规模更小问题的最优解，用更优子树替换它就会让原树也变得更优，与原树最优矛盾。因此可以安全地先合并两个最小权重，再对缩小后的问题重复相同选择；这就是哈夫曼贪心算法的最优子结构。

3. 编码、解码与复杂度

a. 生成码表与解码

树构造完成后，以深度优先遍历生成码表：沿左边下降时在当前路径末尾追加 0，沿右边下降时追加 1；到达叶子便把当前路径复制为该符号的码字，回溯时删除最后一位。编码时按符号查表并连接码字；解码时不需要逐个比较全部码字，只需按输入位在树上下降，到叶子输出符号并回到根。

码表必须与压缩数据一起提供，或者由编码端和解码端根据同一组频率确定性地重建。若直接传输整棵树，树的描述也会占用空间；工程格式常只保存每个符号的码长，再按“码长优先、符号次序次之”生成规范哈夫曼码。规范化不会改变码长和压缩率，却能用更紧凑的元数据重建码表，也让解码表更容易生成。

只有一个不同符号时，构造堆中从一开始就只有一个节点。若给它空码字，连续出现多少次便无法从比特流本身判断；实际格式通常约定至少一位码字，例如 0，并另行保存原始符号数。零权重符号是否纳入树也应由格式明确规定，不能在编码端与解码端各自处理。

b. 时间与空间复杂度

设不同符号数为 $𝑘$ 。建立含 $𝑘$ 个叶子的最小堆需要 $𝑂 (𝑘)$ ；算法执行 $𝑘 - 1$ 轮，每轮两次出堆和一次入堆，各需 $𝑂 (log 𝑘)$ ，所以构造总复杂度为 $𝑂 (𝑘 log 𝑘)$ ，树与堆占用 $𝑂 (𝑘)$ 空间。若权重已经按升序排列，可以用两个队列分别维护未合并叶子和已生成内部节点，把构造降到 $𝑂 (𝑘)$ ，但一般输入使用最小堆更直接。

设待编码文本长度为 $𝑛$ ，码表散列查找为均摊 $𝑂 (1)$ 时，编码遍历为 $𝑂 (𝑛)$ ，另加实际输出位数；解码每读取一位只沿树走一条边，时间与压缩位流长度成正比。哈夫曼码要求每个符号码长为整数，因此其平均码长通常接近但不一定等于信息熵；对概率很偏斜或存在上下文相关性的来源，分组编码、算术编码或上下文模型可能得到更高压缩率。

注 2.（语言与实现）

Rust 可用 BinaryHeap<Reverse<_>> 表达最小堆，或为堆元素反转 Ord；内部节点可由索引、Box 或竞技场统一持有。排序规则必须在权重相同时增加稳定的次级键，否则不同运行仍可能得到同样最优却形状不同的树。这些是确定性与所有权层面的实现选择，不改变“反复合并两个最小权重”的算法。

五、AVL 树

从此开始讨论的都是平衡搜索树。它们在普通 BST 的有序不变量之上维护额外信息，并用旋转改变形状而不改变中序序列。

“平衡”并不意味着左右子树节点数完全相等，而是用某种局部规则保证整棵树不会过高。规则越严格，查询路径通常越短，但插入、删除所需的维护越多。AVL 与红黑树恰好代表了两种不同取舍。

1. AVL 树的性质

AVL 节点的平衡因子定义为 $bf = ℎ_{𝐿} - ℎ_{𝑅}$ ，要求每个节点的 $bf \in {- 1, 0, 1}$ 。节点通常缓存高度；插入或删除后沿祖先路径更新，一旦出现 $| bf | = 2$ 就旋转。AVL 约束严格，查询路径短，代价是更新时更频繁地维护平衡。

struct AvlNode<K, V> {
    key: K, value: V, height: i8,
    left: Option<Box<AvlNode<K, V>>>, right: Option<Box<AvlNode<K, V>>>,
}

2. 四种旋转

a. 旋转究竟改变什么

旋转是对失衡节点附近少量指针的一次局部重连。它改变父子关系和子树高度，却不改变键的中序次序，因而不会破坏二叉搜索树的不变量。旋转也不是把整棵树在平面上“转一个角度”：只有失衡节点、它的一个孩子以及夹在二者之间的一棵子树需要改接，其余子树内部完全不动，所以一次旋转的时间复杂度为 $𝑂 (1)$ 。

以右旋为例。设失衡节点为 $𝑦$ ，其左孩子为 $𝑥$ ； $𝑥$ 的左右子树依次为 $𝐴$ 、 $𝐵$ ， $𝑦$ 的右子树为 $𝐶$ 。旋转前的次序关系是

𝐴 < 𝑥 < 𝐵 < 𝑦 < 𝐶 .

右旋时让 $𝑥$ 上升为这棵局部子树的新根，让 $𝑦$ 下降为 $𝑥$ 的右孩子，并把原先的中间子树 $𝐵$ 从 x.right 改接到 y.left。旋转后的中序遍历仍是 $𝐴, 𝑥, 𝐵, 𝑦, 𝐶$ ： $𝐵$ 中的所有键本来就大于 $𝑥$ 而小于 $𝑦$ ，所以改接位置恰好合法。左旋是它的镜像：右孩子上升、原根下降为左孩子，中间子树改接到原根的右侧。

可以把右旋的指针变化概括为：

        y              x
       / \\            / \\
      x   C   -->      A   y
     / \\                / \\
    A   B              B   C

旋转完成后应先重新计算下降节点 $𝑦$ 的高度，再计算新根 $𝑥$ 的高度，因为后者依赖前者的新高度。

b. 怎样判断 LL、RR、LR 与 RL

插入后从新节点向根回溯并更新高度，找到第一个满足 $| bf | = 2$ 的祖先，记为 $𝑧$ 。第一个字母表示从 $𝑧$ 走向较高孩子的方向，第二个字母表示再从该孩子走向增高分支的方向。因此，LL 并不是一种名叫“左旋”的操作，而是“从失衡节点连续向左走两步”的失衡形状。

类型	增高路径	平衡因子特征	修复操作
LL	`z → left → left`	$bf (𝑧) = 2$ 且 $bf (z.left) \geq 0$	对 $𝑧$ 做一次右旋
RR	`z → right → right`	$bf (𝑧) = - 2$ 且 $bf (z.right) \leq 0$	对 $𝑧$ 做一次左旋
LR	`z → left → right`	$bf (𝑧) = 2$ 且 $bf (z.left) < 0$	先左旋 `z.left`，再右旋 $𝑧$
RL	`z → right → left`	$bf (𝑧) = - 2$ 且 $bf (z.right) > 0$	先右旋 `z.right`，再左旋 $𝑧$

LL 与 RR 的增高路径是一条直线。一次旋转让中间节点上升，便能同时缩短过高一侧并加深过低一侧。LR 与 RL 的路径却是折线：若直接旋转 $𝑧$ ，内侧孙节点无法成为合适的新根。因此必须先旋转较高孩子，把折线整理成 LL 或 RR 直线，再旋转 $𝑧$ 。所谓“双旋”并不是第五种基本操作，而是两次方向相反的单旋组合。

c. 用插入序列理解四种情况

连续插入 30, 20, 10 时，首个失衡节点是 30，增高路径为 30 → 20 → 10，即 LL；右旋 30 后，20 成为局部根。连续插入 10, 20, 30 得到 RR，左旋 10 即可。插入 30, 10, 20 时，20 位于左孩子 10 的右侧，属于 LR：先左旋 10，使 20 上升，再右旋 30。插入 10, 30, 20 则是镜像的 RL：先右旋 30，再左旋 10。四种情况的目标完全相同——让三个关键节点中键值居中的那个成为局部根。

插入只会使祖先路径增高一层，修复从下向上遇到的第一个失衡节点后，局部子树通常恢复到插入前的高度，因而无需继续旋转；删除可能让修复后的子树高度继续降低，失衡会向更高祖先传播，所以可能需要沿路径进行多次再平衡。无论是哪一种更新，沿祖先路径查找失衡点为 $𝑂 (log 𝑛)$ ，每次单旋仍为 $𝑂 (1)$ 。

注 3.（语言与实现）

在 Rust 中实现旋转时，通常先用 take() 取出将要上升的孩子与中间子树，再按上述关系重新组装 Box。这是所有权模型下表达指针重连的方式；判断 LL、RR、LR、RL 以及保持中序次序不变，才是 AVL 算法本身。

六、红黑树

红黑树不像 AVL 那样直接限制左右高度差，而是给节点加上红、黑两种颜色，并维护一组约束：根与概念上的空叶为黑；红节点不能有红孩子；从任一节点到其所有后代空叶的路径包含相同数量的黑节点。忽略红节点后，各条路径黑高相同；又因为红节点不能相邻，最长路径至多在每两个黑节点之间插入一个红节点，于是不会超过最短路径的两倍，高度仍为 $𝑂 (log 𝑛)$ 。

相比 AVL，红黑树允许稍松的形态，查询路径可能略长，但更新时通常旋转更少，因此是工程中最常用的内存平衡树之一。新插入节点先染红，是因为红节点不会增加任一路径的黑高；若父节点也是红色，再根据叔节点颜色选择重新着色或旋转。删除更复杂：移走黑节点可能减少一条路径的黑高，需要把“额外的黑”沿父路径向上传递并修复。

这些修复规则可以被严格证明，却很容易在手写代码中因空节点、根节点和对称分支出错。除非正在实现容器库或学习算法，项目代码应优先使用标准库提供的有序映射，而不是复制一份未经充分测试的红黑树。

注 4.（语言与实现）

Java 的 TreeMap 官方定义为红黑树；C++ map/set 只保证有序关联容器的语义与对数复杂度，常见实现是红黑树但标准没有锁死布局。Rust 标准库没有红黑树映射，而提供适合缓存层次的 BTreeMap。

七、B 树与 B+ 树

二叉平衡树每个节点只放一个键，分支因子最多为二。如果一次“访问节点”的代价远大于节点内部做几次比较——例如节点位于另一个缓存行、磁盘页或网络存储中——那么减少树高比减少节点内比较更重要。B 树家族让一个节点容纳多个有序键，从而把分支因子提高到几十、几百乃至更多。

1. B 树

阶数定义因教材而异，最稳妥的描述是用最小度数 $𝑡 \geq 2$ ：非根节点含 $𝑡 - 1$ 到 $2 𝑡 - 1$ 个键，内部节点相应有 $𝑡$ 到 $2 𝑡$ 个孩子；所有叶子同层。搜索先在节点内定位区间，再下降一个孩子。插入在下降前分裂满节点；删除通过向兄弟借键或合并，保证即将进入的孩子有足够键。

B 树的一个节点内部保存有序键，键之间的间隔分别对应孩子范围。例如节点含 20, 50 时，三个孩子分别保存小于 20、位于 20 与 50 之间、大于 50 的键。搜索先在节点内部线性或二分定位区间，再只下降到一个孩子。

B 树插入不能等走到叶子才不加准备地处理满节点。常见的自顶向下算法在准备进入满孩子前先把它分裂：中间键提升到父节点，两侧键分别形成两个孩子。这样真正抵达叶子时总有空间可插入。删除则需要保证即将进入的孩子键数足够；不足时先向相邻兄弟借键，无法借用再与兄弟和父分隔键合并。

B 树节点中的键和值都可以承载记录，适合减少指针追逐。Rust 的 BTreeMap 使用连续数组容纳一个节点中的多项，官方文档也强调这能减少分配并改善缓存效率。[2]

2. B+ 树

B+ 树进一步区分内部索引与叶子数据：完整记录或记录指针只保存在叶子，内部节点只保存分隔键与孩子指针。分隔键可能在叶子再次出现，因此它与普通 B 树“每个键只出现一次”的直觉不同。所有叶子还按键序通过链连接，使范围查询不必反复回到父节点。

数据库索引使用 B+ 树，是因为一次随机页 I/O 远贵于页内数十次比较。节点大小可以对齐磁盘页或缓冲池页，一次读取带回数百个分隔键；如此高的扇出使三四层树就能覆盖海量记录。内部节点不携带完整记录，又能进一步提高同一页容纳的孩子数。

范围查询先从根定位第一个满足下界的叶条目，然后沿叶链顺序读取，直到超过上界；磁盘预读对这种连续扫描也十分友好。页分裂、合并、并发锁存和写前日志则让 B+ 树能够融入事务系统。哈希索引虽然擅长等值查询，却不自然支持范围、排序、最值和前缀扫描，这正是数据库没有简单地用哈希表取代 B+ 树的原因。

八、主流语言中平衡树的应用

语言	有序容器	公开保证	常见选择理由
Rust	`BTreeMap` / `BTreeSet`	B 树、有序迭代、对数操作	缓存友好、范围查询
Java	`TreeMap` / `TreeSet`	红黑树、基本操作 $𝑂 (log 𝑛)$	通用内存有序映射
C++	`map` / `set`	有序与对数复杂度，布局未指定	稳定迭代器、成熟节点式实现
数据库	B+ 树索引	页级平衡、叶层有序	低高度与高效范围扫描

如果只要等值查询，先考虑哈希表；需要有序迭代、上下界与范围查询，选标准库有序映射；只反复取最大或最小元素，选堆；已知离散符号频率并需要构造短前缀码，可以用最小堆建立哈夫曼树；数据驻留外存并按页访问，B+ 树通常更合适。结构的名字不是答案，工作负载才是。

Bibliography

[1] D. A. Huffman, “A Method for the Construction of Minimum-Redundancy Codes,” Proceedings of the IRE, vol. 40, no. 9, pp. 1098–1101, 1952, doi: 10.1109/JRPROC.1952.273898.
[2] The Rust Project Developers, “BTreeMap in std::collections.” [Online]. Available: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
[3] The Rust Project Developers, “BinaryHeap in std::collections.” [Online]. Available: https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
[4] Oracle, “TreeMap (Java SE 25 and JDK 25).” [Online]. Available: https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/util/TreeMap.html