高级数据结构与算法分析¶

本课程的核心是"分析"二字——不仅要知道数据结构怎么实现，更要理解其复杂度背后的数学。数据结构部分涵盖 AVL 树（四种旋转与高度证明）、Splay 树（Zig-zag/Zig-zig 与均摊分析）、红黑树、B+ 树、左偏堆、斜堆和二项队列，每种结构都给出严格的操作复杂度推导。算法部分则按范式组织：回溯（八皇后、Turnpike 重建问题）、分治、动态规划（矩阵链乘法、最优 BST、Floyd-Warshall）、贪心、局部搜索、随机算法和并行算法，最后以 NP 完全性理论和近似算法收尾，建立起对问题难度的系统性认知。

2024-2025 秋冬大二专业课，授课老师：陈昊。