外排序

置换选择排序，顺串长度$2M$
2路归并
k路归并
最佳归并树（哈夫曼树）
胜者树
败者树
区分胜者树和败者树的定义和 节点个数

散列

编号	冲突解决策略	成功检索	不成功检索并插入
1	开散列法	$1+\frac{\alpha}{2}$	$\alpha + e^{-\alpha}$
2	闭散列-双散列法	$\frac{1}{\alpha} \ln \frac{1}{1-\alpha}$	$\frac{1}{1-\alpha}$
3	闭散列-线性探查法	$\frac{1}{2}(1+\frac{1}{1-\alpha})$	$\frac{1}{2}(1+\frac{1}{(1-\alpha)^2})$

索引

主码
数据库中的每条记录的唯一标识
辅码
数据库中可出现重复值的码（属性）
二级索引
针对一级索引占用磁盘块过多设计。
假设一级索引占用了x个磁盘块，则二级索引内有x条记录。
倒排索引
针对属性值的索引
基于属性的倒排
基于正文文件的倒排

动态索引

关键码个数

B树是$[\lceil m/2\rceil - 1,m-1]$
B+树是$[\lceil m/2\rceil,m]$

B树

m阶B树

树中每个节点至多有$m$个子节点；
根节点至少有$2$棵子树，其它非叶节点至少有$\lceil m/2\rceil$棵子树；
每个节点有$\lceil m/2\rceil - 1$到$m - 1$个关键码。

节点的一般形式：j个关键码，j+1个指针：

$ [P_0, K_1, P_1, \dots , P_{j-1}, K_j, P_j] $

$K_i$是关键码，$P_i$是指针。

注意：每一个关键码对应一个记录指针域（如下图所示）。

最多$h+1$次访外读盘。

B树插入

核心思想：以提取中位数到父亲节点的方式分裂节点。

最多$h$次读盘，$2h+1$次写盘：共$3h+1$次访外。

B树删除

删除的关键码不在叶节点层：与后继（前驱）交换位置。

下溢出处理の流：左（右）邻居→父节点→此节点。

B+树

每个节点至少$\lceil m/2\rceil$有个子节点（关键码）（根除外），至多有$m$个子节点（关键码）；
根节点至少有$2$个子节点。

节点

（根为空或独根除外）。

树高：$k \le 1 + \log _{\lceil \frac{m}{2} \rceil} (\frac{N+1}{2})$。

B+树插入

分裂为左右子树，然后更新父节点（最大/小关键码）。

B+树删除

下溢出时合并+借节点。
借过来的节点要附带子树。

红黑树

一些标记：u为当前节点，v为兄弟节点，fa为父节点。

插入

st=>start: 插入红色新节点
st2=>operation: “当前节点”为插入的节点
e=>end: 结束
op=>condition: “当前节点”是否红红冲突？
cond=>condition: 叔叔节点是黑色吗？
fbl=>operation: Rotate(fa)
frd1=>operation: 翻转父节点、叔叔节点和祖父节点颜色
frd2=>operation: 　　更新“当前节点”为祖父节点　　

st->st2->op
op(yes)->cond
op(no)->e
cond(yes)->fbl->e
cond(no)->frd1->frd2
frd2(right)->op

删除

真言

同色变色，兄弟变红（可能继续）
异色旋转，根色不变

首先将要删除的节点与后继交换（ 换值不换色 ）。

不出现双黑节点的情况
若待删除节点有一个NULL
若待删除节点为红色且有两个NULL
结束
出现双黑节点的情况
若待删除结点为黑色且有两个NULL
删除此节点，并把该位置上的NULL标记双黑
双黑结点兄弟是红色

将fa与兄弟反色。
Rotate(v)。
转化为兄弟为黑色的情况↓
双黑节点兄弟是黑色
v有两个黑色子节点

兄弟节点变为红色，父亲节点+1黑，若父亲出现双黑继续调整
v有红色子节点
红色子节点与兄弟节点位于左右同侧“一字型”

兄弟节点继承父亲颜色，父节点与红色侄子变黑
Rotate(v)
红色子节点与兄弟节点位于左右异侧“之字型”

设红色侄子为c，c继承父亲颜色，父亲染黑
Rotate(c), Rotate(c)
结束

广义表

( L1:( a, b ), ( L1, c, L2: (d)), ( L2, e, L3: (f, g ) ), L3 )

Head和Tail操作

对于广义表$L=(x_0,x_1,\dots,x_{n-1})$，$\text{Head}(L)=x_0$，$\text{Tail}(L)=(x_1,x_2,\dots,x_{n-1})$。

最佳BST树

结点等概率访问

构造方法：$E=I+2n$，其中$I$为内部路径长度。

结点不等概率访问

成功检索
比较的次数就是关键码所在的层数加1（根为第0层）
不成功检索
比较次数就等于被检索关键码所属的那个外部结点的层数
构造方法
注意到中序遍历结果为“成功-不成功-成功”交错的形式，最佳BST树子树一定是最佳BST树，因此可以考虑 区间DP 。

AVL树

平衡因子

定义平衡因子$a$为左右子树高度差

插入节点

从插入的节点走到根，发现平衡因子$

> 1$的节点u，则考虑是怎么走到u的：

假设是$u’’ \rightarrow u’ \rightarrow u$。若$u,u’,u’‘$形成了：

zig-zig
$\text{Rotate}(u’)$
zig-zag
$\text{Rotate}(u’’), \text{Rotate}(u’’)$

挖坑

比B树“牛”（或者说目的性更强）一点点的数据结构：

维基百科上并没有中文词条，比较难啃，考完试有时间看。

考完试还有最大团的大作业：『EWLS: A New Local Search for Minimum Vertex Cover』。

立个flag：数分不挂就填坑…

数算A期末复习

外排序

散列

索引