dsa-deng

name	dsa-deng
description	Knowledge base from "数据结构（C++语言版）第3版" by 邓俊辉 (Deng Junhui). Use when learning or applying data structures in C++ with rigorous theoretical foundations - covers vectors, lists, stacks, queues, binary trees, graphs, search trees (BST/AVL/Splay/B/Red-Black/kd), dictionaries (skip list, hash), priority queues (heap, leftist heap), strings (KMP/BM/KR), and sorting (quicksort, selection, Shell).

数据结构（C++语言版）第3版

Author: 邓俊辉 (Deng Junhui) | Pages: ~669 | Chapters: 12 | Generated: 2026-07-08

How to Use This Skill

• Without arguments - load core frameworks and mental models from all 12 chapters
• With a topic - ask about AVL旋转, KMP算法, B-树, 红黑树, Dijkstra, 伸展树, 快速排序, 堆排序 or another indexed topic
• With chapter - ask for ch07 to get full chapter summary
• Browse - ask "what chapters do you have?" for the table of contents

Core Frameworks & Mental Models

算法分析框架 (Ch1)

• 大O记号: T(n) = O(f(n)) -- 渐进上界，忽略常系数和低次项。O(1) < O(log*n) < O(loglogn) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n)。多项式可解，指数不可解。
• 减而治之 (Decrease-and-Conquer): 问题分解为一个可直接求解的子问题 + 一个同类但规模更小的子问题，线性递归实现。
• 分而治之 (Divide-and-Conquer): 大问题分解为若干独立同类子问题，递归求解后合并。关键前提：子问题相互独立，否则导致指数爆炸（如二分递归版Fibonacci: O(2^n)）。
• 递归跟踪法: 将递归实例表示为方框节点，调用关系为有向边，直观分析复杂度。
• 递推方程法: 通过数学归纳导出复杂度定界函数，获得显式复杂度。

向量与动态空间管理 (Ch2)

• 循秩访问 (call-by-rank): A[i] 物理地址 = A + i*s，O(1) 读写--向量区别于列表的根本优势。
• 可扩充向量: 容量满载时加倍扩容（_capacity <<= 1），装填因子 < 25% 时缩容减半。分摊分析: 单次扩容 O(n) 但分摊 O(1)。
• 二分查找递进三版本: A 版三支比较（~1.5logn），B 版两支比较统一均衡（~logn），C 版保证返回不大于 e 的秩最大者。
• CBA 式下界模型: 任一基于比较的算法最坏情况成本 >= ceil(log₃(N!)) = Omega(nlogn)。排序瓶颈不可能突破，除非放弃基于比较。

列表与链式结构 (Ch3)

• 循位置访问 (call-by-position): 通过节点指针 pred/succ 定位，O(1) 插入/删除，但循秩访问退化至 O(n)。
• 哨兵节点模式: header 和 trailer 为对外不可见的固定哨兵，确保任何可见节点的前驱/后继永远存在，消除空指针特殊处理。
• 向量 vs 列表: 静态操作 (循秩 O(1) vs O(n)) 与动态操作 (插入 O(n) vs O(1)) 的两极对称。

栈、队列与递归 (Ch4)

• 栈 Stack (LIFO): 继承自 Vector，push = insert(size(), e)，pop = remove(size()-1)。用于逆序输出、括号匹配、递归模拟、延迟缓冲。
• 队列 Queue (FIFO): 继承自 List，enqueue = insertAsLast(e)，dequeue = remove(first())。
• 试探回溯法: 栈记录路径 (线绳) + 状态标记避免重复 (粉笔)。N 皇后、迷宫寻径的通用框架。
• 运算符优先级表: 二维表驱动机将语法规则转化为确定性算法，optr+opnd 双栈驱动表达式求值。

二叉树与遍历 (Ch5)

• "长子+兄弟"表示: 任意有序多叉树可等价转化为二叉树，故二叉树不失一般性。
• 真二叉树 (proper binary tree): 不含一度节点，内部节点左右孩子双全。
• 四种遍历: 先序 VLR / 中序 LVR / 后序 LRV (均用栈) / 层次遍历 (用队列)。迭代版均 O(n) 时间 O(h) 辅助空间。
• stature(p): (p) ? (p)->height : -1 -- 统一空树高度为 -1 的约定。
• Huffman 最优编码树: 自底向上贪心合并频率最小两树，O(nlogn)。

图与优先级搜索 PFS (Ch6)

• PFS 统一框架: BFS(队列)、DFS(栈)、Prim(DijkstraPU)、Dijkstra(松弛) 均为 PFS 的特例，仅优先级更新策略不同。
• BFS: 波峰集策略，队列维护。用于连通域分解、无权图最短路。
• DFS: dTime/fTime 活跃期标记，边分 TREE/BACKWARD/FORWARD/CROSS 四类，用于拓扑排序 (VISITED 逆序) 和环路检测 (BACKWARD 边)。
• Prim 算法: 贪心 -- 每次取割的最短跨越边，priority(v) = min(priority(v), weight(uk, v))。
• Dijkstra 算法: 松弛操作 priority(v) = min(priority(v), priority(uk) + weight(uk, v))，仅适用于非负权图。
• 最短路径单调性: 最短路径的任一前缀也是对应的最短路径 -- Dijkstra 贪心正确性的理论基础。

二叉搜索树与平衡 (Ch7)

• BST 顺序性: 左子树 <= 根 <= 右子树，充要条件是中序遍历序列单调非降。
• _hot 语义: searchIn() 无论成功与否，_hot 始终指向命中节点的父亲 -- 统一查找/插入/删除的位置信息。
• 等价变换: "上下可变，左右不乱"--中序遍历序列相同的 BST 彼此等价。
• "3+4" 统一重构: connect34(a,b,c,T0,T1,T2,T3) 一次完成所有 zig-zig/zig-zag/zag-zig/zag-zag 重平衡。
• AVL 平衡因子: balFac(v) = stature(lc(v)) - stature(rc(v))，|balFac| < 2。插入后至多两次旋转，删除后可能需 O(logn) 次旋转 (失衡传播)。

高级搜索树 (Ch8)

• 伸展树: 双层伸展 (zig-zig/zag-zag) 使被访问节点高度折半，利用数据局部性，分摊 O(logn)。单次最坏 O(n)。
• B-树: m 阶 B-树每内部节点含 [⌈m/2⌉-1, m-1] 个关键码，[⌈m/2⌉, m] 个分支。以内存内比较换 I/O 次数。上溢 (分裂) 和下溢 (旋转/合并)。
• 红黑树 <=> (2,4)-树 等价: 红节点提升与黑父亲水平对齐即得 4 阶 B-树节点。双红修正 (RR-1 旋转终止 / RR-2 染色递归)，双黑修正 (BB-1~BB-4)。插入/删除至多 O(1) 次旋转。
• kd-树: 递归二分划分 k 维空间，交替方向。范围查询 O(r + logn) 输出敏感。

词典与散列 (Ch9)

• 跳转表 (Skip List): 自顶向下、向右不向左的查找，塔高概率逐层减半 (p=1/2)，期望 O(logn) 查找，期望空间 < 2n。
• 除余法 + MAD 法: hash(key) = (a*key + b) mod M，M 须取素数避免聚集。
• 闭散列 (开放定址): 线性试探 / 平方试探 / 再散列，装填因子 λ < 0.5。懒惰删除标记避免查找链断裂。
• 桶排序 / 基数排序: 放弃关键码比较改用循秩访问，突破 Ω(nlogn) CBA 下界，O(n+M)。

优先级队列 (Ch10)

• 完全二叉堆: 向量紧凑存储，Parent(i)=(i-1)>>1，LChild(i)=1+(i<<1)，RChild(i)=(1+i)<<1。
• 上滤 + 下滤: insert 用上滤 (新词条自底向上攀升)，delMax 用下滤 (新堆顶自顶向下沉降)。
• Floyd 建堆: 自下而上的下滤策略，O(n) (深层次节点多而高度小，Σ高度 = O(n))。
• 左式堆: npl(null path length) 指标 + 左倾性约束 npl(lc) >= npl(rc)，merge 沿最右侧通路递归 O(logn)。insert/delMax 均可归约为 merge。

串匹配 (Ch11)

• KMP 算法: next 表将"记忆"转化为"预知力"，失配时 i 永不回退。改进版 next 表将"失败的教训"也编码进去。O(n+m)。
• BM 算法: 自右向左比对，BC 坏字符策略 + GS 好后缀策略，实际效率常优于 KMP (尤其大字符表)。
• Karp-Rabin: 指纹散列将串匹配转化为数值比对，O(1) 滑窗更新指纹。

排序 (Ch12)

• 快速排序: 先划分后递归的分治。版本 A "勤于拓展"--全等时退化 O(n^2)；版本 B "懒于拓展、勤于交换"--全等时反而均衡。
• k-选取: quickSelect 平均 O(n) (实用)；select (中位数之中位数) 最坏 O(n) (理论最优)。
• 希尔排序: 递减增量策略，底层为插入排序。互素增量序列避免"井水不犯河水"，Sedgewick 序列最坏 O(n^(4/3))。

Chapter Index

#	Title	Key Frameworks
Ch1	绪论	大O记号, 减而治之, 分而治之, 递归跟踪/递推方程, DP/制表, ADT
Ch2	向量	循秩访问, 加倍扩容+分摊, 二分查找(A/B/C), Fibonacci查找, CBA下界, 归并排序
Ch3	列表	循位置访问, 哨兵节点, 双向链表, 有序列表归并排序, 选择/插入排序
Ch4	栈与队列	LIFO/FIFO, 栈混洗(Catalan), 试探回溯, 延迟缓冲, 优先级表驱动
Ch5	二叉树	真二叉树, 遍历(4种迭代版), 长子+兄弟表示, PFC/Huffman编码, HLVFL
Ch6	图	BFS/DFS/PFS框架, Prim, Dijkstra, 拓扑排序, 边分类, 活跃期
Ch7	搜索树	BST顺序性, _hot语义, 等价变换, "3+4"重构, AVL平衡因子, 失衡传播
Ch8	高级搜索树	伸展树(双层伸展), B-树(上溢/下溢), 红黑树<=>(2,4)-树, kd-树
Ch9	词典	跳转表, 除余法/MAD法, 闭散列(开放定址), 懒惰删除, 桶/基数排序
Ch10	优先级队列	完全二叉堆(Floyd建堆), 上滤/下滤, 左式堆(merge), 就地堆排序
Ch11	串	KMP(next改进版), BM(BC+GS), Karp-Rabin(指纹散列)
Ch12	排序	快速排序(A/B版), quickSelect, select(LOT), 希尔排序(递减增量)

Topic Index

Topic	Ch		Topic	Ch
3+4重构 (connect34)	7		AVL树 (插入/删除/失衡传播)	7
B-树 (上溢/下溢/分裂/合并)	8		BC坏字符策略	11
BFS (广度优先搜索)	6		BM算法 (BC+GS)	11
BST (_hot/顺序性/等价变换)	7		CBA下界模型	2
DFS (深度优先搜索/活跃期/边分类)	6		Dijkstra算法	6
Fibonacci查找	2		Floyd建堆	10
GS好后缀策略	11		Huffman编码树	5
KMP算法 (next表/改进版)	11		Karp-Rabin指纹散列	11
Prim算法 (MST)	6		Shell/增量序列	12
kd-树 (范围查询)	8		k-选取 (quickSelect/select)	12
上滤 (percolateUp)	10		下滤 (percolateDown)	10
二叉堆 (完全二叉堆)	10		二分查找 (版本A/B/C)	2
优先级搜索 (PFS框架)	6		哨兵节点 (header/trailer)	3
回溯 (试探回溯法)	4		堆排序 (就地)	10
基数排序 (LSD)	9		大O/大Omega/大Theta记号	1
快速排序 (版本A/B/随机轴点)	12		归并排序 (向量版/列表版)	2/3
循秩访问 (call-by-rank)	2		循位置访问 (call-by-position)	3
散列 (除余法/MAD/闭散列)	9		桶排序	9
栈混洗 (Catalan数)	4		桶排序/基数排序	9
红黑树 ((2,4)-树等价/双红/双黑)	8		跳转表 (Skip List)	9
长子+兄弟表示	5		队列 (FIFO)	4
零路径长 (npl)	10		伸展树 (双层伸展/Splay)	8

Supporting Files

• glossary.md -- 150+ Chinese terminology definitions
• patterns.md -- all algorithmic patterns with when/how/trade-offs
• cheatsheet.md -- decision rules, trade-off matrices, thresholds

Scope & Limits

This skill covers the book content only. All code is C++. For Python DSA, see dsa-hello-algo. For OOP-focused C++ DSA, see dsa-yin (殷人昆). The book emphasizes rigorous theoretical foundations, complexity analysis, and "3+4" reconstruction. Not covered: Splay tree amortized proof details, advanced graph algorithms beyond Prim/Dijkstra, or STL implementation internals.