回溯法
- 给定几个点之间的距离，假设它们共线，求出他们的坐标
- 思路：先考虑距离最大的
- 时间复杂度：假设能够在$\Omicron(1)$求出最大距离，那么时间复杂度为$\Omicron(N^2)$
分治法
- 算时间复杂度：递归树法
- 算时间复杂度：主定理
- 关于主定理的记忆：$a$是divide把问题分成子问题的个数，$b$是子问题的规模，$\Theta (N^k \log^{p} N)$是合并的复杂度
- 需要比较的是$aT(N/b)$项和$\Theta (N^k \log^{p} N)$谁占据主导地位，类似于极限的抓大头原则
- 如果说$aT(N/b)$占据主导地位，那么总的时间复杂度只需要考虑分割的过程，$T = \Omicron(\sum_{h = 0}^{\log_{b}N}a^{\log_{b}N - h}) = \Omicron(N^{\log_{b}a})$，是在背不出就记得分母上的在对数中放在底上，无论哪种情况，都有N的几次方
- 如果说合并$\Theta (N^k \log^{p} N)$占据主导地位，那么总的时间复杂度一定是单次合并的复杂度这个数量级的（合并次数是常数）
- 如果说两者同样重要，仍然是合并的过程更占主导，但是需要补偿给切分的过程一个指数
- 判断主导，比较$a$（分割问题的规模）和$b^k$（合并问题的规模），实在不记得记得后面有个汉堡王就完事了
- 最近点对问题
- 使用一些方法使合并时只需考虑常数个数的点
$T(N) = \Omicron(N)$
动态规划
算了吧
算了吧
贪心算法
算了吧
算了吧
NP完全性
-
P：多项式时间内可以求解的问题
-
NP：多项式时间内可以判定解的正确性的问题
-
NP-Complete：所有NP问题都可以归约到的问题
-
NP-Hard：属于NP-Complete，但不属于NP的问题
-
co-NP: 多项式时间内可以判定解的错误性的问题
-
归约：常用符号$A \leq_q B$，表示经过某种多项式次数的调用求解$B$的算法，可以解出$A$（或者一个等价的定义，通过多项式时间的变换，可以把$A$变换为问题$B$），可以粗浅的理解为不等号指示了问题的难度，如果已知其中一个能或不能在多项式时间内求解，问另一个的状况
-
在这一章的复杂度分析中，我们是按每Bit为单位考虑的
- 可满足性问题SAT
- 给定一个逻辑表达式，是否存在某种赋值让其为真
- 顶点覆盖问题
- 在图中，找到一个最小的顶点集合，使得该集合中的顶点能够覆盖图中的所有边
- Clique（团）问题
- 无向图中找到一个完全子图，其中的每两个顶点都直接相连
- 哈密尔顿回路、哈密尔顿路径问题
- Dominating Set问题
- 在图中，找到一个最小的顶点集合，使得该集合中的每个顶点或者与之相邻的顶点都在集合中
- Independent Set问题
- 在图中，找到一个最大的顶点集合，使得该集合中的任意两个顶点都没有边连接
- 0-1背包问题或者划分问题
- 在一个集合中寻找一个子集，让子集元素之和等于二分之一全集元素之和
- 旅行商问题
- 给定一系列城市和城市间的距离，求解遍历每个城市的最短距离的回路
- 装箱问题（NP-HARD）
- 给定n个物品，能否用k个箱子装下
近似算法
- 近似比$\rho = \max {OPT/C, C/OPT }$，$C$为解，$OPT$为最优解。近似比恒大于1，我们的目标是让近似比经历接近1。
- PTAS：poly-Time Approx Scheme，多项式时间近似算法。
- PTAS产生一个近似比为$1 + \epsilon$的解（$\epsilon \gt 0$），同时要求对于问题规模N的时间复杂度随总是多项式时间的，无论$\epsilon$取何值。
- NextFit：第二个能够和第一个装进箱子就装，否则开个新的
- 假设$M$是最优解，NextFit最多用$2M-1$个箱子
- FirstFit：查找之前所有装过东西的箱子，装到第一个能装进去的，没有就开个新的
- 假设$M$是最优解，FirstFit最多用$17M/10$个箱子，可以构造序列让FirstFit使用$17(M - 1)/10$个箱子
- BestFit：查找之前所有装过东西的箱子，装到装进去后最满的那个箱子里，没有就开个新的
- 时间复杂度$T(N) = \Omicron (N \log N)$
- 假设$M$是最优解，BestFit最多用$17(M)/10$个箱子
- 不存在近似比优于$1.6666..$的在线算法
- 离线算法：对所有物品排个序，然后套上面的三个方案
- FirstFitDecreasing：假设$M$是最优解，最多用$11M/9 + 6/9$个箱子，能够构造序列恰好使用这么多箱子
- 你可以选择装一个物品的一定比例，而非全部装入，还是求背包内的总价值最大的装法
- 贪心算法：近似比为2
- 在一个点集中，找k个点，使得所有点到这些点的最小距离组成的集合中的最大值最小。
- 贪心算法：近似比为2，没有近似比更小的算法
局部搜索
- 邻域的概念：由状态$S$作微小改变可以转为的任意一个状态$S^\prime$的集合，符号表记为$N(S)$
- 常用的局部搜索框架
S = 某个可行解
while (1)
{
S' = findBest(N(S))
if (f(S') > f(S))
{
maxF = f(S');
S = S'
}
else break; // 不能找到更好的解了 结束
}
- 这是常常用于解决求NP问题的近似解的方法
- 邻域:=任意交换两个边的连接关系
A --- B A \ / B => X C --- D C / \ D - 算法示例：https://blog.csdn.net/qx3501332/article/details/105546250
- 在这个问题中，为了解决可能遇到的进入死胡同问题，再找不到更好的解的条件下，以概率$e^{\frac{-\Delta cost}{kT}}$跳到另一个点，这个数字似乎与热力学规律有关。（模拟退火）
- 邻域:=删去一个点
- 边是好的：两个顶点的值乘以权重是负数
- 点是好的：和他相连的所有边，好边权重和大于坏边权重和
- 问题：求一种对点的赋值，使得所有点是好的
- 邻域:=选择一条不好的边，选一个顶点取反（Stabe-filpping Algrorithm）
- 其实是最大化好边权重和的过程，当取反一个顶点的时候，必然有原先和他相连的好边变坏边，坏边变好边
- 可以证明，最大迭代次数等于边的权值的绝对值之和
- 不一定能够收敛到全局最优
- 问题：在一个图中，每一个边都有一个正的权值，将图划分为两个集合，使得跨越两个集合的边的权值最大
- 这个问题可以转化为霍普菲尔德神经网络问题，点分别赋值为-1或者1（集合A和集合B），因为都是最大化好边权重和。
- 近似比：2，即局部最优解大于等于全局最优解的一半
随机化算法
- 随机化算法：在算法中引入随机函数，且随机函数的返回值影响算法的执行流程或执行结果
- 可以将确定性算法视作随机化算法的特例——一个高概率产生正确答案的高效随机化算法
- 离散变量的期望：$E[X] = \sum_{j = 0}^{+ \infty} j \cdot \Pr[X = j]$
- 面试一个人的成本远小于雇佣一个人的成本
- 问题：从N个求职者中，雇佣M个人（并不是一个固定的要求值），使得总雇佣开销最小，同时使得受雇者的质量尽量高
- 解决方案1：总是雇佣目前质量最高的求职者，直到雇佣了M个人为止
- 最差情况：求职者按质量升序排列
- 解决方案2（随机化算法）
- 基本假设：雇佣者按质量随机排列（每个分割下，第二组的第一个人都有等概率是第一组加上他组成的集合中，质量最好的）
- 令$X$为雇佣的人数，$X_i$为第$i$个求职者的受雇情况，用0表示不雇用，1表示雇用
-
$E[X_j] = Pr[j_ is_ hired] = 1 / j$ ，使用解决方案1 - 那么，$X = \sum_{j = 1}^{+ \infty}X_j$，雇佣人数的期望$E[X] = E[\sum_{j = 1}^{+ \infty}X_j] = \sum_{j = 1}^{+ \infty}E[X_j] = \sum_{j = 1}^{+ \infty} 1 / j = \ln N + O(1)$
- 算法：将所有求职者按随机顺序重排（通过给每个求职者一个$[0, N^3)$的随机整数后排序得到），再使用上面的解决方案1
- 解决方案3（使用随机化算法的在线算法）
- 取前k个求职者作为样本，不雇用他们，但统计他们之中的最高质量。从第k+1个人起，只要有人质量大于最高质量，就雇用他，然后结束算法（只雇用一个人，$M = 1$）。
- 问题：我们雇用到最高质量的求职者的概率是多少？
- 定义：事件$S_i$，第$i$个求职者的是质量最高的求职者，并且被我们雇用。$S_i = {\textrm{质量最高的求职者是第i个} } \cap { \textrm{第k+1到第i-1个求职者没有被雇佣}}$
- 定义：事件$S$，质量最高的求职者被我们雇用。$\Pr [S] = \sum_{i = k + 1}^{N}\Pr [S_i] = \sum_{i = k + 1}^{N}\frac{k}{N(i - 1)}$
- 上面的级数可以通过柯西准则夹逼，得到$\frac{k}{N}\ln \frac{N}{k} \leq \Pr [S] \leq \frac{k}{N}\ln \frac{N - 1}{k - 1}$
- 快速排序：平均运行时间$\Theta(N \log N)$，最差运行时间$\Theta(N^2)$
- 修改快速排序中的pivot：将集合分为两部分的元素，每一部分至少含有1/4数量的元素。
- 实际上，可以证明，即使我们的pivot是完全随机选取的，仍然可以有$E[T(N)] = 2(N + 1)(\ln N + \gamma + \Omicron(\frac{1}{N})) - 2n = \Theta(N\log N)$
并行算法
- Parallel Random Access Machine （PRAM）：可以同时执行指令的机器。
- 下面的伪代码语句常常用来表示循环体是n个处理单元并行执行的
for Pi, 1 <= i <= n pardo // do something, e.g. A[i] = B[i] - 可能会导致访问冲突，这是体系结构课程的内容。
- 下面的伪代码语句常常用来表示循环体是n个处理单元并行执行的
-
$T(N)$ ：时间复杂度，和其他语境下含义一致。一个并行算法最差的情况下（单线程）消耗的时间。 -
$W(N)$ ：Work load，总的运算数量 -
$p$ ：处理单元个数- 存在以下渐进关系需要注意：
- 算法需要的处理器单元数量$P(N) = W(N)/T(N)$
- 算法的时间为$W(N)/p \neq T(N)$，对于任意满足$p \leq W(N)/T(N)$的处理单元数量
- 对于任意的q，我们都可以将算法的时间消耗写成$W(N)/p + T(N)$，尽管这个估计放缩的有些大
- Input:
$A(1), A(2), …, A(n)$ - Output:
$A(1) + A(2) + … +A(n)$ - 思路：两两相加，然后两两相加，直到只有一个值为止。
- 将数组
A[]中的元素存入数组B[0][]，即B[0][1] = A[1], B[0][2] = A[2], ... -
B[0][]中相邻元素两两相加，结果存入B[1][]，并保持原有的前后顺序 - 迭代上述步骤
- 将数组
- 伪代码
for Pi , 1 <= i <= n pardo // <- B(0, i) = A( i ) for h = 1 to log n do if i <= n/2h B(h, i) = B(h-1, 2i-1) + B(h-1, 2i) else stay idle for i = 1: output B(log n, 1); for i > 1: stay idle // <-- PPT上说这个表示方法没有揭示算法如何在不同数量的处理器的PRAM上运行
- 用Work-Depth模型表示
for Pi , 1 <= i <= n pardo B(0, i) = A( i ) for h = 1 to log n for Pi, 1 <= i <= n/2h pardo B(h, i) = B(h-1, 2i-1) + B(h-1, 2i) for i = 1 pardo output B(log n, 1) $T(N) = \log N + 2$ $W(N) = N + \sum_{i = 1}^{\log N} n/2^{i} + 1 = 2n$
- Input:
$A(1), A(2), …, A(n)$ - Output:
$\sum_{i = 1}^{1} A(i), \sum_{i = 1}^{2} A(i), \sum_{i = 1}^{3} A(i), ...$ - 使用平衡二叉树，自叶
B[0][1], B[0][2]向上建树（就像上个例子中的一样），然后自根节点向下做一些操作（每个结点的值传递给它的右儿子，而左儿子的指决定于它本身和与其父亲最接近的叔叔的和），这些操作最终使得这棵树的最深一层分别是我们要求的前缀和C[0][1], C[0][2], ...- https://blog.csdn.net/lavorange/article/details/39103609
-
B[][]由叶节点向树根构造（从下往上），而C[][]由树根向叶节点构造 - 可以画一个八个元素的递增序列
A[] = {1, 2, 3, ..., 8}体会一下这个过程
$T(N) = \Omicron(\log N)$ $W(N) = \Omicron(N)$
- Input: 两个递增序列
A[]，B[]，规模分别为n和m - Output: 合并
A[],B[]后得到的递增序列C[] - 为了简化这个问题，我们假设：
-
A[]，B[]中的元素各不相同 $n = m$ -
$n$ 与$n/\log n$均为整数 - 数组下标从1开始
-
- 算法：对数组元素排位（Ranking）
-
Rank(j, A) = i表示B[j] < A[i + 1] < B[j + 1]，表示B中第j和第j+1个元素中可以插入A中的第i+1个元素 - 极端情况：
Rank(j, A) = 0表示B[j] < A[1] - 极端情况：
Rank(j, n) = 0表示B[j] > A[n] - 对于
Rank(i ,B)，以同样法则计算 - 并行地，令
C[i + Rank(i, B)] = A[i]; C[i + Rank(i, A)] = B[i]
-
$W(N)= \Omicron(N)$ $T(N) = \Omicron(\log N)$
- Input:
$A(1), A(2), …, A(n)$ - Output:
$\max { A(n)}$ - 算法：在求和问题中，将加法运算修改为求最大值运算
-
$T(N) = O(\log N)$ ，与分治法相比没有特别大的优势 $W(N) = O(N)$ - 另一种算法直接并行地比较，虽然有可能造成访问冲突，$T(N) = \Omicron(1)$，$W(N) = \Omicron(N^2)$
- 假设：$h = \log \log n$是一个整数
- 按$\sqrt{N}$的大小切分原数组
- 对每一组求最大值，每一组的开销为$T(\sqrt{N}), W(\sqrt{N})$，对于这些最大值，再求一次最大值。求最大值使用上面提到的直接并行比较的方法，每一个组的为开销$T(\sqrt{N}) = \Omicron(1), W(\sqrt{N}) = \Omicron(N)$
- 那么，总的开销为$T(N) \leq T(\sqrt{N}) + c_1$，$W(N) \leq W(\sqrt{N}) + c_2$，解这个方程，得到$T(N) = \Omicron(\log \log N)$，$W(N) = \Omicron(N \log \log N)$
- 从这个结论出发，我们可以一开始就以$h = \log \log n$的大小切分原数组，这能将工作量优化到$W(N) = \Omicron(N)$
- 在数组A中，随机地选取一个大小为$n^{7/8}$的块B1（这一步很重要）
- 将B1按$n^{1/8}$的大小切分，能够分成$n^{3/4}$个块
- 在这些块中，选取最大值组成下一个大小为$n^{3/4}$的块B2
- 将B2按$n^{1/4}$的大小切分，能够分成$n^{1/2}$个块
- 在这些块中，选取最大值组成下一个大小为$n^{1/2}$的块B3
- B3不需要进一步切分了，直接取最大值，返回结果
- 每一步取最大值都是$T = \Omicron(1)$的，$W$为规模的二次方量级。最终我们得到一个$T(N) = \Omicron(1)$，$W(N) = \Omicron(N)$的近似算法
外部排序
- 问题：当需要被排序的数组足够大而不能够完整地放入内存时，如何对这个数组进行排序？
- 想法：将待排序数组分块排序后，进行归并
- K路归并（K-way merge）：将N个块合并为一块，并保持全序性
- run：实际上就是我们有序序列（排序后的块），每次进行K路归并，我们将n个run合并为1个run
- pass：将kc个run合并成c个run的过程
- tape：顺序读写介质，我们从这里加载数据进入内存
- 内排序中的归并排序：就是我们在数据结构基础的课程上提到的2路（不限于2路）归并排序，自整体从上往下按1/k切分
- 外排序中的归并排序：由于内存大小限制，我们的切分基本单元是固定的大小，我们利用这些排序的基本单元自部分从下往上按k合并
- 假设：
- 我们无限个tape用于存储数据
- 内存大小只允许我们存放3个数据，即$M = 3$
- 待排序的数组：
T1: 81 94 11, 96 12 35, 17 99 28, 58 41 75, 15$N = 13$ - 目标：向某一个tape输出我们的排序结果
- (pass1)依次读取
T1中的每一段数据（其实是按内存上限读取，这里已经分好段了），对他们进行内排序（在内存中进行排序） - (pass1)将这些排序后的段平分地写入到
T2与T3，注意这里的T1为了方便理解，我们将它看作是空的tapeT1: NULL T2: 11 81 94, 17 28 99, 15 T3: 12 35 96, 41 58 75 - (pass2)依次取
T2与T3的第一个、第二个、第三个、...run进行merge，选取两个闲置的tape（在这里是T1和T4），平分地写入这两个tape（即先将第一个大小为6的run写入T1，然后将第二个大小为6的run写入T4，然后将第三个大小为6的run写入T1，...）T1: 11 12 35 81 94 96, 15 T2: NULL T3: NULL T4: 17 28 41 58 75 99 - (pass3)依次取
T1与T4的第一个、第二个、第三个、...run进行merge，选取两个闲置的tape（在这里是T2和T3），平分地写入这两个tape（即先将第一个大小为12的run写入T2，然后将第二个大小为12的run写入T3，然后将第三个大小为12的run写入T2，...）T1: NULL T2: 11 12 17 28 35 41 58 75 81 94 96 99 T3: 15 T4: NULL - (pass4)依次取
T2与T3的第一个、第二个、第三个、...run进行merge，选取两个闲置的tape（在这里是T1和T4），平分地写入这两个tape（即先将第一个大小为12的run写入T1，然后将第二个大小为12的run写入T4，然后将第三个大小为12的run写入T1，...）实际上，从pass2开始的过程可以视作是迭代的。当只剩下一个tape中存在数据，排序结束T1: 11 12 15 17 28 35 41 58 75 81 94 96 99 T2: NULL T3: NULL T4: NULL
- merge的过程：不考虑时间复杂度，我们直接顺序的读取两个tape，最初的指针位于数组头部，我们选择两个元素中较小的，将其输出到输出的目的tape，然后移动指向这个元素的指针指向后一个元素
-
#run：用于描述某一个tape上，run的个数，例如在上一个例子中，pass1时，tapeT1的#run = 5- 在两路归并的条件下，每一次merge，都会使得某两条tape的
#run减1，某一条异于前面两条的tape的#run加1
- 在两路归并的条件下，每一次merge，都会使得某两条tape的
-
max(#run)：某一个状态下（例如pass1时），所有tape的#run的最大值，例如在上一个例子中，pass1时max(#run) = 5- 每一次pass都能够将
max(#run)缩小一半，最终算法的终止条件（必要非充分条件）是max(#run) = 1，如果max(#run) = 1并且只有一条tape上存在数据，算法终止，排序结束
- 每一次pass都能够将
-
total(#run)：所有tape的#run之和- 在两路归并的条件下，每一个pass都会令
total(#run)缩小为原先的1/2
- 在两路归并的条件下，每一个pass都会令
-
#pass：排序过程中，总的pass数量- 经过上面的分析可以得知，k路归并满足$#pass = 1 + \lceil \log_k (N/M) \rceil$，其中$N$为数据量，$M$为内存能够一次处理的数据量
- 替换选择算法：减少pass1中的初始run个数，这就意味着它们的初始长度可以不是$M$
- 其思路是：在对初始run进行排序时，我们使用选择排序每次能够选出当前的最小值，那么我们可以记录这个最小值为
min，然后将其放入输出tape，并再从输入tape中读取一个元素进来，只要我们选择排序选择的最小值大于min，就输出，并更新min为输出的元素的值，直到我们选不出任何一个元素，我们就得到了第一个run，然后重复以上过程，得到所有run
- 其思路是：在对初始run进行排序时，我们使用选择排序每次能够选出当前的最小值，那么我们可以记录这个最小值为
- 在上面的例子中，k路归并外部排序需要
2k个tape，这不利于我们暴力地增加k来减少pass的数量 - 观察：在上面的例子中，例如15这个run，做的只是从一个tape移动到另一个tape上，直到最后一轮才被merge，我们不如直接摆烂不移动它
- 解决方案：不再平均地将run分配到tape上
- 例子：两路归并排序，表中列出了每个tape的
#run即run的个数，从上至下，每一行代表一个pass
T1 |
T2 |
T3 |
备注 |
|---|---|---|---|
| 21 | 13 | - | 初始情况 |
| 8 | - | 13 | T1的前13个run和T2的所有run合并，写入T3 |
| - | 8 | 5 | T1的所有run和T2的前8个run合并，写入T2 |
| 5 | 3 | - | T2的前5个run和T3的所有run合并，写入T1 |
| 2 | - | 3 | |
| - | 2 | 1 | |
| 1 | 1 | - | |
| 0 | - | 1 |
- 但这实际上增加了pass的数量
- 我们发现，这些tape上run的个数恰好是二阶斐波那契数列，
0, 1, 1, 2, 3, 5, 8, 13, 21, ...中的项。更加确切的说，如果我们按着pass的倒序从下往上看这个表格，每一行的最大值或者每一行的最小值组成的数列，都恰好组成了斐波那契数列。 - 那么，对于初始两个tape的
#run不是斐波那契数列相邻两项的情况呢？- 如果初始的两个tape的
#run是斐波那契数列相邻两项，那么这个对run的分配方案比其他分配方案所需要的pass是最小的。 - 为了使所需要的pass最小，我们需要尽量使得初始的k个tape是斐波那契数列中的相邻若干项。
- 因此，对于初始k个tape，m个run，我们选择k阶斐波那契数列中大于等于m的第一个项，然后，我们从这一项开始（不包括）往前取k项，作为初始的run分配，对被我们选取的最大项来说，我们还需要修改它的值，减去总run的数量与这一项斐波那契数的差。
- 例如，总共有31个run，4个tape，对于3路归并排序，如何分配每个tape的
#run使得pass最少？ - 三阶斐波那契数列：
0 0 1 1 2 4 7 13 24 44，最接近的项是44，所以run的分配为7, 13, (24 - (44 - 31))
- 例如，总共有31个run，4个tape，对于3路归并排序，如何分配每个tape的
- 需要注意，在这种情况下，每一个pass中，各个tape的
#run的最大值或者最小值其中之一组成被以下递归式定义的数列。
- 如果初始的两个tape的
- 更加一般地，对于k路归并外部排序，我们有这样的规律（前提是初始的k个tape的
#run是下面提到的数列中的相邻两项）：每一个pass中，各个tape的#run的最大值组成被以下递归式定义的数列，最小值亦然。其中，k是一个上标，表示这是k阶斐波那契数列中的项。
就像名字一样。
我们每次总是选取规模最小的两个run进行合并，这将有助于减少我们的读I/O请求。因为霍夫曼树的WPL是最小的。
当归并的路数
添加虚段的目的是使得霍夫曼树中只有度为 0 或 k 的节点，计算添加的虚段个数，根据以下的性质列方程：
- 所有的归并段在构建霍夫曼树时，都会位于叶节点，即度为 0 的节点；
- 对于只有度为 0 或 k 的节点的树，总节点数
$N = n_k + n_0$ ，其中$n_k$ 是度为 k 的节点数，$n_0$ 是度为 0 的节点数； - 通过数儿子的方法，总节点数
$N = k \cdot n_k + 1$ ； - 联立上下两个方程，解得
$\displaystyle n_k = \frac{n_0 - 1}{k - 1}$ ； - 上面的方程需要在整数域中有解，因此
$n_0 - 1$ 必须是$k - 1$ 的倍数； - 补充虚段，使得总归并段的数量满足
$\equiv 1 \mod (k - 1)$ 。
其实数据结构部分比较重要，一个是因为都是选择或者判断，搞清楚插入删除的过程和几个基本结论（例如树形数据结构节点数与树高的关系、插入删除查找的时间复杂度）基本上就能混到分，第二个是比算法分析好搞懂，除了摊还分析的部分比较复杂。
面向卷面四十分复习的话只需要把后面每一章的例子看一看，了解一下思想就差不多了，要算的难题不是考试周复习两天能学会的
对18-19学年起，至22-23学年的历年卷观察得到以下结论：对于选择题来说，19年T多，20年F多，21年T多，22年F多，23年T多
而且一般情况下并不是均匀地分布的，例如今年（22-23学年）的13道选择题中，选F的仅有5道，全选T的正确率比大部分卷面60分左右的同学还要高
以下是 ADS 课程要求与统考计算机考试范围重合的一些数据结构，以供参考。
BST 中序遍历将直接得出排序结果。BST 维护偏序关系，左子树 < 根节点 < 右子树。
- 查找：从根节点逐层向下查找
- 插入：查找（如果插入的元素和树中已有的元素是不同的，那么查找必然失败），直到叶节点。插入新的节点，成为这个叶节点的左儿子或右儿子。
- 删除：有三种情况
- 删除的节点没有左子树：直接使用右子树替代被删除的节点；
- 删除的节点没有右子树：直接使用左子树替代被删除的节点；
- 删除的节点有左右子树：找到左子树中最大的节点或右子树中最小的节点，替代被删除的节点。这个被用于替代的节点必然是 a 或 b 的情况。
左右子树的高度差不超过 1，在插入或删除时需要调整二叉树以满足这一性质。
- 插入：使用 BST 的插入方式插入，如果发生不平衡，从叶到根，调整不平衡的子树
- 删除：使用 BST 的删除方式删除，如果发生不平衡，从叶到根，调整不平衡的子树
- 调整不平衡的子树：可以归纳到四种情况：LL、LR、RR、RL（自己画一画就能推导出）。每一种旋转方式，旋转后得到的二叉树满足 AVL 性质，并且中序遍历结果不变。
- 深度为
$h$ 的 AVL 树，最少节点数量满足$F(h) = F(h-1) + F(h-2) + 1$ ，其中$F(0) = F(1) = 1$ ，最多节点数量是满二叉树的情况。
- 红黑树是满足以下五条性质的 BST：
- 每个节点要么是黑色的，要么是红色的；
- 根节点是黑色的；
- 叶节点是黑色的；
- 每个叶节点，黑高相等；
- 不存在两个相邻的红色节点。
- 为了方便起见，我们为每个有值的节点，使用黑色的 NIL 节点补充其缺失的子节点。
- 插入：
- 插入的节点是红色的；
- 判定插入节点的父节点：
- 如果插入节点的父节点是黑色的，OK；
- 如果插入节点的父节点是红色的，判定其叔节点：
- 红叔叔：反转父代、爷代的颜色
- 黑叔叔：将
n、n.p、n.p.p调整为高为 2 情况，重新染色使得这个子树根节点是黑色，子节点是红色。（黑叔叔意味着调整n、n.p、n.p.p不影响黑高）
- 如果调整后，整棵树的根节点是红色的，将根节点染黑；
- 上面的过程从叶到根，逐层向上调整。
- 删除：算了吧。
- 从根到叶节点的最大长度不大于最小长度的两倍（红色节点不相连、最短为全黑）
- 有
$n$ 个节点的红黑树的高度不超过$2 \log(n + 1)$ （根的黑高至少为$\displaystyle \frac{h}{2}$ ，最极端的情况：所有路径都是全黑的，此时总节点数$n \geq 2^{h/2} - 1$ ）
- 查找：同 BST
- 插入：先查找到要插入的目标位置，如果节点元素
$> m-1$ ，分裂，以中间节点$\text{ceil}(m/2)$ 为界，左侧成为新的左侧节点，右侧成为新的右侧节点，中间元素进入父节点。分裂过程从叶到根，逐层向上调整。 - 删除：先查找到要从中删除的目标位置，如果节点元素
$< \lceil m/2 \rceil - 1$ ，则需要向兄弟节点借一个元素。如果够借，那么借一个节点过来，调整父节点的元素；如果不够借，兄弟节点合并，调整父节点中的元素。删除过程从叶到根，逐层向上调整。 - 优势：减少磁盘 I/O 次数，减少树的高度，提高查找效率。
只有叶节点存储数据，非叶节点只存储索引。
为了实现该目的，节点中每一个元素对应一个指向下一节点的指针，被指向的节点中，所有元素都小于等于该元素，大于等于该元素的前一个元素。
m 阶 B+ 树，每一个非根节点中含有的元素数量
阶直接决定分叉数的范围，不论是 B 树还是 B+ 树。
无论查找成功与否，都需要遍历到叶节点。