外排序
- 置换选择排序,顺串长度$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为父节点。
插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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$为左右子树高度差
插入节点
从插入的节点走到根,发现平衡因子$ | 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:数分不挂就填坑…