DSA Mastery理论与实验教程

外观

动手实验

Lab 08-P-01：自平衡查找树——AVL 旋转维护与退化对比

实现 AVL 树的四种旋转与删除再平衡，用不变量检查与普通 BST 基线对比退化。

08P01300～420 分钟更新于 2026-08-21RichardYi-SYSU-Mac综合draft

目标 ​

实现一棵自平衡二叉查找树（AVL 树），先证明它"和普通 BST 做得一样对"，再回答"自平衡用局部旋转换来的最坏情况保证，究竟值不值"。本 Lab 是查找这一章的收口工程，要求你把递归插入、旋转、删除再平衡和不变量检查四个能力整合进同一个系统。

前置知识 ​

  • 第 8.2 节二叉排序树的查找、插入与三类删除；
  • 第 8.3 节平衡查找树中 LL / RR / LR / RL 四种旋转与平衡因子；
  • 第 0 章时间复杂度与递归分析；基本的 C++ 类、std::unique_ptr 与 std::vector。

建议用时 ​

300～420 分钟（5～7 小时），建议分 2～3 次提交：先做普通 BST 基线，再做 AVL 插入旋转，最后做删除再平衡。

任务与评分 ​

Task类型权重依赖交付物
bststdio30无普通 BST 命令行驱动
avlCTest50bstcontracts/avl.hpp 的实现
reportmanual20avl树高对比、旋转与再平衡报告

顶层评分会分别显示自动分和待人工分。任务依赖用于推荐顺序和定位，不会暗中把前置任务变成"一票否决"。

运行与评分 ​

进入本目录后优先使用：

powershell
make doctor
make run
make run TASK=bst CASE=001-basic
make run TASK=avl
make score

Windows 未安装 GNU Make 时，在仓库根使用免 Make 兜底：

powershell
pnpm lab:run -- labs/chapter-08/project/P-08-01-avl-tree-rotations
pnpm lab:run -- labs/chapter-08/project/P-08-01-avl-tree-rotations --task bst --case 001-basic
pnpm lab:score -- labs/chapter-08/project/P-08-01-avl-tree-rotations

维护者可用 --target solution 验证参考实现自动部分满分。Project 使用 CMake ≥ 3.25 与 CTest；CMake 可选择当前平台的可用生成器，Ninja 只是可选加速项。所有构建产物只写入 .lab-cache/。

任务一：普通 BST 基线 ​

从标准输入逐行读取指令，直到文件结束：

指令含义输出
insert x插入关键字（重复键忽略）无
find x查找关键字命中 1，未命中 0
remove x删除关键字成功 1，未找到 0
inorder中序遍历升序序列，空格分隔，空树输出空行
height树高空树 0，否则最长根到叶路径上的结点数

任务二：AVL 树 ​

实现 contracts/avl.hpp 中的 avl::AvlTree。每次插入、删除后都必须保持：中序严格升序、任意结点平衡因子在 {-1, 0, 1} 内、结点高度等于左右子树较大高度加 1。

失衡类型触发条件（新结点插入后）修复
LL左孩子的左子树过深右单旋
RR右孩子的右子树过深左单旋
LR左孩子的右子树过深先左旋左孩子，再右单旋
RL右孩子的左子树过深先右旋右孩子，再左单旋

插入在第一个失衡结点处旋转一次即可；删除可能连续多处失衡，需逐层回溯重新平衡。verify() 应校验有序性、高度一致性与平衡因子范围，供每次修改后调用。

测试输入 ​

  • 四组三键插入分别触发 LL / RR / LR / RL，旋转后树高应为 2；
  • 有序插入 1..15 后依次删除 8、4、12、2、14、6、10，验证多级回溯再平衡；
  • 有序插入 1..1000，AVL 树高应约为 ⌊log₂1000⌋+1 = 10，远低于普通 BST 的 1000。

提交物 ​

  • 可运行代码；
  • make run TASK=bst 与 make run TASK=avl 的输出；
  • 设计说明（500～800 字），覆盖"复杂度分析要求"的 4 个问题；
  • 报告模板 report/template.md 的填写。

验收标准 ​

复杂度分析要求 ​

在说明文档里回答：

  1. 四种旋转各是常数时间，为什么一次插入最多触发一次旋转、一次删除可能触发 O(log n) 次？
  2. 普通 BST 与 AVL 的单次查找、插入、删除的平均与最坏复杂度各是多少？
  3. 有序插入时普通 BST 与 AVL 的树高差异如何量化？给出反例（3 个键演示 LL 旋转即可）。

加分项 ​

  • 再实现一棵红黑树，比较三种结构在同一负载下的旋转次数与树高；
  • 把每次旋转前后的树形输出成 DOT 或 HTML 快照，肉眼验证旋转方向；
  • 研究"删除顺序不同导致树形不同"的现象，找出一个使 AVL 需要连续回溯的序列。

延伸思考 ​

  1. AVL 用"严格平衡因子 ≤ 1"换最坏情况保证，红黑树放宽到"黑高平衡"，代价是树高略大。这个取舍什么时候更划算？
  2. 如果只做查找、从不删除，AVL 的旋转是否永远必要？有没有更简单的替代？
  3. 把 AVL 的"高度"改成"子树结点数"（即加权平衡树），会带来什么新性质？