Posts

记录完成 CMU 15-445 各 Project 的学习过程，重点整理数据库内核中的缓冲池、B+ 树、并发控制与调试心得。

基于带注释的完整代码介绍跳表的层高生成、跨度维护与有序集合操作，并用洛谷 P3369 作为正确性检验。

给出一份基础跳表实现，说明随机层高、跨度维护以及排名、前驱后继等常见操作。

从 DFS 序性质出发整理树链剖分的核心思想，说明重链划分、线性化与路径/子树查询的实现基础。

以颜色平衡树题为例讲解 dsu on tree 的保重儿子、删轻留重与统计维护思路。

围绕稳定排序需求，介绍 MergeSortWithoutBuffer 的核心思想、rotate 技巧以及小 buffer 优化，讨论如何在更低额外空间下完成归并。

以课程设计为背景，梳理无向图关节点问题的需求、Tarjan 求解思路，以及如何把关节点改造成非关节点的实现细节。

从课程设计角度回顾红黑树的性质、实现框架与迭代器设计，再延伸到顺序统计等应用，适合作为手写 STL 风格 map 的实践记录。

从 libstdc++ 源码切入分析 std::sort 的 introsort 策略，理解快排、堆排与插排如何组合工作。

站在实现难度、扩展性和基础操作效率三个维度，对 B 树、AVL、红黑树、Splay、Treap 与 Trie 方案做一次总览式复盘。