DSA Mastery理论与实验教程

外观

第 5 章 · 树的应用

第 5 章 树的应用

从有序查找、优先级处理、最优编码、集合维护到外存索引，系统学习树结构的典型应用。

约 5 分钟阅读更新于 2026-08-24Azenreview

第 4 章回答了“树是什么、怎样存、怎样遍历”。本章继续追问：一旦给树附加有序性、完全性、权重或集合语义，它能替我们解决什么问题？

二叉搜索树把比较结果变成搜索方向；AVL 树用旋转控制高度；堆只维护局部偏序，却能持续取出最高优先级；赫夫曼树把频率变成短码；并查集用一片浅森林维护集合划分；B 树与 B+ 树则用高分支降低外存访问次数。这些结构的共同点不是“都长得像树”，而是都在维护一种可利用的不变量。

本章定位 ​

从形状到约束

普通二叉树只规定每个节点至多有两个有序孩子。本章的结构会再增加一层合同：

  • 二叉搜索树要求左小右大；
  • AVL 树要求每个节点左右高度差受限；
  • 堆要求父节点与孩子保持偏序；
  • 赫夫曼树让高频符号靠近根；
  • 并查集让每个集合由一棵代表树管理；
  • B 树与 B+ 树让一个外存页容纳大量分支。

新增的约束会带来更强的操作保证，也会增加插入、删除时维护不变量的成本。

学习目标 ​

完成本章后，你应该能够：

  1. 根据二叉搜索树的不变量完成查找、插入、删除，并解释退化原因；
  2. 识别 AVL 树的 LL、RR、LR、RL 四类失衡，选择正确旋转恢复平衡；
  3. 用数组实现堆，推导自底向上建堆为什么是 O(n)，并使用优先队列解决 Top-K 等问题；
  4. 从字符权重构造赫夫曼树，计算 WPL，生成前缀码并完成编码、解码；
  5. 实现带路径压缩和按秩或按大小合并的并查集，说明 α(n) 结论的前提；
  6. 解释 B 树与 B+ 树为什么适合外存，手算查找、分裂、借位和合并过程；
  7. 面对新问题时，从高频操作、数据规模和存储层级出发选择结构，而不是只凭名称套模板。

前置知识 ​

建议先统一高度约定

本章在 AVL 树中约定：空树高度为 −1，叶节点高度为 0。其他教材也可能把空树和叶节点高度分别记作 0、1；只要全程一致，平衡判断不变。遇到不同资料时先检查约定，再比较公式。

五篇文章如何分工 ​

学习问题对应文章完成后的可检查能力
怎样让查找树既保持有序，又避免退化？5.1 二叉搜索树与平衡能实现 BST/AVL 的核心操作并手算旋转
怎样持续取得最大或最小优先级？5.2 堆与优先队列能实现堆、分析 Heapify，并解决 Top-K
怎样让高频符号获得更短编码？5.3 赫夫曼树与赫夫曼编码能构造最优前缀码并完成编解码
怎样高效维护不断合并的集合？5.4 并查集能实现优化并查集并用于连通性/Kruskal
为什么数据库索引使用多路平衡树？5.5 B 树与 B+ 树能手算分裂、借位、合并并比较两类索引树

本章知识图谱 ​

graphviz Diagram

横向比较时始终问三个问题：

  1. 维护什么不变量？ 它决定操作正确性。
  2. 一次操作会触碰多高或多少个节点？ 它决定时间复杂度。
  3. 节点位于内存还是外存页？ 它决定真正昂贵的成本单位。

推荐学习顺序 ​

  1. 先学 BST 与 AVL，建立“更新后修复不变量”的基本模式。
  2. 再学堆与优先队列，体会只维护部分顺序也能高效解决问题。
  3. 用优先队列构造赫夫曼树，把结构选择与贪心策略连接起来。
  4. 学并查集，理解树不一定用于遍历，也可以用来压缩代表关系。
  5. 最后学习 B 树与 B+ 树，把复杂度视角从 CPU 操作扩展到页 I/O。

本章 Labs ​

理论题库与编程实验均已开放

侧栏“本章 Labs”当前提供两类练习：

  • 理论 Theory：五组交互题库，覆盖森林转换、树与森林遍历、赫夫曼编码、并查集和堆。选择题可直接提交、查看解析并重新作答；源材料已有的综合题保留在对应页面中。
  • 实验 Exercise：17 道可编译、可评测的编程实验，按主题分布为二叉搜索树 5 道、堆与优先队列 3 道、赫夫曼 3 道、并查集 4 道、B 树与 B+ 树 2 道。每道实验都提供 student/ 起始代码、solution/ 参考实现与配套测试用例。

工程 Project 仍保留空槽位，收到可执行题目后再依据站内 Lab 更新与测试指南选择类型并接入。

理论题库 ​

入口对应文章
森林与二叉树转换题精练承接 4.5 树、森林与二叉树
树与森林遍历题精练承接 4.5 树、森林与二叉树
哈夫曼树与编码题精练5.3 赫夫曼树与赫夫曼编码
并查集题精练5.4 并查集
堆题精练5.2 堆与优先队列

编程实验 ​

主题实验
二叉搜索树与平衡BST 插入与查找、BST 删除、验证 BST 先序序列、BST 第 k 小元素、AVL 插入与平衡
堆与优先队列最小堆实现、数据流中位数、任务调度器
赫夫曼树与编码哈夫曼编码、最优合并问题、k 叉哈夫曼树
并查集并查集实现、动态连通性查询、食物链、银河英雄传说
B 树与 B+ 树B 树的插入、B+ 树的范围查询

学习方法 ​

  • 先手算再运行：对旋转、堆调整、赫夫曼合并和 B 树分裂，先画出每一步的局部结构。
  • 把复杂度写成结构参数：先用树高 h、符号种类数 σ、堆大小 k 表达，再代入平衡条件。
  • 主动制造反例：递增插入 BST、在堆中误用二分查找、让并查集执行删除，观察不变量在哪里失效。
  • 区分逻辑成本和存储成本：B+ 树的优势主要来自减少页 I/O，不只是比较次数更少。

准备好后，从5.1 二叉搜索树与平衡开始。