Skip to content
DSA MASTERY · CURRICULUM

Ch.5

树的应用

学习搜索树与平衡、堆与优先队列、赫夫曼编码、并查集及多路索引树。

draft · 草稿

学习目标

  • 根据有序、平衡、偏序、权重与集合不变量选择并维护合适的树结构。
  • 实现 BST/AVL、堆、赫夫曼树与并查集的核心操作,并准确分析复杂度前提。
  • 解释 B 树与 B+ 树如何用高分支降低外存 I/O,并比较点查与范围查询。

本章路径

  • 二叉搜索树、AVL 与局部旋转
  • 堆、优先队列与赫夫曼编码
  • 并查集、B 树与 B+ 树

已有内容入口

第 5 章 树的应用章节导读5.1 二叉搜索树与平衡理论文章5.2 堆与优先队列理论文章5.3 赫夫曼树与赫夫曼编码理论文章5.4 并查集理论文章5.5 B 树与 B+ 树理论文章5.6 树的应用代码题解析——从惰性维护到对立约束理论文章5.7 树的应用代码题解析——贪心最优性理论文章Lab 05-T-01:森林与二叉树转换题精练相关 LabLab 05-T-02:树与森林遍历题精练相关 LabLab 05-T-03:哈夫曼树与编码题精练相关 LabLab 05-T-04:并查集题精练相关 LabLab 05-T-05:堆题精练相关 LabLab 05-E-01:二叉搜索树的插入与查找相关 LabLab 05-E-02:二叉搜索树的删除相关 LabLab 05-E-03:验证 BST 先序遍历序列相关 LabLab 05-E-04:BST 中第 k 小的元素相关 LabLab 05-E-05:AVL 树的插入与平衡相关 LabLab 05-E-06:将二叉搜索树变平衡相关 LabLab 05-E-07:祭坛三元组相关 LabLab 05-E-08:最小堆的实现相关 LabLab 05-E-09:数据流中的中位数相关 LabLab 05-E-10:任务调度器相关 LabLab 05-E-11:前 K 个高频元素相关 LabLab 05-E-12:吃苹果相关 LabLab 05-E-13:可以到达的最远建筑相关 LabLab 05-E-14:蚯蚓相关 LabLab 05-E-15:哈夫曼编码相关 LabLab 05-E-16:最优合并问题相关 LabLab 05-E-17:k 叉哈夫曼树相关 LabLab 05-E-18:并查集的实现相关 LabLab 05-E-19:动态连通性查询相关 LabLab 05-E-20:食物链相关 LabLab 05-E-21:银河英雄传说相关 LabLab 05-E-22:亲戚相关 LabLab 05-E-23:冗余连接相关 LabLab 05-E-24:关押罪犯相关 LabLab 05-E-25:星球大战相关 LabLab 05-E-26:B 树的插入相关 LabLab 05-E-27:B+ 树的范围查询相关 Lab