数算A期末复习

外排序

  • 置换选择排序,顺串长度$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$为左右子树高度差

插入节点

从插入的节点走到根,发现平衡因子$|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:数分不挂就填坑…

Show Comments