Hashing Table

• 哈希表/散列表：可根据哈希值直接访问的数据结构

• 原理：以哈希值做为地址，缩小搜索空间、提高查找效率

  • 使用哈希函数为每个键计算哈希值，得到位于 $0, \cdots, m-1$之间整数
  • 按照哈希值把键分布在$H[0, \cdots, m-1]$哈希表中
  • 查找匹配键时，以查找键哈希值作为起点在哈希表中 搜索

• 应选择合适的哈希函数、哈希表长度，尽量把键尽量均分在 哈希表中

  • 哈希函数$hash$：参见math_algebra/#todo
    • 对闭散列：减少冲突
    • 对开散列：避免数据集中
  • 散列表长度$m$：常为质数（方便双散列）

Load Factor

负载因子：$\alpha = \frac {noempty} {m}$

• $m$：哈希表中slots数量（长度）（哈希桶数量）
• $noempty$：非空数量

• 闭散列：负载因子反映哈希表冲突可能性、查找效率

  • 负载因子过小：冲突可能性小，查找效率高，但浪费空间
  • 负载因子过大：冲突可能性大，查找效率低，空间利用率高
  • 负载因子取值最大为1
  • 应适当平衡负载因子，负载因子接近1时重散列，避免冲突 过多影响查找效率

  • Java中HashMap初始负载值为0.75

• 开散列：负载因子反映查找效率

  • 但应该无法反映冲突可能性（也无必要）
    • 开散列往往被用于应对大规模数据，冲突总是存在
    • 查找效率更多取决于数据（哈希值）偏倚程度
  • 负载因子可以大于1

应用

• 字典/映射实现：cs_algorithm/data_structure/set

Open Addressing

闭散列/开放寻址：所有键存储在散列表本身中，不扩展存储空间

• 哈希表$m$至少要和哈希键数量$n$一样大

• 冲突问题解决：根据一定规则计算下个地址

• cluster：聚合，散列表接近满时，一序列连续单元格被占据

  • 线性探查性能恶化，操作效率降低
  • 聚合越来的越大时，新元素插入聚类可能性增加
  • 聚合可能被新插入元素连接，导致更大程度聚合

增量类型

增量类型：碰撞发生后，根据一定规则对原哈希值修正

• $d_i = i$：linear probing，线性探查
• $d_i = i^2, -i^2$：quadratic probing，二次探查
• $d_i = 伪随机数$：伪随机探查
• $d_i = i hash_2(K), i=0,1,2,\cdots$：double hashing* ，再散列法

• 再散列法说明：为保证哈希表中每个位置被探查，增量$s(K)$ 必须互质
  • $m$为质数时自动满足
  • 文献推荐：$s(K) = m - 2 - K mod (m-2)$
  • 对较小散列：$s(K) = 8 - (K mod 8)$
  • 对较大散列：$s(K) = K mod 97 + 1$

操作

• 插入：依次检查哈希值$h(K)$、探查目标序列，直至找到空 单元格放置键

• 查找：给定查找键K，计算哈希值$h(K)$、探查目标序列，比较 K和单元格中键值

  • 若查找到匹配键，查找成功
  • 遇到空单元格，查找失败

• 删除：延迟删除，用特殊符号标记曾经被占用过、现被删除 的位置

  • 不能直接删除，否则的中间出现空单元格，影响查找正确性

算法效率

• 成功查找访问次数： $S \approx \frac 1 2 (1+\frac 1 {(1-\alpha)})$

• 失败查找访问次数： $U \approx \frac 1 2 [1+\frac 1 {(1-\alpha)^2}]$

• 简化版本近似结论（散列规模越大，近似结论越正确）
• 无法避免散列表趋满时性能恶化
• 再哈希法数学分析困难，经验表明优秀的散列函数（两个）， 性能较线性探查好

Multi Hashing

多重哈希：使用一组哈希函数$h_0,\cdots,h_n$依次计算哈希值， 确定插入、查找地址

• 类似增量类型方法，仅各次地址独立使用哈希函数计算

增大空间

Rehashing

重散列：扫描当前表，将所有键重新放置在更大的表中

• 散列表趋满时唯一解决办法

Overflow Area

建立公共溢出区：将哈希表分为基本表、溢出表两部分

• 将发生冲突的元素都放入溢出区
• 基本表中可以考虑为为每个哈希值设置多个slots
  • 即基本表直接存储哈希桶

Chaining

开散列/分离链：哈希表作为目录，使用额外数据空间组织哈希键

拉链法/分桶法

拉链法/分桶法：哈希表作为目录项存储指向hash桶的指针，hash桶 中存储哈希键

• 目录项表：顺序表，连续存储空间

  • 可以通过hash值在常数时间内定位：一般其索引位置就是 hash值
  • 目录项越多，数据分布相对越稀疏、碰撞概率越小、效率 越高

• hash桶：存储具有相同哈希值元素的顺序表

  • 目录项存储chain为顺序表：每个链即为hash桶
  • 目录项存储chain为顺序表链：链中每个顺序表为hash桶
    • 即每个目录项对应多个hash值，链接多个hash桶

操作

• 查找
  • 对查找键K，使用同样散列函数计算键散的函数值$h(K)$
  • 遍历相应单元格附着链表，查找是否存在键K
• 插入：计算键对应桶，在链表尾部添加键即可
• 删除：查找需要删除的键，从链表中移除即可

算法效率

• 效率取决于链表长度，而链表长度取决于字典、散列表长度 和散列函数质量

  • 成功查找需要检查指针次数$S = 1 + \alpha / 2$
  • 不成功查找需要检查指针次数$U = \alpha$
  • 计算散列函数值是常数时间操作
  • 若n和m大致相等，平均情况下$\in \Theta(1)$

• 算法查找的高效是以额外空间为代价的

Perfect Hashing

完美哈希：采用两级全域哈希，目录项链接独立哈希表的拉链哈希表

• 二级哈希表开头部分存储哈希表元信息

  • $m = n^2$：哈希表槽数，$n$为映射至该槽元素数量 （此时由全域哈希性质：冲突次数期望小于0.5）
  • $a, b$：全域哈希参数

• 复杂度

  • 时间复杂度：最坏情况下查找为$O(1)$
  • 空间复杂度：期望空间为线性 $E(\sum_{i=1}^{m-1} \theta(n_i^2) = \theta(n)$

• 完美哈希没有冲突的概率至少为0.5
• 全域哈希参见math_algebra/hash_funcs

Dynamic Hashing

动态hash：在hash表中元素增加同时，动态调整hash桶数目

• 在原hash表基础上进行动态桶扩展
• 不需要遍历表元素重复执行插入操作
• 开散列法在大规模、在线数据的扩展

多hash表

多hash表：通过建立多个hash表的方式扩展原hash表

• 思想、实现简单
• 占用空间大，数据分布偏斜程度较大时，桶利用率不高

实现

操作时需要考虑多个hash表

• 插入

  • 若存在hash相应桶中存在空闲区域，直接插入
  • 否则分裂，新建hash表，插入元素至空闲区域

• 查找：需要查找所有hash表相应桶才能确定

  • 当表中元素较多时，可以考虑并行执行查找操作

• 删除操作：若删除元素导致某hash表空，可考虑删除该表

可扩展动态hash

可扩展动态hash：只分裂将要溢出的桶，使用目录项作为索引

• 多个目录项可能指向同一个桶
• 分裂时代价较小
  • 翻倍目录项替代翻倍整个hash表
  • 每次只分裂将要溢出桶
  • 只需要进行局部重散列，重分布需要分裂的桶
• 目录指数级增长
  • 数据分布不均时，会使得目录项很大

插入

• D：全局位深度，hash值截断长度，为局部桶深度最大值
• L_i：桶局部深度，等于指向其目录项数目

• 若对应桶存在空闲位，则直接插入

  

• 否则分裂桶：分裂后两桶局部深度加1

  

  • 若分裂桶局部深度不大于全局位深度

    • 创建新桶
    • 重散列原始桶中数据
    • 更新目录项中对应指针：分别指向分裂后桶

  • 若分类桶局部深度大于全局位深度

    • 更新全局位深度
    • 目录项翻倍
    • 创建新桶
    • 重散列原始桶中数据
    • 更新目录项中对应指针
      • （新增）无关目录项仍然指向对应桶
      • 相关目录项指向分别指向分裂后桶

查找

• 计算原始hash值
• 按照全局位深度截断
• 寻找相应目录项，找到对应桶，在桶中进行比较、查找

删除

• 计算原始hash值
• 按照全局位深度截断
• 寻找相应目录项，找到对应桶，在桶中进行比较、删除
  • 若删除后发现桶为空，考虑与其兄弟桶合并，并使局部深度 减1

线性散列

线性散列：按次序分裂桶，保证整个建表过程类似完全二叉树

• 整个哈希表建表过程始终保持为完全二叉树

  • 每次分裂的桶是完全二叉树编号最小的叶子节点
  • 分裂前后桶间均为有序

• 相较于可扩展散列

  • 无需存放数据桶指针的专门目录项，节省空间
  • 能更自然的处理数据桶满的情况
  • 允许更灵活的选择桶分裂时机
  • 但若数据散列后分布不均，则问题可能比可扩散散列严重

• 实现相较而言更复杂

桶分裂

• N：hash表中初始桶数目，应为2的幂次
• d = log_2N：表示桶数目需要位数
• level：分裂轮数，初始值为0，则每轮初始桶数为 $N * 2^{level}$
• Next：下次要发生分裂的桶编号

• 每次同分裂条件可以灵活选择

  • 设置桶填充因子，桶中记录数达到该值时进行分裂
  • 桶满时发生分裂

• 每次发生的分裂的桶总是由Next决定

  • 与当前被插入的桶溢出无关，可引入溢出页处理桶溢出
  • 每次只分裂Next指向的桶，桶分裂后Next += 1
  • 后续产生映像桶总是位于上次产生映像桶之后

• “轮转分裂进化”：各桶轮流进行分裂，一轮分裂完成后进入下轮 分裂

查找

• 根据N、level计算当前d值，截取原始hash值

• 若hash值位于Next、N之间，说明该轮对应桶还未分裂， 直接在桶中查找

• 若hash值小于Next，说明该轮对应桶已经分裂，hash值向前 多取一位，在对应桶中查找

删除

• 删除操作是插入操作的逆操作

• 若删除元素后溢出块为空，可直接释放
• 若删除元素后某个桶元素为空，Next -= 1
  • 当Next减少到0，且最后桶也是空时，Next = N/2 - 1 ，同时level -= 1

1`

Huffman Tree

哈夫曼树/最优树：带权路径长度WPL最短的树

• 哈夫曼树中没有度为1的结点，又称为严格的（正则的）二叉树

• 树带权路径长度：树中所有叶子结点的带权路径长度之和 $WPL = \sum_{k=1}^n w_k l_k$

哈夫曼算法

哈夫曼算法：构建最小加权路径二叉树

• 输入：给定的n个权值${w_1, w_2, \cdots, w_n}$

• 初始化n个单节点二叉树集合$F={T_1, T_2, \cdots, T_n}$
• 合并权重最小的两棵树，将其权重之和作为新树权重记录于新树 根节点中
• 重复，直至生成单独一棵树

特点

• 贪婪算法
• Huffman算法构建的最优二叉树是只有叶子节点有权值，若所有 节点都有权值的最优二叉查找树，需要使用动态规划算法， 参见cs_algorithm/data_structure/tree_search

哈夫曼编码

• 哈夫曼编码：编码总长度最短的二进制前缀编码
• 前缀编码：任意编码都不是其他编码的前缀，此时编码可以

• 前缀编码可以使用二叉树设计，叶子结点代表字符，根节点到 叶子结点路径上分支代表的二进制串即为其二进制编码

• 对给定出现频率$P[1..n]$的字符集$C[1..n]$，生成哈夫曼树 即可得到哈夫曼编码

链式存储

哈夫曼树

1
2
3
4

typedef struct HTNode{
	unsigned int weight;
	struct HTNode *parent, *lchild, *rchild;
}HTNode, *HuffmanTree;

选拔树

优胜树

优胜树：非叶结点取值是两个孩子中较小者的完全二叉树

• 根据定义，根节点的取值是整个树的最小值
• 从叶节点构建/重构优胜树的过程中
  • 每对兄弟结点捉对比赛，胜利者晋升为父亲结点
  • 胜者逐级向上直到根节点为止
  • 调整优胜树的时间效率$\in \Theta(logk)$

顺序存储结构

1

typedef SqBiTree SqVictTree;

• 数组实现的二叉树可以通过完全二叉树性质迅速计算父节点、 孩子节点位置

淘汰树

淘汰树：非叶结点值是两个孩子结点中较大者，即指向失败者的 选拔树

• 可以简化选拔树重构过程
• 需要额外结点记录/指向胜者

用途

归并多路有序序列

• 问题：k路有序（降序）序列，要将其归并为一组有序序列， 归并过程每轮输出一个最小关键字记录 （显然只能是当前k路序列中第一个记录）

• 以k路序列首k个元素建立k个叶节点的选拔树

• 构建选拔树，输出最小元素值

  

• 用其所属序列下个元素替换其所在叶节点值，重构选拔

  

• 重复n轮：所有k轮归并总时间为$\in \Theta(nlogk)$

)$

树&森林

Free tree

自由树：连通、无回路图，具有一些其他图不具有的重要 特性

• 边数总比顶点数少一：$|E|=|V|-1$

  • 这个是图为一棵树的必要条件，但不充分
  • 若图是连通的，则是充分条件

• 任意两个顶点之间总是存在简单路径

(Rooted)Tree

（有根）树：存在根节点的自由树

• $root$：根节点数据元素
• $F=(T_1, T_2, \cdots, T_m)$：森林
• $T_i=(r_i, F_i)$：根root的第i棵子树

• 在任意一棵非空树中

  • 有且仅有一个特定称为根的节点
  • 节点数n>1时，其余节点可以分为m个互不相交的有限集 ，每个集合本身又是一棵树，称为根的子树

• 树中任何两个节点间总存在简单路径，所以可以任选自由树 中某节点，作为有根树的根

• 有根树远远比自由树重要，所以也简称为树

  • 根一般放在树的顶层，第0层
  • 之后节点根据和根的距离放在相应层数

Forest

森林：无回路但不一定连通的图

• 其每个连通分量是一棵树
• 对树中每个节点，其子树集合即为森林

Ordered Tree

有序树：所有顶点的所有子女都是有序（不能交换次序）的有根树

应用

• 常用于描述层次关系

  • 文件目录
  • 企业的组织结构
  • 字典的实现
  • 超大型的数据集合的高效存储
  • 数据编码

• 用于分析递归算法

  • state-space tree：状态空间树，强调了两种算法设计 技术：回溯、分支界限

结构

• ancestor：从根到该顶点上的简单路径上的所有顶点
• proper ancestor：除自身外的所有祖先顶点
• parent：从根到顶点简单路径中，最后一条边的另一端节点
• parental：至少有一个子女的顶点
• child：
• sibling：具有相同父母的顶点
• leaf：没有子女的顶点
• descendent：所有以该顶点为祖先的顶点
• proper descendent：不包括顶点自身的子孙
• subtree：顶点的所有子孙、连接子孙的边构成以该顶点为根的 子树
• depth：根到该顶点的简单路径的长度
• height：根到叶节点的最长简单路径的长度

链式存储结构

• 链表结点代表树中一个顶点，其中至少包含：数据域、指向子女 的指针域
• 链表头指针指向二叉树根节点

双亲表存储

双亲表示法

• 利用除根节点外，每个结点只有一个双亲，给所有结点添加一个 指向双亲的指针域

1
2
3
4
5
6
7
8

typedef struct PTNode{
	TElemType data;
	int parent;
}PTNode;
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];
	int r, n;
}PTree;

• 求结点双亲时是常数时间
• 求结点孩子时需要遍历整个结构

孩子链表存储

孩子表示法

• 把每个结点的孩子结点排列起来，视为线性表，以单链表作为 存储结构

  • 否则结点同构则浪费空间，不同构时操作不方便

    

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

typedef struct CTNode{
	// 逻辑意义的结点，存储兄弟关系
	int child;
		// 结点位置，`nodes`中序号
	struct CTNode *next;
		// 指示下个兄弟结点
}*ChildPtr;
typedef struct{
	// 实际存储信息的结点
	TElemType data;
	ChildPtr firstchild;
		// 孩子链表头指针
}CTBox;
typedef struct{
	CTBox nodes[MAX_TREE_SIZE];
	int n, r;
		// 节点数，根节点位置
}CTree;

二叉链表存储

First Child-next Silbling Representaion：孩子兄弟/二叉链表 /二叉树表示法

• 每个节点只包含两个指针，左指针指向第一个子女，右指针指向 节点的下一个兄弟
• 节点的所有兄弟通过节点右指针被单独的链表连接

1
2
3
4

typedef struct CSNode{
	ElemType data;
	struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

• 可高效的将有序树改造成一棵二叉树，称为关联二叉树
• 易于实现某些操作
  • 寻找孩子结点

森林与二叉树转换

• 给定一棵树，可以以二叉链表为媒介导出树与二叉树之间的对应 关系，即可以找到唯一一棵二叉树和与之对应

  • 任何一棵树对应的二叉树，其右子树必然为空

• 将森林中各棵树的根节点看作兄弟结点，则可以得到森林和 二叉树的对应关系

森林转换为二叉树

森林$F={T_1, T_2, \cdots, T_M}$转换为二叉树的 $B=(root, LB, RB)$

• 若F为空，即m=0，则B为空树
• 若F非空
  • root即为森林中第一个树的根$ROOT(T_1)$
  • LB是从$T_1$中根节点的子树森林转换而成的二叉树
  • RB是从森林$F^{‘}$转换而来的二叉树

二叉树转换为森林

二叉树的$B=(root, LB, RB)$转换为森林 $F={T_1, T_2, \cdots, T_M}$

• 若B为空，即m=0，则F为空树
• 若B非空
  • F中第一棵树根$ROOT(T_1)$即为二叉树根root
  • $T_1$中根节点的子树森林$F_1$是由B的左子树LB转换来的 子树森林
  • F中除$T_1$外的其余树组成的森林$F^{‘}$是由B的右子树 RB转换而来的子树森林

树、森林遍历

• 以二叉链表作树、森林的存储结构式，树、森林的先（根）序 遍历、后（根）序遍历对应二叉树先序、后序遍历

Binary Tree

二叉树：所有顶点子女个数不超过2个，每个子女不是父母的 left child就是right child的有序树

• 二叉树的根是另一棵二叉树顶点的左（右）子女
• 左右子树也是二叉树，所以二叉树可以递归定义
• 涉及二叉树的问题可以用递归算法解决

特点

• 二叉树第i层之多有$2^{i-1}$个节点
• 深度为k的二叉树最多有$2^k-1$节点

• 对任何二叉树$T$，如果其终端节点数$n_0$，度为2的节点数为 $n_2$，则$n_0=n_2+1$

  $$\left. \begin{array}{r} 考虑节点数：n = n_0 + n_1 + n_2 \\ 考虑分支数：n = n_1 + 2n_2 + 1 \end{array} \right \} \rightarrow n_0 = n_2 + 1$$

  • $n, n_0, n_1, n_2$：总结点数、终端节点数、度1节点数 、度2节点数

顺序存储结构

完全二叉树

顺序存储结构：顺序存储完全二叉树结点元素

1
2

typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

• 将完全二叉树编号为i的结点存储在一维数组中下标为i-1分量中
• 一般二叉树则将每个结点与完全二叉树结点相对照，存储在相应 分量中，并标记不存在的结点
  • 对某些二叉树空间利用效率极低
  • 所以顺序存储结构只适合完全二叉树

链式存储结构

• 二叉树的链表节点中至少包含3个域：数据域、左右指针域
• 链表头指针指向二叉树根节点
  • 为方便，也可以添加一个头结点，其lchild指针域指向 根结点

二叉链表

1
2
3
4

typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

• 含有n个结点的二叉链表中有n+1个空链域

三叉链表

1
2
3
4

typedef struct BiTriNode{
	TElemType data;
	struct BiTriNode *parent, *lchild, *rchild;
}BiTriNode, *BiTriTree;

• 在二叉链表基础上增加指向双亲结点的指针域

二叉线索链表

Threaded Binary Tree：线索二叉树/线索化树

• 使用二叉链表中的n+1个空链域存放二叉树遍历的前驱、后继 信息
• 附设标记域区分指针域存放子孙结点、前驱/后继

• 适合经常需要遍历的二叉树、查找遍历所得线性序列中前驱、 后继
  • 时间复杂度常数系数小
  • 无需设栈

1
2
3
4
5
6

typedef enum PointerTag{Link, Thread};
typedef struct BiThrNode{
	TElemType data;
	struct BitThrNode *lchild, *rchild;
	PointerTag LTag, RTag;
}BiThrNode, *BiThrTree;

• 后序线索化树找后继时需要知道双亲，应该使用带标志域的 三叉链表

Complete Binary Tree

• 满二叉树：深度为k且有$2^k-1$节点的二叉树，每层上的节点数 都是最大节点数

• 完全二叉树：essentially complete，树的每层都是满的，除 最后一层最右边的元素（一个或多个）可能有缺位

特点

• 只存在一棵n个节点完全二叉树，高度为 $\lfloor log_2 n \rfloor$

  • 深度为k、节点数为n的完全二叉树同深度为k的满二叉树中 1-n号节点一一对应
  • 叶子节点只可能在层次最大的两层上出现
  • 对任一节点，其左分支只能和右分支深度相同或大1

• 从上到下、从左到右对结点编号，即使用数组H存储完全二叉树 （从1开始编号，数组H[0]不存储节点值，或存放限位器）

  • 父母节点键会位于数组前$\lfloor n/2 \rfloor$个位置中 ，叶子节点位于后$\lceil n/2 \rceil$

  • 对位于父母位置i的键，其子女位于2i、2i+1，相应的对于 子女位置i的键，父母位于$\lfloor i/2 \rfloor$

应用

• 堆

二叉树高度

• 将空树高度定义为-1

算法

1
2
3
4
5
6
7
8

Height(T):
	// 递归计算二叉树的高度
	// 输入：二叉树T
	// 输出：T的高度
	if T = null_set
		return -1
	else
		return max{Height(T_left), Height(T_right)} + 1

特点

• 检查树是否为空是这个算法中最频繁的操作

• 算法时间效率

  • 树的节点数为n，则根据加法操作次数满足递推式 $A(n(T))=A(n(T{left})) + A(n(T{right})) + 1$， 得到$A(n(T)) = n$

  • 考虑为树中每个节点的空子树添加外部节点得到 扩展树，则外部节点数量x满足$x=n+1$

  • 检查树是否为空次数即为扩展树节点数目 $C(n(T))=n+x=2x+1$

二叉树遍历

• 不是所有关于二叉树的算法都需要遍历两棵子树，如：查找、 插入、删除只需要遍历两颗子树中的一棵，所以这些操作属于 减可变规模（减治法）

• 先序、中序、后序遍历都需要用到栈

• 中序遍历得到的序列称为中序置换/中序序列，先序、后序类似

递归版本

• Preorder Traversal：先序

  1 2 3 4 5 6

  PreOrder(T): visit(T) if T_left not null: PreOrder(T_left) if T_right not null: PreOrder(T_right)

• Inorder Traversal：中序

  1 2 3 4 5 6

  InOrder(T): if T_left not null: InOrder(T_left) visit(T) if T_right not null: InOrder(T_right)

• Postorder Traversal：后序

  1 2 3 4 5 6

  PostOrder(T): if T_left not null: PostOrder(T_left) visit(T) if T_right not null: PostOrder(T_right)

栈非递归

• 先序遍历

  • 深度优先入栈：左子树优先入栈

    • 节点先访问后入栈，栈内存已访问节点

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

    PreOrder(T): s = InitStack() cur = T while s.not_empty() or cur: while cur: visit(cur) s.push_back(cur) cur = cur.left cur = s.pop() cur = cur.right // 等价写法，仅使用`if`利用外层循环 PreOrder(T): s = InitStack() cur = T while s.not_empty() or cur: if cur: visit(cur) s.push_back(cur) cur = cur.left else: cur = s.pop() cur = cur.right

    • 基于对遍历性质的考虑
    • 扩展性较好，可以扩展到中序、后序遍历

  • 广度优先入栈：同层右、左节点先后入栈

    1 2 3 4 5 6 7 8 9 10

    PreOrder(T): s = InitStack() s.push_back(T) while s.not_empty(): cur = s.pop() if cur.right: s.push_back(cur.right) if cur.left: s.push_back(cur.left) visit(cur)

• 中序遍历

  • 深度优先入栈

    • 节点先入栈后访问，栈内存未访问节点

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

    InOrder(T): s = InitStack() cur = T while s.not_empty() or cur: while cur: s.push_back(cur) cur = cur.left cur = s.pop() visit(cur) cur = cur.right // 等价写法，仅使用`if`利用外层循环 InOrder(T): s = InitStack() cur = T while s.not_empty() or cur: if cur: s.push_back(cur) cur = cur.left else: cur = s.pop() visit(cur) cur = cur.right

• 后序：需要标记当前节点左、右子树是否被访问

  • 深度优先入栈

    • 节点先入栈后访问，栈内存未访问节点
    • 记录最后一次访问节点，判断右子树是否被访问 （若右子树被访问，右子节点必然是上个被访问节点）

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

    PostOrder(T): s = InitStack() cur = T last = NULL while s.not_empty() or cur: while cur: s.push_back(cur) cur = cur.left cur = s.top() // 检查右子树是否被访问过 if cur.right == NULL or cur.right == last: visit(cur) last = s.pop() // 此时再弹出`cur` cur = NULL // 置`cur`为`NULL`，否则 // 再次访问左子树，死循环 else: cur = cur.right

  • 或者为每个节点附设标志位

层次遍历

• 队列实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

  # 判断节点是否存在、再填充至队列 LevelTraversal(T): q = InitQueue() cur = T while q.not_empty() or cur: if cur.left: q.push_back(cur.left) if cur.right:d q.push_back(cur.right) visit(cur) cur = q.pop_first() # 先填充、再判断节点是否为`None` # 填充可保证、适合节点位置和满二叉树对应 LevelTraversal(T): q = InitQueue() q.push(T) # 层次遍历使用队列实现，所以无需像栈一样使用 # 两个判断条件`q.not_empty or cur` while q.not_empty(): cur = q.pop_first() # 弹出时判断节点是否有效 if cur: visit(cur) q.push_back(cur.left) q.push_back(cur.right)

• 严格分层遍历：记录队列长度、遍历固定长度

  1 2 3 4 5 6 7 8 9 10 11 12 13

  LevelTraversal(T): q = InitQueue() q.push(T) while q.not_empty(): # 记录当前开始时队列长度 # 每轮遍历该长度数目元素，严格分层遍历节点 for i=0 to len(q): cur_node = q.pop_left() visit(cur_node) if cur.left: q.push_back(cur.left) if cur.right: q.push_back(cur.right)

树的计数

• 二叉树相似：二者为空树或二者均不为空树，且其左右子树分别 相似
• 二叉树等价：二者不仅相似，而且所有对应结点上的数据元素 均相同

• 二叉树的计数：n个结点、互不相似的二叉树数量$b_n$
• 树和一棵没有右子树的二叉树一一对应，所以具有n个结点不同 形态的树的数目，等于具有n-1个结点互不相似的二叉树数目

数学推导

二叉树可以看作是根节点、i个结点的左子树、n-i-1个结点的右子树 组成，所有有如下递推

求解得

遍历性质

• 给定结点的前序序列、中序序列，可以唯一确定一棵二叉树

• n个结点，不同形态二叉树数目恰是前序序列为$1 \cdots n$ 二叉树能得到的中序序列数目

• 中序遍历过程实质是结点进栈、出栈的过程，序列$1 \cdots n$ 按不同顺序进栈、出栈能得到排列的数目即为中序置换数目 $C{2n}^n - C{2n}^{n-1} = \frac 1 {n+1} C_{2n}^n$

K-dimentional Tree

Kd树：循环遍历各维度，按该维度取值二分数据

• 对高维数据进行快速搜索二叉树

  • 超平面都垂直于轴的BSPTree

• Kd树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中超矩形区域
  • 构造kd树相当于用垂直于坐标轴超平面不断划分k维空间， 得到一系列超矩形区域

• Kd树构建目标

  • 树应该尽量平衡，即分割应尽量均匀
  • 最大化邻域搜索的剪枝

建树

• 输入：数据点$X_i, i=1,2,\cdots,N$

• 确定划分维度（轴）
  • 选择方差最大的轴，使得数据尽量分散
  • 按次序循环遍历所有轴：方便查找时定位轴
• 选择该维度上数值中位数作为划分点
  • 中位数查找方法
    • 各维度统一全体排序、记录
    • 抽样，使用样本中位数
  • 小于中位数的数据点划分至左子树，否则划分至右子树
• 递归建立左、右子树直至无法继续划分
  • 节点中包含数据项数量小于阈值

查找K近邻

• 输入：Kd树、目标点x

• 在Kd树中找出包含目标点x的叶节点，以之为近邻点

  • 从根节点出发，与节点比较对应坐标值，递归访问至叶节点 为止
  • 目标点在训练样本中不存在，必然能够访问到叶节点

• 沿树回溯，检查节点是否距离目标点更近，尝试更新

• 检查该节点另一子区域是否可能具有更近距离的点

  • 即考察以目标点为圆心、当前近邻距离为半径圆，同划分轴 是否相交
  • 则只需比较目标点同相应切分平面距离、近邻距离

• 若目标点同该对应切分平面距离小于近邻距离

  • 则将目标节点视为属于该子区域中的点
  • 从节点未访问子树开始重复以上步骤，进行近邻搜索

• 否则继续回退

• 退回到根节点时，搜索结束，近邻点

• 回溯过程中需要盘对子域是否访问过，可以通过标记、比较相应 轴坐标等方式判断
• k>1的情况类似，不过检测时使用最远近邻，新近邻需要和所有 原近邻依次比较

其他操作

插入新节点

• 从根节点出发，根据待插入节点、当前节点在对应维度取值确定 插入左、右子树
• 遍历直至叶子节点，插入

删除节点

• 简单方法：将待删除节点子节点组成新集合，对其重新构建， 将新子树挂载在原被删节点位置

• 分类讨论：设删除节点T对应划分维度为D

  • 节点无子树：直接删除
  • 节点有右子树
    • 在右子树寻找维度D取值最小节点P，替换被删除节点T
    • 在右子树递归处理删除节点P
  • 节点无右子树有左子树
    • 在左子树寻找维度D取值最小节点P，替换被删除节点T
    • 将T的左子树作为P的右子树
    • 在右子树递归处理删除节点P

查找维度D最小点

• 若当前结点切分维度为D：只需查找左子树
• 否则需要对左、右子树分别递归搜索

Vantage Point Tree

VP树：任选样本点，按照数据点与该点距离二分数据

• 对高维数据进行快速搜索二叉树

• VP树对样本点的组织表示对k维空间的划分

  • 每个节点对应k维空间中一个球形划分
  • 构造kd树相当于用以给定样本点为球心不断划分k维空间， 得到一系列球内、球外区域

建树

• 输入：数据$X_i, i=1,2,\cdots,n$

• 选择某数据点$X_v$作为划分球心
• 计算其他数据点距离$D_i = d(X_i, X_v)$
• 求出$D_i$中位数$M$
  • 与$X_v$距离$D_i \leq M$的数据点$D_i$划分至左子树
  • 与$X_v$距离$D_i \gt M$的数据点$D_i$划分至右子树

Rectangle Tree

R树：将空间划分为有重叠的

• B树高维推广
  • 类似B树将一维区间划分为多个不重叠的子区间
  • 同样是平衡树，所有叶子位于同一层上

• R树退化至1维有分割区间重叠问题，效果不如B树

性质

• $M$：节点中最大键数量
• $m \leq \frac M 2$：节点中条目最小数量

• 非根叶节点包含$m-M$索引记录：$I$表示可在空间中完全覆盖 节点中条目点的MBR

• 非根、非叶节点包含$m-m$个子节点：$I$表示可在空间中完全 覆盖节点中条目矩形的MBR

• 根节点条目数$[2, m]$，除非为叶子节点

• minimal bounding rectangle：MBR，最小边界矩形

节点结构

• 叶子节点结构：$(I, tuple-ids)$

  

  • $I((s_1, e_1), (s_2, e_2), \cdots, (s_n, e_n))$： n维空间中矩形
  • $tuple-ids$：节点包含的记录

• 非叶节点：$(I, child-pointer)$

操作

建树

矩形搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

SearchRect(T, S, ret):
	// 利用R树搜索矩形范围中包含的记录点
	// 输入：R树根节点T、待搜索矩形S
	// 输出：矩形S覆盖的条目

	if T.I join S == NULL:
		return

	// 若T不是叶子节点，检查其每个条目E
	if not T.is_leaf():
		for E in T.entries:
			// 对与S相交E.I对应条目E，递归调用搜索
			if T.I join S != NULL:
				SearchRect(E, S, ret)

	// 若T是叶子节点且T.I与S相交，检查其每个记录点
	elif T.I join S != NULL:
		for E in T.entries:
			if E in S:
				ret.add(E)

选择所属叶子

1
2
3
4
5
6
7
8
9
10
11
12
13

ChooseLeaf(T, E):
	// 在R树中寻找新索引条目所属叶子节点
	// 输入：R树根节点T、索引条目E
	// 输出：E所属R树中叶子节点

	if T.is_leaf():
		Assert(E.is_subset(T))
		return T

	else:
		for T_E in T.entries:
			if E.is_subset(T_E)
				return ChooseLeaf(T_E, E) or T_E

插入新条目

1
2
3
4
5
6
7
8
9
10
11
12

Insert(T, E):
	// 向R树中插入新条目
	// 输出：R树根T、新条目E

	L = ChooseLeaf(T, E)
	if L.has_slot():
		L.add(E)
	else:
		LL = L.split()
		L.add(E)
		P = L.get_parent()
		

调整树

1
2
3
4
5
6
7
8
9
10
11
12
13
14

AdjustTree(T, L):
	// 从不满足节点开始调整R树至满足要求
	// 输入：R树根T、不满足要求节点L
	// 输出：

	if L.is_root():
		return

	P = L.get_parent_node()
	if L.splitted():
		NN = L.get_split_node()
		if P.
	// 调整节点L在父节点中矩形框I大小
	addjust_I(P.L.I)

R*-tree

X-tree

SS-tree

SR-Tree

Metric-tree

总述

• 二叉查找树：最基础的查找树，但是不平衡时效率很差
• 自平衡查找树：使用旋转技术得到平衡二叉树
• 多路查找树：使用多叉树达到平衡

• 树高度一般即决定其查找、插入、删除效率
• 以代码复杂性、插入节点时间代价，换取查询时$logN$性能

Self-Balancing Binary Tree

自平衡查找树：如果节点插入、删除产生了一棵违背平衡要求的树， 就从称为旋转的一系列特定变换中选择一种，重新构造树使得 树满足平衡要求

• 不同的对平衡的定义产生了不同的实现
• 这种方案属于变治法中实例化简

Balance Factor

平衡因子：节点左、右子树高度差（一般右树-左数）

• AVL树中平衡情况下节点平衡因子只能为-1、+1、0

• 更新节点后可能存在不平衡节点，其平衡因子可能变为-2、+2

• 平衡因子也可以被定义为左右子树叶子数

Rotation

旋转需要使得二叉树平衡时，保证二叉树依然有序

• 左旋：节点平衡因子符号为正，即右子树高于左子树

  • 节点T下沉为其右儿子R的左儿子
  • 如果右儿子R本身有左子树RL，则左子树RL成为节点T 新右子树

• 右旋：节点平衡因子符号为负，即左子树高于右子树，

  • 节点T下沉为其左儿子L的右儿子
  • 如果左儿子L本身有右子树LR，则右子树LR成为节点T 新左子树

• 旋转只涉参与选择的至多3个节点指针变化，其余节点状态保持
• “旋转”行为确实类似：节点绕其子节点旋转，子节点旋转后上浮 成为父节点
• 参与旋转的两个节点也称为轴

分类

• AVL树
• 红黑树
• 分裂树

Multiway Search Tree

多路查找树：允许查找树中单个节点中不止包含一个元素

• 二叉查找树的推广，用于磁盘超大数据集的高效存取
• 此方案属于变治法中改变表现

分类

• 2-3树
• 2-4树
• B树
• B+树

Binary Search Tree

二叉查找树：分配给每个父母顶点的数字都比其左子树中数字大， 比右子树数字小

• 二叉树有序，保证二叉树能够快速找到中间元素，从而支持 二分查找

特点

• 对于n个顶点的二叉树，满足 $ \lfloor {log_{2}^{n}} \rfloor \leq h \leq n-1 $

• 二叉查找树的查找算法效率取决于二叉树的高度

  • 平均情况下，查找、插入、删除时间$\in Theta(logn)$

  • 最差情况下（严重不平衡的树，接近链表结构），树高度 h接近节点数n，查找、插入、删除时间$\in Theta(n)$

• 包含n个键的二叉查找树总数量 $c(n) = \frac 1 {n+1} C_{2n}^n, c(0)=1$

应用

• 查找

操作

查找

在给定二叉查找树中查找给定键值K

• 如果树为空，查找失败

• 若树不为空，将查找键K和树根节点K(r)比较

  • 相等则查找停止
  • $K < K(r)$：在左子树中继续查找
  • $K > K(r)$：在右子树中继续查找

特点

• 算法时间效率
  • 最差情况下，二叉树完全偏斜，需要进行n次比较
  • 随机情况下，查找n个随机键构造的二叉树比较次数$2logn$

插入

除非是空树，否则总是把新键K插入叶子节点中

• 通过查找K确定合适插入位置（叶子节点）
• 若K大于叶子节点键值，则作为右子女，否则作为左子女

最优二叉查找树

对集合中元素确定的查找概率，成功查找的平均比较次数最小的 二叉查找树（可以扩展到包含不成功查找）

• $a_i, i=1,2,\cdots,n$：从小到大互不相等的键
• $p_i, i=1,2,\cdots,n$：键查找概率
• $T_i^j$：由键$a_i, \cdots, a_j$构成的二叉树
• $C(i, j)$：成功查找的最小平均查找次数

动态规划构造

• 根据最优化法则，最优二叉查找树左右子树均是最优排列的

• 二叉树$Ti^j$有序，设树根为$a_1$，$a_2,..,a{k-1}$构成 的左子树、$a_{k+1},..,a_j$构成右子树均是最优排列的

递推式如下

• $1 \leqslant i \leqslant j \leqslant n$

  $$\begin{align} C(i, j) & = \min_{i \leqslant k \leqslant j} \{p_k + \sum_{s=i}^{k-1} p_s * (a_s在T_i^{k-1}中层数 + 1) + \sum_{s=k+1}^j p_s * (a_s在T_{k+1}^j中层数 + 1) \}\\ & = \min_{i \leqslant k \leqslant j} \{ \sum_{s=i}^{k-1} p_s * a_s在T_i^{k-1}中层数 + \sum_{s=k+1}^j p_s * a_s在T_{k+1}^j中层数 + \sum_{s=i}^j p_s \} \\ & = \min_{i \leqslant k \leqslant j} \{C(i, k-1) + C(k+1, j)\} + \sum_{s=i}^j p_s \end{align}$$

• $1 \leqslant i \leqslant n+1, C(i, i-1)=0$：空树

• $1 \leqslant i \leqslant n, C(i, i)=p_i$：单节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

OptimalBST(P[1..n])
	// 动态规划法构建最优二叉查找树
	// 输入：P[1..n]n个键查找概率
	// 输出：在最优BST中查找成功的平均比较次数，最优BST子树根表
	for i = 1 to n do
		C[i, i-1] = 0
		C[i, i] = P[i]
		R[i, i] = i
	C[n+1, n] = 0
		// 初始化平均查找次数表、子树根表
	for d = 1 to n-1 do
		// d为二叉树节点数
		for i = 1 to n-d do
			// n-d是为了控制j的取值
			j = i + d
			minval = \infty
			for k = i to j do
				// 遍历设置二叉树根节点
				if C[i, k-1] + C[k+1, j] < minval
					minval = C[i, k-1] + C[k+1, j]
					kmin = k
			R[i, j] = kmin
			sum = P[i]
			for s=i+1 to j do
				sum += P[s]
			C[i, j] = minval + sum
	return C[1, n], R

算法特点

• 算法效率
  • 算法时间效率为立方级
  • 算法空间效率为平方级

AVL Tree

AVL树：要求其节点在左右子树高度差不能超过1的平衡二叉树

• 基本思想：总能通过一次简单的节点重排使树达到平衡

  • 如果树插入操作使得一棵AVL树失去平衡，利用旋转对树作 变换
  • 若有多个这样的节点，找出最靠近新插入的叶子节点不平衡 结点，然后旋转以该节点为根的子树

• AVL树高度h即为其查找、插入效率

  • 包含n个节点AVL树高度h满足 $\lfloor log_2 n \rfloor \leq h < 1.4405log_2(n+2) - 1.3277$

  • 最差情况下，操作效率$\in \Theta(logn)$

  • 平均而言，在n不是太小时，高度h平均为 $1.01log_2 n + 0.1$（几乎同折半查找有序数组）

• AVL树缺点（平衡代价），阻碍AVL树成为实现字典的标准结构

  • 需要频繁旋转
  • 维护树的节点平衡
  • 总体比较复杂

旋转

按照节点平衡符号进行旋转：+左旋、-右旋

• 单旋：不平衡节点、不平衡子节点不平衡因子符号相同

  • 全为+：不平衡节点左旋
  • 全为-：不平衡节点右旋

• 双旋：不平衡节点、不平衡子节点不平衡因子符号不同

  • 先旋转不平衡子节点
  • 再旋转不平衡节点

• 优先考虑最底层、不平衡节点

插入节点

AVL树插入关键：查找不平衡节点

• 节点中应有存储其平衡因子的实例变量
• 插入过程中经过每个节点返回当前节点子树深度是否变化
• 比较节点平衡因子、子节点深度变化返回值判断是否平衡

• 插入过程中查询的每个节点都有可能不平衡
• 自下而上返回深度变化情况，优先旋转最底层不平衡节点

4种插入情况

根据插入情况的不同，对最靠近新插入叶子节点的不平衡点T

LL

插入T左儿子L的左子树LL：平衡因子全-

• 即T到最底层叶节点（只可能有一个）的路径为LL（中间省略）
• R-rotation：右单转，对T做一次右旋即可平衡

RR

插入T右儿子R的右子树R：平衡因子全+

• 即T到最底层叶节点（只可能有一个）的路径为RR（中间省略）
• L-rotation：左单转，对T做一次左旋即可平衡

LR

插入T左儿子L的右子树R：平衡因子-+

• 即T到最底层叶节点（只可能有一个）的路径为LR（中间省略）
• LR-rotation：左右双转
  • 先对左儿子L做一次左旋，变成LL模式
  • 在LL模式下，再对T做一次右旋

RL

插入T右儿子R的左子树L：平衡因子+-

• 即T到最底层叶节点（只可能有一个）的路径为RL（中间省略）
• RL-rotation：右左双转
  • 先对右儿子R做一次右旋，变成RR模式
  • 在RR模式下，再对T做一次左旋

实现

删除节点

• 在AVL树中删除键相对而言比较困难，但也是对数级的

实现

Red-Black Tree

红黑树：能够容忍同一节点的一棵子树高度是另一棵的2倍

Splay Tree

分裂树：

2-3树

2-3树：可以包含两种类型的节点2节点、3节点，树的所有叶子节点 必须位于同一层

• 2-3树的高度即决定其查找、插入、删除效率

  • 节点数为n的2-3数高度h满足 $log_3(n+1)-1 \leq h \leq log_2(n+1) - 1$
  • 最差、平均情况下，操作效率$\in \Theta(logn)$

• 2-3树总是高度平衡

  • 所有叶子节点位于同一层，即树根到其路径长度相同
  • 2-3树平衡代价
    • 树中节点可以有1或2个键，需要处理2种节点类型
    • 拆分3节点的情况有很多种

• 节点类型

  • 2节点：只包含1个键K、2个子女

    • 左子女：作为所有键都小于K的子树的根
    • 右子女：作为所有键都大于K的子树的根

  • 3节点：两个有序键$K_1 < K_2$、3个子女

    • 最左边子女：作为键值小于$K_1$的子树的根
    • 中间子女：作为键值位于$[K_1, K_2]$之间子树的根
    • 最右边子女：作为键值大于$K_2$的子树的根

• 类似的还有2-4树

查找

• 如果根是2节点，当作二叉树查找

  • 若K等于根键值，停止
  • 若K小、大于根键值，在左、右子树中查找

• 若根是3节点

  • 和两个键值比较，有相等，停止
  • 否则能确定应该在3棵子树中哪棵继续查找

插入节点

除非是空树，否则总是把新键K插入叶子节点中

• 查找K确定合适的插入位置（叶子节点）

• 若叶子节点2节点，根据大小关系将K作为第一个键或第二个键 插入

• 若叶子节点3节点，把叶子分裂为两个节点：3个键中最小的放入 第一个叶子中，最大的放入第二个叶子中，中间的键提升到原 叶子节点父母中

  

  • 若叶子就是根，则需要创建新根容纳中间键
  • 中间键的提升可能会导致父母节点分裂，并引起祖先链条上 多个节点的分裂

删除节点

B树

B树：允许节点可以有$1~m-1$个键（$2~m$个子女）

1
2
3
4
5
6
7

#define BTREE_M
typedef struct BTNode{
	unsigned int degree;				// 节点实际包含键数
	KeyType key_slots[BTREE_M-1];		// 节点存储键数组
	struct BTNode ptr_slots[BTREE_M];	// 指向子女节点指针
	struct BTNode * ptr_parent;			// 父节点指针
}BTNode, *BTNodePtr;

• $m$：B树阶数，节点允许最大子女数

  • 节点最多允许有$m-1$个条目
  • $m=2$即为二叉树、$m=3$即为2-3树

• 键：用于构建树的关键字，和具体条目类似于键值对

• 根节点具有$2~m$个子女，除非为叶子节点

• 非根、非叶节点具有$[\lceil m/2 \rceil, m]$个子女

  • 即具有$[\lceil m/2 \rceil - 1, m]$个有序键

  • 其中子树$T_0$所有键小于$K_1$，子树$T_1$中所有键大于 等于$K_1$小于 $K_2$，以此类推

• B树是完美平衡的：所有叶子节点在同一层上

查找

算法

• 输入：B树、目标查找键
• 输出：查找键所属B树节点（若存在）

• 从根节点开始，比较查找键k和节点中键序列大小

  • 节点中键有序，若B树阶数足够大，可考虑折半查找

• 若在节点键序列中找到匹配键，则查找成功、返回

• 否则根据比较结果选择合适分支，顺着指针链前进，在相应子女 节点中进行查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

BTreeSearch(T, k):
	// 在B树中搜索键
	// 输入：B树根节点T、目标查找键k
	// 输出：目标键所在节点、目标键在节点中序号
	i = 0
	cur = T

	// 遍历寻找目标键对应键、分支
	while i < cur.degree and k > cur.key_slots[i]:
		i += 1

	if i < cur.degree and k == cur.key_slots[i]:
		return cur, i
	elif cur.is_leaf():			// 未找到目标键
		return cur, -1
	else:
		return BTreeSearch(cur.ptr_slots[i], k)

分裂

算法

• 输入：待分裂节点父节点、待分裂节点序号

• 计算待分裂节点分裂中心

  • 将分裂中心右侧数据移动至新节点

• 将节点分裂中心、新节点提升至父节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

BTreeNodeSplit(T, ptr_idx):
	// 分裂B树中节点
	// 输入：待分裂节点父节点`T`、待分裂节点序号`ptr_idx`

	nnode = BTreeNode()
	fnode = T.ptr_slots[ptr_idx]

	// 分裂中心
	mid = fnode.degree // 2

	// 复制右半部分键至新节点
	nnode.key_slots[:fnode.degree - mid] = fnode.key_slots[mid:fnode.degree]
	fnode.key_slots[mid:fnode.degree] = NULL

	// 若原节点非叶子节点，复制右半部分指针至新节点
	if not fnode.is_leaf():
		nnode.ptr_slots[:fnode.degree + 1 - mid] = fnode.ptr_slots[mid: fnode.degree + 1]
		fnode.ptr_slots[mid: fnode.degree+1] = NULL

	// 修改两节点度
	nnode.degree = fnode.degree - mid
	fnode.degree = mid

	// 将分裂中心提升至父节点
	// 修改父节点指向子女节点指针
	T.key_slots.insert(fnode.key_slots[mid], ptr_idx)
	T.ptr_slots.insert(nnode, ptr_idx+1)	// 原节点指针不变

插入

• 输入：B树根T、待插入键K
• 假设B树中不存在键K，否则查找、更新对应值即可

• 根据需要插入键K，查找需要插入的叶子节点L
• 若叶子节点L键数小于m-1，直接插入结束
• 否则以叶子节点键值中位数mid为中心分裂
  • 将mid插入叶子节点L父节点P中
  • 将mid左子支指向分裂后左子树、右子支指向分裂后右子树
• 对父节点尝试操作

1
2
3
4
5
6
7
8
9
10
11
12
13

BTreeInsert(T, k)
	// 向B树中插入不存在键K
	// 输入：B树根T、待插入键k

	// 找到键`k`应该插入的叶子节点`L`
	L, _ = BTreeSearch(T, k)
	L.key_slots.insert_in_order(k)


	// 若节点已满、须分裂
	while L.is_full():
		BTreeNodeSplit(L.parent_ptr, L.get_index())
		L = L.parent_ptr

• 此实现是考虑节点都有空位容纳新键，节点插入新键后再 判断是否需要分裂

删除#todo

应用

• 类似一般查找树，把数据记录插入初始为空的树中构造B树

B+树

B+树：B树的一种变形树

• 其中非叶节点只有索引作用，跟记录相关信息均存放在 叶结点中
• B+树中所有叶结点构成有序链表，可以按照键次序遍历

查找

算法

• 从根开始，比较查找键K和节点中键大小，选择合适指针，顺着 指针链前进

• 指针链指向可能包含查找键的叶子节点，在其中查找K

  • 父母节点、叶子节点都是有序的，如果B树次数足够 大，可以考虑使用折半查找

算法效率

以B树作索引存储大型数据文件为例

• 查找指定查找键访问B树节点数量为B树高度$h+1$ （即磁盘访问次数）

• 次数为m、高度为h的B树能够包含最少节点数为 $n \geqslant 4 \lceiling m/2 \rceiling ^ {h-1} -1$， 即$h \leqslant \lfloor log_{[m/2]} \frac {n+1} 4 \rfloor + 1$

• 所以在B树中查找，访问磁盘次数$\in O(logn)$

  • 实际应用中，磁盘访问次数很少超过3，因为B树的根、甚至 是第一层节点会存储在内存中减少磁盘访问次数

插入

算法

• 查找新记录键K对应的叶子节点

• 若叶子节点中还有空间存放此记录，在保持键有序的情况下插入

• 若节点中没有空间

  • 将节点分裂，后半部分记录放在新节点中
  • 新节点中最小键$K^{‘}$、指向其的指针插入原叶子节点 父母节点中（原叶子节点键、指针之后）
  • 插入过程可以一直回溯到树根，甚至直到树根分裂

其他考虑

• 查找新记录对应叶子节点时就分裂满节点，可以避免递归分裂
• 将满叶子节点中部分键移动给兄弟节点，同时替换父母节点中的 键值（保证B树特点），增加少许复杂度以节约空间

算法特点

• 算法效率
  • 算法时间效率$\in O(logn)$

应用

• B+树是存储结构化记录数据集合最重要的索引结构
  • 所有数据记录（键）按照升序存储在叶子节点中，其父母 节点作为索引
  • B+树中节点常常对应磁盘中页
  • 考虑到访问磁盘页面是比较内存中键值比较时间多好几个 数量级，磁盘访问次数是衡量B树效率的主要指标

标

Heap

堆/大根堆：每个节点包含一个键、且大于等于其子女键、基本完备 的二叉树

• 认为非叶子节点自动满足大于其子女键值
• 根到某个叶子节点路径上，键值序列递减（允许键值相等则是 非递增）
• 键值之间没有从左到右的次序，即树的同一层节点间没有任何 关系，或者说左右子树之间没有任何关系

堆特性

• 完全二叉树特性参见完全二叉树
• 堆的根总是包含了堆的最大元素
• 堆的节点及该节点子孙也是一个堆

• 堆这种数据结构经常被用于实现优先队列

最小堆

min-heap：（最大）堆的镜像

• 堆的主要特性最小堆也满足，但
  • 最小堆根节点包含最小元素
• 可通过给元素取反构造（最大）堆得到最小堆

堆算法

Bottom-Up Heap Construction

自底向上堆构造：先利用所有元素构造二叉树，从倒数第二层开始 修改使得整棵树满足堆要求

算法

• 将给定线性表对应为（初始化）一棵完全二叉树
• 对二叉树进行堆化，从最后父母节点开始、到根为止，算法检查 节点键是否满足大于等于其子女键
  • 若不满足，交换节点键K和其子女最大键值
  • 在新位置上检查是否满足大于子女键值，直到满足为止
• 对以当前节点为根的子树满足堆化条件后，算法对节点直接前趋 进行检查，直到树根满足堆化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

HeapAdjust(H[0..n-1], cur):
	// 左右子树已经为堆，仅根节点元素不一定满足
	// 输入：待调整堆H、根节点cur，cur左右子树已经为堆
	// 输入：调整后堆
	while 2*cur+2 < n:

		// 获取左右子女中最大者
		if 2*cur+2 < n:
			_tmp = argmax(H[2*cur+1], H[2*cur+2])
		else:
			_tmp = 2*cur+1

		// 交换自身和最大子女
		if H[_tmp] > H[cur]:
			swap(H[cur], H[_tmp])
			cur = _tmp
		else:
			// 从底向上建堆，左、右子树均为堆
			// 则此时已经满足堆性质
			break

	return H

HeapBottomUp(H[0..n-1]):
	// 用自底向上算法，从给定数组元素中构造一个堆
	// 输入：可排序数组H[0..n-1]
	// 输出：堆H[0..n-1]
	for i=floor((n-1)/2) to 0:
		HeapAdjust(H, i)
	return H

算法特点

• 算法效率
  • 时间效率：最差情况，每个位于树第i层节点会移到叶子层 h中，每次移动比较两次，则总键值比较次数 $C_{worst}=2(n-log_2(n+1))$ （将各层叶子节点可能交换次数加总即差比数列求和）

Top-Down Heap Construction

自顶向下堆构造算法：先利用部分元素构建堆顶，把新键连续插入 已经构造好的堆末尾，修改使之满足堆要求

算法

• 把包含键K的新节点附加在当前堆最后一个叶子节点
• 将K与其父母进行比较
  • 若后者大于K，算法停止
  • 否则交换这两个键，并比较K和其新父母，直到K不大于其 父母或是达到了树根

算法特点

• 算法效率
  • 操作所需键值比较次数小于堆高度$h \approx log_2 n$， 则总比较次数$\in \Theta(nlogn)$

删除堆根节点

算法

• 根键和堆中最后一个键K交换
• 堆规模减1（删除原根键）
• 按照自底向上堆构造算法，把K沿着树向下筛选使得新树满足 堆化

算法特点

• 算法效率
  • 效率取决于树堆化所需比较次数，不可能超过树高度两倍， 即$\in O(logn)$

堆排序算法

算法

• 为给定数组构造堆
• 删除最大键，即对堆应用n-1此根删除操作

算法特点

• 算法效率

  • 根删除阶段算法所需比较次数

    $$\begin{align} C(n) & \leq 2\sum_{i=1}^{n-1} \lfloor log_2i \rfloor \\ & \leq 2 \sum_{i=1}^{n-1} log_2(n-1) \\ & = 2(n-1)log_2(n-1) \end{align}$$

  • 两阶段总效率$\in O(nlogn)$

  • 详细分析证明，无论最差情况、平均情况下，时间效率 $\in \Theta(nlogn)$

• 堆排序时间效率和归并排序、快排时间效率属于同一类，但是 堆排序是在位的（不需要额外存储空间）

• 随机实验表明：堆排序比快排慢、和归并排序相比有竞争力

集合

集合：互不相同项的无序组合

• 要么指出集合的特殊属性，只有集合中元素才满足的特性
• 要么显式列出集合的所有成员

存储映像

位向量存储表示

位串表示法

• 每个集合S使用一个位串表示，位串中每位代表全集U的一个元素
• 当且仅当全集$U$中第i个元素被包含在子集$S$中时，位向量 第i个元素为1

1

typedef int BitSet[MAX_SET_SIZE/sizeof(int)];

• 可以实现快速的标准集合运算
• 以使用大量存储空间为代价的

线性表存储表示

线性表表示法

• 每个集合使用一个线性表表示，线性表中存储集合元素

1
2
3
4

typedef SqList SLSet;
	// 顺序表表示集合
typedef LinkList LLSet;
	// 链表表示集合

• 集合不能包含相同元素，列表可以

  • 可以引入multiset、bag绕过对唯一性的要求
  • 多重集和包是可重复项的无序组合

• 集合是元素的组合，而列表是集合的有序组合

  • 用线性表表示集合时，不必维护线性表的有序排列

集合运算

• 检查元素是否属于集合
• 集合的并集
• 集合的交集

Disjoint Set/Union Find

不相交集/并查集：由某个有限集的一系列不相交子集，及相应 操作构成

• 通常假设集合中元素为整数，或可以映射为整数
• 主要包括find、union操作

存储映像

• 实现应该对find、union有特殊优化

  • 按秩合并：将包含较少结点的集合合并到含有较多结点集合
  • 路径压缩：将每个结点都直接指向根节点

• 大多数实现会使用集合某个元素作为该集合代表

  • 有些对代表没有特殊约定
  • 有的要求代表为子集中最小元素等

树双亲表存储表示

双亲表示法

• 使用树的双亲表示法作存储结构

1

typedef PTree MFSet;

• 以集合中某个元素作为树根、集合名，其余所有结点都作为根 的孩子结点

• 每个结点只能有一个双亲结点，即只能属于一个集合，适合存储 不相交集

应用

• 生成不相交集
  • 求解无向图中连通分量数量
  • 求解等价问题：两两等价元素作为一类，求解每类元素
• 集合归并
  • 生成迷宫：连通入口、出口连通分量

Map/Dictionary

映射/字典：能查找给定元素、增加新元素、删除元素的集合

• 需要处理的是动态内容的查找，因此需要在查找效率和其他两种 操作中达到平衡

• 数组、散列法、平衡查找树都可以实现字典

  ||散列表|平衡查找树| |——-|——-|———| |渐进时间效率|平均$\in \Theta(1)；最坏$\in \Theta(n)$|$\in \Theta(logn)| |有序性保留|不假定键有序，不保证，不适合按序遍历、按范围查询|保证|

应用

• Extendible Hashing：可扩充散列，用于存储磁盘上大型字典
  • 查找时先计算可能包含查找键K的存储段磁盘地址
  • 然后从磁盘中读取段中所有键，从中查找K
  • 因为存取主存开销较磁盘小很多，宁可多次存取主存

线性表综述

线性表：n个数据元素的有限序列

• 元素个数n定义为线性表长度，n=0时称为空表
• 非空表中每个元素都有确定的位置

顺序存储结构

顺序存储结构/映像：使用一组地址连续的存储单元依次存储数据 元素

• 具体参见algorithm/data_structure_intro

顺序表

顺序表：顺序存储结构的线性表

1
2
3
4
5

typedef struct{
	ElemType *elem;
	int length;
	int listsize;
}SqList;

• 以元素在计算机内物理位置相邻表示线性表中数据元素之间 的逻辑关系

• 每个数据元素存储位置和线性表起始位置，相差和其在线性表中 位序成正比常数，所以顺序表时一种随机存取存储结构

  • 高级程序语言中数组类型也有随机存取特点，因此通常 用数组描述

时间效率

• 插入/删除：$O(n)$
  • 主要时间耗费在移动元素上
• 求表长：$O(1)$
• 取第n个元素：$O(1)$

链式存储结构

链式/非顺序存储结构/映像：用一组任意存储单元存储线性表 中数据元素，还需存储一个指示其直接后继的信息

• 具体参见algorithm/data_structure_intro

（线性/单）链表

线性链表：n个节点链接而成

1
2
3
4

typedef struct LNode{
	ElemType data;
	struct LNode * next;
}LNode, *LinkList;

• 链表中每个节点只包含一个指针域
  • 数据元素之间的逻辑关系由节点中指针指示，即指针为数据 元素之间的逻辑关系映像
• 整个链表存取必须从头指针开始
• 单链表中任何两个元素存储位置之间没有固定联系，是非随机 存取存储结构

• 头指针：指示链表中第一个节点的存储位置
• 头节点：在单链表第一个节点之前附设的节点，其数据域可以 不存储信息，也可以存储线性表长度、尾指针等附加信息

时间效率

• 插入、删除：$O(n)$
  • 已知插入、删除元素确切位置的情况下，仅需修改指针， 而不需要移动元素
• 取第n个元素：$O(n)$
  • 访问时间依赖元素在列表中位置

说明

• 在很多场合下，链表是线性表的首选结构

  • 链表不需要事先分配任何存储空间，空间利用合理
  • 插入、删除效率高，只需要重连相关指针

• 但是存在一些实现问题

  • 求线性表长不如顺序存储结构

• 链表中结点关系使用指针表示，数据元素在线性表中“位序” 概念淡化，被“位置”代替

因此重新定义带头结点的线性链表

1
2
3
4
5
6
7
8

typedef struct LNode{
	ElemType data;
	struct LNode * next;
}*Link, * Position;
typedef struct {
	Link head, tail;
	int len;
}

单链表注意事项

• 头结点/头指针：处理链表非常方便的技巧

  • 头指针指向链表首个结点：便于调整首个节点位置时，仍然 记住链表
  • 头指针不包含链表信息，本质不属于链表：有些情况下方便 统一代码，不需要特殊考虑链表首个节点

• 对链表进行可能改变链表的遍历操作：一般使用两个标记 结点/指针

  • 头结点/指针lstart：记住链表
  • 遍历标记指针cur：标记处理结点

• 交换节点：标记指针需要指向当前处理节点的前一个结点

  • 单链表中只有指向下个节点的指针，若标记指针指向当前 节点，则无法方便将链表同当前节点断开、重连
  • 注意待交换两个节点为同一节点的情况：不同于值交换 ，这种情况可能导致链表错误连接成环

• 无指针、纯引用对象语言（python）中：只能使用节点对象 遍历链表

  • 变量为链表中节点引用：使用类似普通指针，需要注意 别修改引用节点数据
  • 变量为额外节点引用：内存类似普通指针，使用时注意 解析引用次数

静态链表

静态链表：使用数组描述的链表

1
2
3
4

typedef struct{
	ElemType data;
	int cur;
}component, SLinkList[MAXSIZE];

• 数组分量表示节点
• 使用游标cur作为指针域指示节点在链表中的逻辑位置
• 第0个分量表示头节点，其指针域cur指向链表第一个节点

• 方便在无指针高级语言中使用链式结构
• 为确定未使用的数组分量，可以将未被使用的、删除的分量用 游标链成备用边表

Circular Linked List

循环链表：表中最后一个节点指针域指向头节点，整个链表形成环

• 循环链表和线性链表操作基本一致
  • 仅循环条件不再是指针域为空，而是是否等于头指针

Double Linked List

双向链表：链表中有两个指针域，分别指向直接后继、直接前驱

1
2
3
4
5

typedef struct DuLNode{
	ElemType data;
	Struct DulNode * prior;
	Struct DulNode * next;
}DuLNode, * DuLinkList;

• 双向链表克服线性链表寻找直接前驱时间$O(n)$的缺点
• 双向链表大部分操作和线性链表相同，指示有些操作需要同时 修改两个指针

• 字符串：数组实现的一种数据结构
  • 字符串常见操作不同于其他数组
    • 计算字符串长度
    • 按照字典序确定字符串排序时位置
    • 连接字符串构

分类

图$G=$：由一些称为顶点的点构成的集合，其中某些顶点由 称为边的线段相连

• 有限集合V：元素为顶点vertex
• 有限集合E：元素为顶点二元组，称为边edge/弧arc

边方向

Undigraph/Undirected Graph

• 无向图：所有边都是无向边的图
• 无向边：若有序对$(u, v) \in E$，必有$(v, u) \in E$， 即E是对称的，顶点对$(u, v)$等同于$(v, u)$，没有顺序

对无向边$(u, v)$

• 则顶点u、v相互adjcent
• 其通过undirected edge$(u, v)$相连接
• 顶点u、v称为边$(u, v)$的endpoint
• u、v和该边incident（相依附）

Digraph

• 有向图：所有边都是有向边的图
• 有向边：若有序对对$(u, v) \in E$无法得到$(v, u) \in E$， 即两者不等同，有顺序

对有向边$(u, v)$

• 边$(u, v)$的方向是从顶点u到顶点v
• u称为tail，v称为head

边权重

Ordered Graph

有序图：各边地位有序

Weighted Graph/Network

加权图/网络：给边赋值的图

• 值称为weight或cost
• 有大量的现实应用

边数量

• complete graph：任意两个顶点直接都有的边相连的图
  • 使用$K_{|v|}$表示有|V|个顶点的完全图
• dense graph：图中所缺的边数量相对较少
• sparse：图中边相对顶点数量较少

特点

• 不考虑loop（顶点连接自身边），则含有|V|个顶点无向图 包含边的数量|E|满足： $ 0 \leq |E| \leq \frac {|V|(|V| - 1)} {2} $

• 对于稀疏图、稠密图可能会影响图的表示方法，影响设计、使用 算法的运行时间

图表示方法（存储结构）

Adjacency Matrix

邻接矩阵：两个数组分别存储数据元素（顶点）信息、数据元素之间 关系（边）的信息

• n个顶点的图对应n * n的bool矩阵
  • 图中每个顶点使用一行和一列表示
  • i、j节点间有边，则矩阵第i行、j列元素为1，否则为0
• 无向图邻接矩阵一定是对称的，有向图邻接矩阵不一定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef enum{DG, DN< UDG, UDN} GraphKind;
typedef struct ArcCell{
	VRType adj;
		// 顶点关系类型：无权图0、1是否相邻，加权图权值类型
	InfoType * info;
		// 弧相关信息
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	VertexType vexs[MAX_VERTEX_NUM];
		// 顶点向量
	AdjMatrix arcs;
	int vexnum, arcnum;
		// 图当前顶点弧数
	GraphKind kind;
}

Adjacency List

邻接表：n条单链表代替邻接矩阵的n行，对应图G的n个顶点

• 每个顶点用一个邻接表表示

  • 线性表的header表示对应的顶点
  • 链表中结点表示依附于顶点的边

• 无向图一条边在邻接链表中对应两条链，有向图对应一条

  • 有向图出度计算简单
  • 计算入度则比较复杂，如果需要频繁计算入度，可以再存储 一个反向邻接表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typedef struct ArcNode{
	int adjvex;
		// 弧指向顶点信息
	struct ArcNode *nextarc;
		// 指向下条弧指针
	InfoType * info;
		// 弧相关信息
}ArcNode;
typedef struct VNode{
	VertexType data;
		// 顶点信息
	ArcNode * firstarc;
		// 首条依附该顶点的弧指针
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
	AdjList vertices;
	int vexnum, arcnum;
	int kind;
}

Orthogonal List

十字链表：将有向图的邻接表、逆邻接表结合起来

• 有向图中每条弧、每个顶点对应一个结点
• 弧结点所在链表为非循环链表，
  • 结点之间相对位置自然形成，不一定按照顶点序号有序
• 表头结点即顶点结点，顺序存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typedef struct ArcBox{
	int tailvex, headvex;
		// 头、尾顶点链域
	struct ArcBox *hlink, *tlink;
		// 头相同、尾相同弧链域
	InfoType *info;
		// 弧相关信息
}ArcBox;
typedef struct VexNode{
	VertexType data;
		// 顶点信息
	ArcBox *firstin, *firstout;
		// 顶点第一条出、入弧
}VexNode;
typedef struct{
	VexNode xlist[MAX_VERTEX _NUM];
		// 表头
	int vexnum, arcnum;
}OLGraph;

Adjacency Multilist

邻接多重表：无向图的另一种存储形式

• 一条边对应唯一结点
  • 所有依附于同一顶点的串联在同一链表中
  • 每个边界点同时链接在两个链表中
  • 避免无向图邻接表中一条边两次出现
• 类似十字链表，仅无需区分头尾结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

typedef struct EBox{
	VisitIf mark;
		// 访问标记
	int ivex, jvex;
		// 边依附的两个顶点
	struct EBox *ilink, *jlink;
		// 依附两个顶点的下条边
	InfoType *info;
		// 边信息指针
}EBox;
typedef struct VexBox{
	VertexType data;
	EBox *firstedge;
		// 第一条依附该顶点的边
}VexBox;
typedef struct{
	VexBox adjmulist[MAX_VERTEX_NUM];
	int vexnum, edgenum;
}AMLGraph;

说明

• 稀疏图：尽管链表指针会占用额外存储器，但是相对于邻接矩阵 占用空间依然较少

• 稠密图：邻接矩阵占用空间较少

• 邻接矩阵、邻接链表都可以方便的表示加权图

  • 邻接矩阵元素A[i, j]设置为有限值表示存在的边的权重， 设置为$\infty$表示不存在边，此时矩阵也称 weighted matrix或cost matrix
  • 邻接链表在节点中型跨同时包含节点名称和相应边权重

• 任何可以存储顶点、边的数据结构（如集合）都可以表示图， 只是存储效率低、无法高效操作

概念

路径

有向图

• directed path：有向图中顶点的一个序列，序列中每对连续 顶点都被边连接，边方向为一个顶点指向下一个顶点

• directed cycle：有向图中节点序列，起点、终点相同，每个 节点和其直接前趋之间，都有一条从前趋指向后继的边

• directed acyclic graph：DAG，有向无环图

无向图

• path：（无向）图G中始于u而止于v的邻接顶点序列，即为顶点u 到顶点v的路径

• simple path：路径上所有点互不相同

• cycle：特殊的path

  • 起点、终点都是同一顶点
  • 长度大于0
  • 不包含同一条边两次

• acyclic：不包含回路的图

长度

• length：路径中代表顶点序列中的顶点数目减1，等于路径中 包含的边数目
• distance：顶点间距离，顶点之间最短路径长度

连通性

无向图

• connected：顶点u、v连通，当且仅当存在u到v的路径

• connected graph：连通图，对图中的每对顶点$(u, v)$， 都有从u到v的路径

• connected component：连通分量，给定图的极大连通子图， 即没有可以添加的连通子图用于扩充

  • 非连通图中包含的几个自我连通的部分

• articulation point：关节点，如果从连通图$G$中删除顶点 $v$、极其邻接边各点之后的的图$G^{‘}$至少有两个连通分量， 则称顶点$v$为关节点

• biconnected graph：重连通图，没有关节点的连通图

• biconnected component：重连通分量，连通图的最大重连通 子图，即不是其他重连通分量的真子图

  • 两个重连通分量不可能共享一个以上节点，即图的一条边 不可能同时出现在两个重连通分量中 （否则两个“重连通分量”可以合并）
  • 所以可以说重连通分量是对原图的边的划分

有向图

• 强连通图：对所有不同顶点u、v，都存在u到v、v到u的路径
• strongly connected component：强连通分量，有向图的 极大连通子图

源点、汇点

• soruce：源，没有输入边的顶点
• sink：汇点，没有输出边顶点

图遍历

遍历图：实质是对每个顶点查找其邻接顶点的过程

• 具体算法参见algorithm/problem/graph

遍历方式

• BFS：Breadth First Search：广度优先搜索，类似树的先序 遍历

• DFS：Depth First Search：深度优先搜索，类似树的按层次 遍历

• 具体算法参见algorithm/problem/graph

结点处理顺序

• post-order：后序，先处理子节点，再处理当前结点
• pre-order：前序，先处理当前结点，再处理子节点

• 搜索森林中仅有一棵树时

  • 前序、后序均满足处理顺序（后序为逆处理顺序）
  • 前序、后序处理仅是处理顺序刚好相反

• 搜索森林中有多棵树时，将每棵树视为一个结点考虑

  • 每个树内前序、后序顶点处理顺序相反
  • 不同树整体前序、后序处理顺序相反
  • 此时前序不再满足处理顺序，后序仍为逆处理顺序，所以 前序不常用

• 节点处理记录方式

  • 栈：出栈顺序同记录反向
  • 队列：出队列顺序同记录顺序

总结

• Pre-Order：正前序，先当前顶点、后子顶点，队列存储

• Reverse Pre-Order：逆前序，先子顶点、后当前顶点， 栈存储

• Post-Order：正后序，先当前顶点、后子顶点，队列存储

• Reversed Post-Order：逆后序，先子顶点、后当前顶点， 栈存储，也称为伪拓扑排序

  • 可以用于得到DAG的拓扑有序序列
  • 也可以用于得到有环有向图的伪拓扑序列
    • 强连通分量整体看作结点，组成DAG
    • 各强连通分量必然可以选出某个顶点，满足在伪拓扑 序列中次序先于DAG中先驱强连通分量所有顶点
  • 用途最广
    • 有向图拓扑排序
    • Kosaraju算法中用到

BFS、DFS森林

广度优先、深度优先生成森林

• 遍历的初始顶点可以作为森林中树的根
• 遇到新未访问的顶点，将其附加为直接前趋子女
• 其实仅有树向边才是符合森林定义（其他边都只是搜索过程 中遇到）

• DFS森林中边是从左到右逐渐生成
• BFS森林中边是从上到下逐渐生成

边类型

• tree edge：树向边，连接父母、子女的边
• back edge：回边，连接非直接前驱的边
  • 对有向图包括连接父母的边
  • 对无向图不存在连接父母边
• cross edge：交叉边，连接非前驱、后继的边
• forward edge：前向边，连接非直接后代的边

边存在性

• 无向图
  • DFS森林：只可能有回边
  • BFS森林：只可能有交叉边
• 有向图
  • DFS森林：可以都有
  • BFS森林：只可能有回边、交叉边

Spanning Tree

生成树/极小连通子图：包含图中所有顶点的连通无环子图（树）

• n个顶点的生成树有且仅有n-1条边，反之不成立

• 在生成树添加一条边必定构成一个环，因为其实使得其依附的 两个顶点之间生成了第二条路径

Minimum Cost Spanning Tree

最小生成树：图的一棵权重最小的生成树（权重指所有边权重之和）

MST性质

• 若$N=(V, {E})$是连通网，U是顶点集V的非空子集，若 $(u, v), u \in U, v \in V-U$是一条具有最小权值（代价）边 ，则图中存在最小生成树包含该边

• 假设网N中最小生成树T不包含边$(u, v)$，将其加入T中

• 因为T为生成树，所以必存在边 $(u^{‘}, v^{‘}), u^{‘} \in U, v^{‘} \in V-U$，且 $u, u^{‘}$、$v, v^{‘}$之间均有路径连通

• 则删除$(u^{‘}, v^{‘})$可以消去上述回路，得到新生成树 $T^{‘}$，且代价不大于$T$，矛盾

• 存在是考虑到存在其他同权值边，若权值严格最小，则所有 最小生成树必然包含
• 依此性质生成算法参见algorithm/problems/graph

连通性

• 对图进行遍历是判断图连通性、求解连通分量的好方法

有向图

• 连通图：从图中任意顶点出发，进行深度、广度优先搜索即可 访问到图中所有顶点

  • 利用DFS生成树可以找出图的重连通分量

• 非连通图：需要从多个顶点起始进行搜索

  • 每次从新的起始点出发进行搜索过程中得到顶点访问 序列就是各个连通分量的顶点集

无向图

• 深度优先搜索是求有向图强连通分量的有效方法

• 具体算法参见algorithm/problem/graph

Directed Acycline Graph

DAG：有向无环图

• 描述含有公共子式的表达式的有效工具
  • 可以实现对相同子式的共享，节省存储空间
• 描述一项工程、系统进行过程的有效工具
  • 拓扑排序：工程能否顺利进行
  • 关键活动：整个工程完成必须的最短时间

Dependence Analysis

依赖性分析：由有向图判断、构造可行任务执行序列

Topological Sort

• 拓扑有序：由偏序得到的全序
• 拓扑排序：由偏序定义得到拓扑有序的操作

• 构造有向图中顶点的拓扑有序序列

  • 得到可行任务执行顺序

• 判断有向图AOV-网中是否存在环，即是否为DAG

  • 若图中所有顶点都在拓扑有序序列中，则有向图中不存在环

• 参见algorithm/problems/graph
• AOV网：activity on vertex network，顶点表示活动，弧 表示活动间优先关系的有向图

关键活动优化

Critical Path

关键路径：路径长度最长的路径

• 对整个AOE网，开始点到结束点的关键路径长度即为完成工程 的最短时间

• 对事件$v_i$，从起始点$v_1$到其的关键路径长度即为，以 $v_i$为尾的活动的最早开始时间

• 关键路径上的所有活动均为关键活动

  • 分析关键路径目的就是找出关键活动
  • 提高关键活动工效缩短工期

• AOE网：activity on edge network，顶点表示事件，边表示 活动持续事件的带权有向无环图

  • 一般网络中只有一个源点、汇点，表示工程开始、完成
  • 以上假设AOE网中活动可以并行进行

关键活动

• 关键活动：记$ee{ij}$为活动$a{ij}$最早开始时间、 $el{ij}$为不推迟整个工程完成前提下$a{ij}$最迟开始时间 ，称$ee{ij} = el{ij}$称为关键活动

• $el{ij} - ee{ij}$表示完成活动$a_{ij}$的时间余量

  • 提前完成非关键活动不能加快工程进度
  • 关键活动耗时一定范围变化影响工程整体完成时间

• 考虑如下事件和活动发生关系有

  $$\left \{ \begin{array}{l} ee_{ij} & = ve_{i} \\ el_{ij} & = vl_{j} - a_{ij} \end{array} \right.$$

  • $ve_i, vl_i$：事件（顶点）i最早、最晚发生的时间
  • $a{ij}$：活动$a{ij}$需要持续时间

• 对$ve_i, vl_i$，存在如下递推关系

  $$\left \{ \begin{array}{l} ve_i = \max\{ve_m + a_{mi} \}, & \forall a_{mi} \in E \\ vl_i = \max\{vl_n - a_{in} \}, & \forall a_{in} \in E \end{array} \right.$$

  则依拓扑排序可计算得$ve_i$，逆拓扑排序可计算得$vl_i$

• 参见algorithm/problems/graph
• 为求解AOE网中活动$e{ij}, l{ij}$，应该首先求出事件

Flow Network

流量网络

• 包含一个源点：物质流唯一出发点
• 包含一个汇点：物质流唯一汇聚点
• 每条有向边权重为边capacity的正整数$u_{ij}$
  • 事实上，有理数总可以通过变换变为整数，所以只要容量为 有理数就可以
  • 计算机无法真正处理无理数，无理数边权只具有理论意义

流量约束

Capacity Constraits

容量约束：通过边的流量不大于边容量$x{ij} \leqslant u{ij}$

Flow-Conservation Requirement

流量守恒要求：除源点、汇点外其余顶点只能改变流方向，进入、 流出物质总量不变，不能消耗、添加物质

• 其中$x_{ij}$表示通过边$(i,j)$的流量（传输量）
• 等式左右为进入、离开顶点i的输入、输出流总和

并且

• 流的值 = 源点输出流 = 汇点输入流
• 可通过流量守恒要求推出

最大流

最大流：分配流量网络中边权（实际流量），使得网络在满足流量 守恒、容量束情况下，最大的流的值（边容量都为正整数）

cut

割：$C(X,\bar X)$=所有头在$X$、尾在$\bar X$边集合

• $X$；包含源点、不包含汇点的顶点V的子集
• $\bar X$：$X$的补集，包含汇点
• 删除割中所有边，则不存在从源点的汇点的路径

Augmenting-Path Method

Augmenting-Path

流量增益路径：当前流情况下，可以传输更多流量、从源点到 汇点路径，考虑路径$i \rightarrow j \leftarrow k$中顶点j边

• forward edge：前向边$(i, j)$，同流量网络中边$(i, j)$ 方向相同

  • 具有正的未使用容量$r{ij} = u{ij} - x_{ij}$
  • 可以把该边流量增加最多$r_{ij}$

• backward edge：后向边$(j, k)$，同流量网络中边$(k, j)$ 方向相反

  • 具有正流量$x_{kj}$
  • 可以把该边流量减少最多$x_{kj}$

增益路径法

• 寻找网络中增益路径，设$r$为路径中各前向边未使用容量 $r{ij}$、后向边流量$x{jk}$最小值

• 每条前向边流量加r、后向边流量减r，可以得到新的可行流量， 且流量值增加r，不断迭代

• 基于边容量、流量都为正整数假设

  • r也为正整数，每次迭代流量值至少增加1

  • 流量最大值有上界为源点为起点边容量和，则增益路径法 在有限步迭代后会停止

• 联合最大流-最小割定律可以证明

  • 最终流量一定是最大化的，等于最小割容量
  • 和增量路径选择无关

• 最后一步迭代中

  • 所有已标记顶点和未标记顶点之间边就构成最小割
  • 这样边流量要么满（标记到未标记）、要么空（反）

• 增益路径法具体实现参见graph
• 算法主要问题在于如何寻找增益路径，生成路径的顺序对算法 有巨大影响

Max-Flow Min-Cut Theorem

最大流-最小割定理：网络中最大流量值等于其最小割容量

Theorem1

网络中最大流量值小于任意割容量

• 设可行流量x值为v，割$C(X, \bar_X)$容量为c

• 通过该割的流量为：$X$到$\bar_X$的流量之和与 $\bar_X$到$X$的流量之和的差值（可由流量守恒推导）

  $$v = \sum_{i \in X, j \in \bar_X} x_{ij} - \sum{j \in \bar_X, i \in X} x_{ji}$$

• 由流量非负可得

  $$v \leqslant \sum_{i \in X, j \in \bar_X} x_{ij} \leqslant \sum_{i \in X, j \in \bar_x} u_{ij}$$

  即网络上任何可行流值不能超过网络上任意割容量

  $$v \leqslant c$$

Theorem2

网络中最大流量等于最小割容量，可以使用增益路径法证明

• 设$v^{}$为通过路径增益法得到的最终流$x^{}$的值

• 对增益路径法最终流量情况下，考虑顶点集合$X^{*}$

  • 包含源点
  • 其他顶点可由源点出发，经未使用的容量大于0的前向边、 流量大于0的后向边组成路径到达

• 则汇点不属于$X^{*}$，否则存在一条流量增益路径，不是流量 增益法最终流情况

• 考虑割$C(X^{}, \bar_{X^{}})$

  • $X^{}, \bar_{X^{}}$之间任意边$(i,j)$： $x{ij} = u{ij}$，没有未使用容量

  • $\bar{X^{}}, X^{}$之间任意边$(j,i)$：$x{ji}=0$， 没有流量

  • 否则顶点j$\in X^{*}$

• 则有

  $$\begin{align}{c} v* & = \sum_{i \in X^{*}, j \in \bar_{X^{*}} x_{ij} - \sum{j \in \bar_{X^{*}, i \in X^{*}} x_{ji} \\ & = \sum_{i \in X^{*}, j \in \bar_{X^{*}}} u_{ij} - 0 \\ & = C(X^{*}, \bar_{X^{*}}) \end{align}$$

  即存在某个割容量等于流量增益法得到最终流量值