原笔记信息

• 原笔记来源：数算.md
• 本资料由原笔记蒸馏整理，建议配合原笔记查漏补缺。

复习 / 预习建议

• 先用“速览”建立主线：数据结构关注逻辑关系、存储映射和操作，算法关注在有限步骤内正确求解问题。
• 预习时优先理解每种结构“适合什么操作”；复习时再记复杂度、边界条件、稳定性和维护规则。
• 线性结构、树、图、排序、检索和索引是主干；AVL、红黑树、B/B+ 树和 Splay 是平衡与外存效率的重点。
• 排序部分建议按“简单排序 -> 分治排序 -> 非比较排序 -> 外排序”串联，重点比较时间、空间和稳定性。
• 每章选择题用于查漏；做错后回到对应小节看定义、算法流程或图形调整规则。

速览

• 数据结构由逻辑结构、存储方式和定义在数据上的运算组成；ADT 只描述数据对象和操作，不涉及实现细节。
• 线性表可用顺序表或链表实现：顺序表随机访问好、空间密度高；链表适合频繁插入删除和动态长度。
• 栈和队列是受限线性表：栈用于表达式求值、递归模拟；队列用于 FIFO 流程和层次遍历。
• 树和图是主要非线性结构：二叉树有遍历、存储和路径性质；图要掌握存储、遍历、最短路径和最小生成树。
• 内排序要比较稳定性、时间、空间和输入敏感性；比较排序下界为 $\Omega(n\log n)$，桶/基数排序依赖关键码范围。
• 外排序的核心是减少外存 I/O：置换选择排序生成更长顺串，k 路归并用胜者树/败者树降低比较开销。
• 检索与索引围绕“预处理换查询效率”：顺序/二分/分块、散列、线性索引、倒排索引、B 树、B+ 树各自服务不同场景。
• AVL、红黑树和 Splay 都是搜索树改进：AVL 更平衡，红黑树旋转较少且稳定，Splay 利用访问局部性提供均摊保证。

知识点整理

概论：数据结构、ADT 与算法效率

本章解决“数算到底研究什么”。数据结构负责把现实问题抽象成数据对象、关系和操作，算法负责给出求解步骤，效率度量用于比较不同实现。预习时先抓“逻辑结构”和“存储方式”的区别；复习时重点记 ADT、算法特性和大 $O/\Omega/\Theta$ 的含义。

数据结构与抽象数据类型

• 数据结构按逻辑关系组织数据：
  • 线性结构：线性表、栈、队列、串等。
  • 非线性结构：树、二叉树、Huffman 树、二叉搜索树、图等。
• 数据需要以一定存储方式映射到计算机中，主要包括顺序、链接、索引、散列四类。
• 数据结构还要在数据上定义运算，例如建立、清除、插入、删除、修改、排序、检索。
• 抽象数据类型（ADT）可写作 $(S,op)$，只定义逻辑结构和运算，不讨论具体实现细节。

算法特性与效率度量

• 问题是从输入到输出的函数；算法是求解问题的方法，是有限指令序列；程序是算法在编程语言中的实现。
• 算法特性：
  • 通用性：对合法输入总能给出正确结果。
  • 有效性：由具体、有限的指令构成。
  • 确定性：每一步含义明确。
  • 有穷性：必须在有限步内结束。
• 基本算法类型包括穷举、搜索、分治、贪心、动态规划。
• 大 $O$ 表示渐近上界： $$\exists n_0,C,\forall n\geq n_0,\ f(n)\leq Cg(n)$$
• 大 $\Omega$ 表示渐近下界，大 $\Theta$ 表示上下界同时成立。

线性表、栈、队列与字符串

本章从最基础的线性结构开始：线性表提供有序元素序列，栈和队列是在访问端受限制的线性表，字符串是元素为字符的线性表。预习时先理解每种结构的访问约束；复习时重点比较顺序存储与链式存储、栈队列溢出情形和字符串匹配的 next 数组。

线性表

• 线性表是元素的有穷序列，基本概念包括表目、索引、长度、空表。
• 线性结构 $B=(K,R)$ 中，$K=a_0,\ldots,a_{n-1}$，$R=\{r\}$ 表示前驱/后继关系。
• 线性结构特点：
  • 均匀性：不同元素必须有相同类型和长度。
  • 有序性：元素间有前驱/后继顺序。
• 线性表主要属性包括长度、表头、表尾、当前位置；基本运算包括建立、清除、插入、删除、修改、排序、检索。

顺序表与链表

• 顺序表也称向量，用定长一维数组顺序存储，存储密度为 1，支持随机访问。
• char S[M]="xxx"; 这类定长数组因结尾有 \0，实际最多存储长度为 $M-1$ 的字符串。
• 链表由数据域和指针域组成，可分为单链表、双链表、循环链表。
• 带头节点的单链表固定存在 head 节点，便于在最前面插入和删除。
• 循环链表头尾相连，可从任意节点访问整个链表；非循环链表尾节点指针域为空。
• 对比：
  • 顺序表无指针额外开销，读访问方便，适合静态或随机访问多的场景。
  • 链表长度可动态变化，适合插入删除多的场景。
  • 元素越多且数据域占比越大，顺序表空间优势越明显。

栈

• 栈是 LIFO/FILO 结构。
• $n$ 个元素的合法出栈序列数量为 Catalan 数： $$f(n)=\sum_{i=0}^{n-1}f(i)f(n-1-i)=\frac{1}{n+1}\binom{2n}{n}$$
• 顺序栈：
  • 上溢：栈满时入栈。
  • 下溢：栈空时出栈。
• 链式栈用单链表存储，维护栈顶指针。
• 合法出栈序列不存在 3 1 2 这种模式。

表达式求值与递归转非递归

• 后缀表达式求值：读到数字入栈；读到运算符 $OP$，取出 $z_n,z_{n-1}$，计算 $z_{n-1}\ OP\ z_n$ 后压回栈。
• 中缀转后缀：
  • 数字直接输出。
  • 左括号入栈。
  • 右括号触发出栈直到左括号。
  • 运算符读入时，先输出栈中优先级大于等于它的运算符，再将当前运算符入栈。
  • 最后将栈中运算符依次输出。
• 尾递归只有一次自身调用，且调用是返回前最后一步，可直接改写成循环，不需要额外栈空间。
• 通用递归转非递归：手动构造栈元素，保存下传参数和返回地址；为函数入口、每次调用后位置和出口设置标签，返回时根据返回地址恢复执行。

队列

• 队列是 FIFO/LILO 结构。
• 顺序队列用头尾两个变量表示队头和队尾。
• 常见问题：
  • 上溢：队列满时入队。
  • 下溢：队列空时出队。
  • 假溢出：尾指针到数组末尾，但头指针前仍有空位。
• 循环队列若要区分满和空，需要额外标记元素个数或是否有元素，因为队列状态有 $n+1$ 种，而头尾相对位置只有 $n$ 种。
• 链式队列维护头指针和尾指针；顺序队列和链式队列都不能直接访问内部任意元素。

字符串与匹配

• 字符串是元素属于字符集的线性表；连续子段称为子串，空串是任意串的子串。
• C 字符串函数包括 strlen、strcpy、strcat、strcmp、strchr、strrchr、strstr。
• 动态长度可用 string，例如 s.substr(id,len) 返回从 id 开始长度为 len 的子串。
• 字符串匹配中： $$N[i]= \begin{cases} -1&i=0\\ \max_k s[0...k-1]=s[i-k,i-1]&k\ exist\\ 0&other \end{cases}$$
• 优化：求 N[i] 时，若 S[i]==S[bj]，二者会同时失配，可设 N[i]=N[bj]。
• 若模式串长度大于主串剩余部分，可直接退出，减少无效匹配。

二叉树、一般树与 Huffman 树

本章进入非线性结构。二叉树是很多树结构和搜索结构的基础，一般树可通过左儿子/右兄弟表示与二叉树互相转换，Huffman 树体现了树结构在编码优化中的应用。预习时先掌握术语和遍历；复习时重点记二叉树性质、堆操作和 Huffman 构造。

树与二叉树基本概念

• 树是 $n$ 个点的有穷集合，非空树有且仅有一个根，根没有前驱，其他节点都有且仅有一个前驱。
• 叶节点/外部节点没有子树；分支节点/内部节点有子树。
• 路径长度是路径中边数；度数是子树数目；根层数为 0；树的深度是节点最大层数；树的高度是深度加 1。
• 二叉树区分左右儿子。
• 满二叉树：节点要么有两个儿子，要么是叶节点。
• 完全二叉树：除最后一层外全满，最后一层从左侧连续填充。
• 点数一定时，完全二叉树中根到各节点路径总和最小。
• 扩充二叉树把空子树替换为特殊外部节点，得到满二叉树。
• 重要性质：
  • 扩充二叉树中外部路径和 $E$、内部路径和 $I$、内部节点数 $n$ 满足 $E=I+2n$。
  • 二叉树中叶节点数比度为 2 的节点数多 1。
  • 非空二叉树空子树数等于节点数加 1。
  • $n$ 个节点的完全二叉树高度为 $\lceil\log_2(n+1)\rceil$，深度为 $\lceil\log_2(n+1)\rceil-1$。

二叉树遍历、存储和搜索

• 遍历包括前序、中序/对称序、后序。
• 中序 + 前序或中序 + 后序可还原二叉树。
• 非递归遍历通常用栈模拟：沿左子树压栈，回退后转向右子树；后序遍历需要额外标记区分第一次回到节点和右子树遍历结束后访问节点。
• 结构紧凑时可用顺序存储，通过下标关系推断父子；链式存储用两个指针指向左右儿子。
• $n$ 个节点的二叉链表有 $n+1$ 个空指针。
• 存储密度 $\alpha$ 表示数据本身存储量占整个结构占用存储量的比例。
• 链式存储中，若指针大小为 $p$、数据大小为 $d$，总空间为 $(2p+d)n$，结构性开销为 $2pn$。
• 二叉搜索树满足左子树关键码小于节点关键码、右子树关键码不小于节点关键码。
• 删除二叉搜索树节点时，可用左子树最大值或右子树最小值替代；被选中点最多有一个儿子，再把其儿子接到原位置。

堆与 Huffman 树

• 最小堆中每个节点值都不大于其子孙；堆一定是完全二叉树，因此适合顺序存储。
• 堆不唯一，交换左右儿子仍合法。
• 筛选法建堆：从最后一个分支节点开始向前，对每个节点执行 shiftdown。
• 插入：新元素放堆尾，再 shiftup。
• 删除：将最后一个元素放到删除位置，再根据大小选择 shiftup 或 shiftdown。
• 定长编码需要 $\lceil\log_2 n\rceil$ 位。
• 前缀编码要求任何字符编码都不是另一个字符编码的前缀，可通过根到叶路径唯一解码。
• 带权外部长度是每个叶子频次乘以到根路径长度之和。
• Huffman 树使带权外部长度最小；构造方法是每次取频次最小的两个节点合并，新节点频次为二者之和，直到只剩一个节点。
• Huffman 树是满二叉树且不唯一。
• k 叉 Huffman 树中，每个 k 度节点使总数减少 $k-1$；若最后需要 $r<k$ 度节点，先选 $r$ 个节点合并，再每次选 $k$ 个合并。

一般树和森林

• 树的儿子区分顺序，但二度树不等于二叉树，因为一度节点的儿子不区分左右。
• 森林是零棵或多棵不交树。
• 森林到二叉树的一一对应：每个节点左儿子为最左子节点，右儿子为后兄弟。
• 先根遍历森林等价于对应二叉树的前序遍历；后根遍历森林等价于对应二叉树的中序遍历。
• 树的链式存储包括子节点链表表示、静态左儿子/右兄弟表示、动态多指针表示、动态左子右兄表示。
• 父指针表示法可实现并查集；优化包括加权合并和路径压缩。
• 顺序存储森林可用带右链先根次序、带双标记先根次序、带双标记层次次序、带度数后根次序等方式。

图

图用于表达多对多关系，关键问题包括如何存储、如何遍历、如何求路径和生成树。预习时先分清有向/无向、连通/强连通、路径/回路等术语；复习时重点比较邻接矩阵和邻接表、Dijkstra/Bellman-Ford/Floyd 的适用条件、Kruskal/Prim 的使用场景。

基本概念和存储

• 图 $G=(V,E)$ 中，$V$ 为点集，$E$ 为边集。
• 若 $u$ 可通过一条边到达 $v$，称 $v$ 为 $u$ 的邻接点。
• 路径是点序列，且后一个点是前一个点的邻接；简单路径除起点终点可能相同外，其他点互不相同。
• 起点与终点相同的简单路径称为回路/环；路径长度是边数。
• 有向图中，若存在 $v_0$ 可到达所有点，则称它为图的根，图为有根图。
• 连通图：任意两点都可互相到达；有向图的强连通要求方向也可达，弱连通则把边看作无向后连通。
• 连通分量/强连通分量是极大连通/强连通子图。
• 完全图中任意两点之间都有边；有向完全图两点之间有两条方向相反的边。
• 稀疏图：边数小于完全图的 $5\%$。
• 存储方式：
  • 邻接矩阵适合稠密图。
  • 邻接表空间 $O(V+E)$（有向）或 $O(V+2E)$（无向），适合稀疏图，但不支持随机访问边。
  • 十字链表用于有向图，每条边同时挂在起点出边链表和终点入边链表中。

遍历、最短路径与最小生成树

• 图遍历从给定节点出发，访问且仅访问所有可达节点一次，核心是用数组标记是否访问过。
• 有向无环图存在拓扑序列，拓扑排序就是求出所有边都从前往后的序列。
• DFS 拓扑排序：每个点在返回前输出，最终输出的逆序是拓扑序列，本质上不断输出出度为 0 的节点。
• 有负环的图不存在最短路。
• Dijkstra 不能处理负边：有负环无法判断，有负边可能求错。
• Bellman-Ford 可处理负边并判断源点可达负环；第 $k$ 轮后，长度不超过 $k$ 条边的最短路已更新正确，最多 $n-1$ 轮。
• Floyd 是全源最短路，可处理负边并判断负环。
• 生成树包含图所有点且是一棵树；最小生成树是边权和最小的生成树。
• Kruskal 和 Prim 都可求最小生成树；Prim 更适合稠密图。

内排序

排序部分是算法比较的集中训练。每个排序算法都要同时看时间、空间、稳定性和输入敏感性；同为 $O(n\log n)$ 的算法，常数、局部性、是否稳定也会影响实际表现。预习时先会描述每种排序流程；复习时重点掌握复杂度表、比较排序下界和桶/基数排序前提。

基本概念

• 序列是由记录组成的线性表；记录是排序基本单位。
• 关键码唯一确定记录，排序码是排序依据。
• 内排序指整个排序过程在内存中完成。
• 稳定性：相同排序码记录在排序后相对次序不变。
• 衡量标准包括时间、空间和算法复杂程度。

简单排序和堆排序

• 插入排序：每次把第 $i$ 个元素插入前 $i-1$ 个元素构成的有序序列。
  • 稳定，空间 $O(1)$。
  • 最好 $O(n)$，最坏和平均 $O(n^2)$。
• 冒泡排序：不断从后往前比较，把第 $i$ 小的元素冒到前面；一轮无交换可提前结束。
  • 稳定，空间 $O(1)$。
  • 最好 $O(n)$，最坏和平均 $O(n^2)$。
• 选择排序：每轮从剩余元素中选最小值，与第 $i$ 个交换。
  • 不稳定，空间 $O(1)$。
  • 比较 $O(n^2)$，移动 $O(n)$，时间 $O(n^2)$。
• 堆排序：建最大堆，每次删除堆顶相当于把最大值放到序列末尾。
  • 空间 $O(1)$。
  • 建堆 $O(n)$，删除总计 $O(n\log n)$，总时间 $O(n\log n)$。

Shell、归并与快速排序

• Shell 排序把序列按间隔 $\Delta$ 分成子序列，各自插入排序，再逐步减小 $\Delta$ 直到 1。
• Shell 排序利用短序列和部分有序序列上插入排序较快；若间隔序列不互素，可能退化。
• 取 $\Delta_i=2^i-1$ 可改进；取 $2^p3^q$ 可接近 $O(n\log^2 n)$。
• 归并排序把序列分为两半分别排序，再归并。
  • 稳定，空间 $O(n)$。
  • 时间 $\Theta(n\log n)$，不依赖输入。
  • 短序列可改用插入排序减少递归消耗。
• 快速排序选择轴值 $v$，把小于 $v$ 的放左侧、大于 $v$ 的放右侧，再递归两边。
  • 轴值可选最左、随机、三数中值。
  • 空间为递归深度，最坏 $O(n)$，最好/平均 $O(\log n)$。
  • 时间递推 $T(n)=T(i)+T(n-i-1)+cn$，最坏 $O(n^2)$，最好/平均 $O(n\log n)$。
  • 快排通常比归并快，因为读写次数少且局部性更好。
• 快速选择用快速排序划分思想求第 $k$ 大，期望 $O(n)$。
• STL sort 使用自省排序：递归深度过大改堆排序，短段停止后用最终插入排序；右侧递归、左侧用循环可减少函数调用。

比较排序下界、桶排序和基数排序

• 只比较相邻元素的排序（插入、冒泡）平均要处理 $n(n-1)/4$ 个逆序对，平均 $O(n^2)$。
• 基于比较的排序下界为 $\Omega(n\log n)$：比较过程可视作决策树，每个叶子代表一种排列，叶子至少 $n!$ 个，因此深度至少 $\log(n!)=\Omega(n\log n)$。
• 桶排序适用于元素属于 $\{0,1,\ldots,m-1\}$ 的场景，时间 $O(n+m)$，空间 $O(n+m)$。
• 链表桶排序稳定；计数桶排序通过前缀和并从后往前填输出数组也稳定。
• 基数排序适用于 $m$ 很大但可分解为 $d$ 个字段/数位的关键码。
• MSD 先高位后低位，符合人类习惯，但可能产生大量桶。
• LSD 先低位后高位，依赖桶排序稳定性，时间 $O(d(n+r))$，空间 $O(n+r)$。
• 链式基数排序用链式桶排，直接修改指针，不需要额外数组转存。
• 若无重复关键码，$r^d\geq n$，所以 $d\geq\log_r n$，基数排序复杂度反思仍有 $\Omega(\log n)$ 的位数因素。
• 间接排序通过索引数组排序，避免移动过大的原记录。

外排序

外排序关注内存装不下全部数据时怎样排序。核心瓶颈是外存 I/O，因此目标不是只减少 CPU 比较次数，还要尽量生成更长顺串、减少归并轮数和缓冲区读写。预习时先理解顺串和 k 路归并；复习时重点掌握置换选择排序、胜者树和败者树。

存储介质与顺串

• 一般内存快、小、贵、易失；外存慢、大、便宜、非易失。
• 交错因子描述磁盘扇区排布。
• 外排序根据内存大小把外存数据分段，每次读入一段排序。
• 已排好的段称为顺串或归并段。
• 目标是生成尽可能长的顺串，减少顺串数量，从而减少后续归并开销。

置换选择排序与 k 路归并

• 常规内部排序输出长度最多为内存大小，顺串不够长。
• 置换选择排序流程：
  • 从外存读满内存并建立小根堆。
  • 每轮比较堆顶和上一个输出值。
  • 若堆顶大于上一个输出值，就输出堆顶，并读入新元素维护堆。
  • 若堆顶小于上一个输出值，就将堆顶移到堆尾视为当前顺串不可用。
  • 当前顺串结束后，剩下元素可重新建堆生成下一顺串。
• 堆大小为 $n$ 时，最好一轮解决整个输入文件，最坏顺串长度为 $n$，平均顺串长度为 $2n$。
• k 路归并 $m$ 个顺串至少需要 $\lceil\log_k m\rceil$ 轮，归并顺序本质上类似 Huffman 树问题。
• 常规 k 路归并每次找最小需要 $k-1$ 次比较，开销大。
• k 路归并有 $k$ 个输入区和 1 个输出缓冲区，每个元素读入一次、输出一次。
• 胜者树：叶子对应各路当前最小元素，内部节点维护较小顺串编号；输出后只更新一条路径。
• 败者树：父节点保存输者，赢者继续向上比较；更新时只需与路径节点比较，常数更小。
• 总复杂度： $$O(k+n\log k)$$

检索与散列

检索研究如何在记录集合中找关键码等于给定值的记录。顺序、二分、分块适合不同有序程度和更新需求；散列用空间和哈希函数换接近常数的查询。预习时先理解 ASL 和装载率；复习时重点比较冲突处理策略、墓碑标记和装载率对性能的影响。

顺序表检索、集合检索和分块检索

• 检索过程包括预处理、查询解析、检索和格式化输出。
• 平均检索长度 ASL 表示平均比较次数。
• 顺序检索可在 0 处设哨兵，倒序比较；无需预处理，插入 $O(1)$。
  • 检索成功 ASL 为 $(n+1)/2$。
  • 检索失败需比较 $n+1$ 次，包括哨兵比较。
  • 成功/失败概率不同，则 $(n+1)/2\leq ASL\leq n+1$。
• 二分检索要求表已排序。
• 分块检索把数据划分成块，块间有序，并维护块最大值和起始编号：
  • 先在块上二分，再块内顺序比较：$O(\log(n/b)+b)$。
  • 块上顺序比较时可做到 $O(\sqrt n)$。
  • 优势是插入删除维护相对小；局限是块大小可能失衡，需要额外空间维护块信息。
• 集合检索可用 01 位向量（bitset）表示集合。

散列检索

• 哈希表装载率： $$\alpha=\frac{n}{m}$$ 其中 $n$ 为元素数量，$m$ 为哈希表长度。
• 冲突：不同关键码通过哈希函数得到相同地址；发生冲突的关键码称为同义词。
• 常见散列函数包括取模、乘法散列、平方取中、按字符位分布选择、进制变换、折叠法、ELF hash。
• 开散列：每个哈希值维护一个链表，可把链表改成二叉搜索树等结构。
• 闭散列：计算一系列备用地址，找第一个非空位置存储。
• 线性探查：$d,d+1,d+2,\ldots$；容易产生聚集。
• 二次探查：$d+1^2,d-1^2,d+2^2,\ldots$；不能保证探查所有位置。
• 伪随机探查：预生成随机排列 $p_i$，每次探查 $d+p_i$。
• 二次聚集来自初始地址相同导致后续探查地址相同；双散列可用 $$d_i=(d+i h_2(key))\bmod M$$ 其中 $h_2(key)$ 最好与 $M$ 互质。
• 删除：
  • 开散列可直接删除。
  • 闭散列要用墓碑标记，防止探查链被截断；之后插入可复用墓碑。
• 效率近似： $$1+\sum_i^\infty \left(\frac{n}{m}\right)^i=\frac{1}{1-\alpha}$$
• 插入过程中平均步数近似： $$\frac{1}{\alpha}\ln\frac{1}{1-\alpha}$$
• 当 $\alpha\leq0.5$ 时，多数操作预期小于 2；超过 0.5 后性能可能急剧下降。插入删除频繁时需要定期重新哈希，清除墓碑或调整高频元素位置。

索引

索引用额外结构把关键码和记录位置关联起来，是大型文件和数据库提高检索效率的核心手段。预习时先理解主文件、索引文件、稠密/稀疏索引；复习时重点掌握 B 树、B+ 树为什么适合外存，以及二者的节点内容差别。

索引基础和倒排索引

• 输入顺序文件按记录进入系统顺序存储，类似未排序线性表，不支持高效检索。
• 主码是每条记录唯一标识；辅码可重复，大多数检索通过辅码索引完成。
• 索引把关键码和记录位置关联成 $(key,pointer)$ 对。
• 一个主文件可有多个索引文件，每个索引文件支持一个关键码字段，因此无需重排主文件。
• 稠密索引：每个记录建立一个索引项，主文件记录不需要重排。
• 稀疏索引：一组记录建立一个索引项，组内通常按关键字排序，索引指向该组记录起始位置。
• 线性索引按关键字排序，局限是索引太大时需放磁盘，访问效率下降且更新困难。
• 二级线性索引对一级索引再建索引，二级索引可放内存，减少访问一级索引次数。
• 倒排索引根据属性值或文本词项建立到记录/文本位置的指针列表。
• 数据库倒排索引要求属性值离散，存储代价大、更新困难。
• 文本索引包括：
  • Word Index：建立关键词到文本位置的结构，需分词、去除无用词、处理同义词。
  • Full-text Index：维护子串到文本位置的结构，支持任意文本检索但开销大。

B 树

• 静态索引在文件创建或初始装入时生成，运行中不改变；动态索引支持运行时插入删除并保持检索效率。
• B 树是高度平衡的多分树，每个节点包含记录和索引信息，适合减少磁盘访问。
• m 阶 B 树：
  • 根至少两个儿子，除非根也是叶子。
  • 除根和叶节点外，其他节点至少 $\lceil m/2\rceil$ 个儿子。
  • 所有叶子在同一层。
  • k 个儿子的节点恰有 k-1 个关键码。
• B 树节点存三类值：关键字、指向儿子的指针、关键码对应记录位置的指针。
• 查找从根开始，在节点关键字中查找，若未找到则进入关键字区间对应儿子，直到找到或遇到空指针。
• 查找效率约为： $$O(\log_{\frac m2}n)$$ 更具体地： $$k\leq1+\log_{\lceil m/2\rceil}\frac{n+1}{2}$$
• 插入先找到叶子并插入关键码；若关键码数达到 $m$，则对半分裂并把中间关键字插入父节点，必要时递归到根，根分裂会使树高加一。
• 平均分裂次数： $$s=\frac{p-1}{n}\leq\frac{1}{\lceil m/2\rceil-1}$$
• 删除若目标不在叶子，可与叶子后继交换；删除后若关键码过少，则向兄弟借关键码或与兄弟及父节点分隔关键码合并，必要时递归到根。

B+ 树与位图索引

• B+ 树所有关键字放在叶子节点。
• 内部节点若有 k 个儿子，就记录 k 个值，表示儿子关键字中的最大值。
• 叶子链接后可看作所有记录的有序序列，因此支持区间查询。
• 非标准 B+ 树可让叶节点阶数与内部节点不同，并用儿子的最小关键字作为分隔值。
• B+ 树节点只存关键字和儿子指针，叶子中指针指向记录。
• 若磁盘页大小为 $k$，关键字和指针大小为 $s$，B 树最大阶约为 $k/(3s)$，B+ 树最大阶约为 $k/(2s)$；B+ 树阶更大、树更矮，因此效率更好。
• B 树局限：
  • 唯一值较少的字段价值不大。
  • 数据仓库中构造和维护索引代价高。
  • 对复杂查询无能为力。
• 位图索引对一个属性的一个取值建立位向量，表示不同记录是否具有该值；特征文件记录一个属性所有值的位向量。按列存储，更适合某些数据仓库查询。

其他数据结构与平衡搜索树

本章是对前面结构的扩展：多维数组和稀疏矩阵关注存储压缩，广义表表示嵌套关系，Trie 适合字符串集合，AVL/红黑树/Splay 则从不同角度维持搜索树效率。预习时先把每种结构的应用场景记住；复习时重点掌握 AVL、红黑树和 Splay 的平衡维护差异。

多维数组、稀疏矩阵、广义表和存储管理

• 多维数组可按行优先或列优先存储；常规编程语言多用行优先，Matlab 等使用列优先。
• 稀疏因子： $$\delta=\frac{t}{mn}$$ 其中 $t$ 是非零元素数；若 $\delta<0.05$，称为稀疏矩阵。
• 稀疏矩阵可用三元组 $(i,j,a_{ij})$ 表示。
• 十字链表用行链表和列链表串联，每个非零点有两个指针，便于访问整行或整列。
• 广义表允许元素本身也是表；单独元素为原子，表元素为子表。
• 广义表深度是把元素和括号展开后的最大括号层数。
• 广义表操作：
  • head：取第一个元素。
  • tail：去掉第一个元素后的表。
• 纯表、可重入表、循环表分别对应从树形结构到图形引用关系的不同复杂度。
• 自己实现内存管理可避免频繁系统调用；可用单链表栈维护空闲空间，new 弹栈顶，delete 插回栈顶。
• malloc/free 策略包括首次适配、最佳适配、最差适配。
• 失败处理包括存储压缩和无用单元收集。

Trie 和后缀树

• 字典树（Trie）是结构与输入顺序无关的搜索树。
• 插入时沿字符路径建节点，用 * 表示该路径构成一个词。
• 可去掉叶节点 * 子节点压缩树；Patricia 结构进一步合并只有一个儿子的节点。
• 单次插入/查找复杂度只与 key 长度有关，与树规模无关；查找命中通常效率高。
• 对 $N$ 个随机 key 的字典树，大量查找失败平均访问节点数为 $O(\log_R N)$。
• 空间缺点：关键词多、长度长、字符集大时空间开销可能很高。
• 后缀树相关数组：sa[i] 表示第 $i$ 小后缀的起点，LCP[i]=lcp(sa[i],sa[i+1])。

AVL 树

• AVL 树通过旋转维护左右子树深度差不超过 1，保证树高为 $O(\log n)$。
• 平衡因子： $$bf(x)=height(rson)-height(lson)$$
• 单旋是节点与父节点旋转；双旋是节点向上连续旋转两次。
• 插入：
  • 先按搜索树规则插入到叶子。
  • 若某节点平衡变为 0，可终止。
  • 若平衡变为 1/-1，还要继续检查父节点。
  • 若平衡变为 2/-2，分 LL、LR、RL、RR 四类；LL/RR 单旋，LR/RL 双旋。
  • 旋转后三个节点中间值成为根，子树高度不变，因此不必继续检查祖先。
• 删除：
  • 有右子树时用右子树最小节点交换，再删除那个最多一个子树的节点。
  • 删除后平衡变为 1/-1 可终止；变为 0 需继续检查父节点；变为 2/-2 时看未删方向子节点 $b$ 的平衡因子。
  • $bf(b)=0$：单旋，旋转后树高不变，可终止。
  • $bf(b)=bf(a)$：单旋，旋转后树高减小，继续检查祖先。
  • $bf(b)=-bf(a)$：双旋，旋转后树高减小，继续检查祖先。

• 最不平衡 AVL 树也可推出高度复杂度 $O(\log n)$。
• AVL 树比红黑树更平衡、树高更低，但实现更复杂，实践效率可能更低。

红黑树

• 红黑树是平衡扩展二叉树。
• 规则：
  • 根为黑。
  • 扩展节点为黑。
  • 内部节点为红或黑。
  • 红节点的两个儿子必须是黑节点。
  • 从一个节点到任意扩展子孙路径上的黑节点数相同，称为该节点的秩，不包含该节点但包含扩展子孙。
• 扩展节点秩为 0，树的秩是根的秩。
• 节点秩为 $k$ 时，向下路径长度最多 $2k$、最少 $k$；秩为 $k$ 至少有 $2^k-1$ 个内部节点。
• $n$ 个内部节点的红黑树高度至多 $2\log(n+1)+1$。
• 插入：
  • 先插入到叶节点，并扩展两个黑色外部节点。
  • 新节点先标红。
  • 若父节点为红，再看父节点兄弟颜色：黑色则旋转调整，红色则改色并继续检查。

• 删除：
  • 若目标节点有两个内部子树，先与右子树最小节点交换值，着色不变。
  • 若删除红色节点，直接删除，不影响性质。
  • 若删除黑色节点且有红色儿子，把红色儿子改黑并替代它。
  • 若删除黑色节点且无红色儿子，要按兄弟节点颜色和兄弟红儿子情况调整。

• 与 AVL 相比，红黑树旋转次数通常更少；与 Splay 相比，单步复杂度更稳定。
• 红黑树可等价转换为 4 阶 B 树/2-3-4 树：把红色节点提到与父节点同一高度即可。

Splay

• Splay 查询和插入后把目标节点旋到根；删除时把目标节点父节点旋到根。
• 双旋分一字型和之字型；之字型与 AVL 双旋类似，一字型不同。
• 多次操作有均摊复杂度保证，单次操作没有严格保证。
• 若操作 $m\geq n$，复杂度为 $O(m\log n)$。
• 若操作只涉及 $k$ 个点，复杂度为 $O(k\log n+m\log k)$，体现局部性优势。
• 常见插入方式是先插到叶子再 splay；更好的方式是按 $x$ 分裂成两棵树，再分别作为 $x$ 的左右子树。
• 删除可先将 $x$ 旋到根，删除后将左子树最大值旋到根，再接上右子树。
• 半伸展树在一字型双旋中只旋 fa(x)，保留结构调整但失去把确定节点旋到确定位置的能力。

易错点 / 高频考点

• ADT 不规定具体存储实现；顺序、链式、索引、散列是从逻辑结构到物理存储的不同映射。
• 顺序表适合随机访问和静态数据；链表适合频繁插入删除，不能把“链表一定省空间”当结论。
• 循环队列需要额外标记区分满和空，否则头尾相对位置不足以表示 $n+1$ 种状态。
• 后缀表达式遇到运算符时，计算顺序是先弹出的为右操作数，后弹出的为左操作数。
• 二叉树中“完全”和“满”不同；完全二叉树只允许最后一层不满且必须左对齐。
• 二叉搜索树删除有两个儿子的节点时，常用左子树最大值或右子树最小值替代，替代节点最多只有一个儿子。
• 堆是完全二叉树，适合顺序存储；堆不唯一，不能用左右儿子顺序判断唯一结构。
• Dijkstra 不能处理负边；Bellman-Ford 可处理负边并检测源点可达负环；Floyd 是全源最短路。
• 稳定性只关心相同排序码记录的相对顺序，选择排序、堆排序、快速排序通常不稳定。
• 快速排序最坏 $O(n^2)$，平均 $O(n\log n)$；实际常快于归并，原因包括读写次数少和局部性好。
• 比较排序下界只约束基于比较的排序；桶排序和基数排序依赖关键码范围、位数和稳定桶排。
• 外排序重点是 I/O；置换选择排序通过更长顺串减少归并轮数，胜者树/败者树减少 k 路归并比较成本。
• 闭散列删除不能简单清空位置，要用墓碑标记；装载率超过约 0.5 后性能可能明显下降。
• B 树节点同时存关键字、儿子指针和记录指针；B+ 树关键字集中在叶子，更适合范围查询，阶也通常更大。
• AVL 更严格平衡但实现复杂；红黑树旋转较少且单步稳定；Splay 依赖均摊分析和访问局部性。
• 红黑树插入常看“叔节点”颜色；删除常看“兄弟节点”颜色及其红儿子方向。