0%

挑战程序设计竞赛 02 章 02

鉴于上篇笔记写完了才发现有相当巨大的篇幅,以后的笔记以一章的每节为单位。

这一节是数据结构基础,简单介绍了树,进而讲了堆、二叉搜索树和并查集的简单使用。

数据结构里会添加一些教材的内容,权当复习。

啊我咕了这么久吗。

树和二叉树

树又称半线性结构,所以线性表显然是线性结构,图是非线性结构。树是 $n$ 个结点的有限集,具体来说是图的特例(即无回路的连通图,也称自由树 free tree 或有根树 rooted tree)。

  • 树的基本单位是结点
  • 当树的结点个数 $n$ 等于 $0$ 时,这棵树为空树
  • 当 $n > 1$ 时
    • 它有且仅有一个结点作为根结点
    • 根结点之外的所有结点都可以被分为若干个互不相交的有限集合,其中每个集合又是一棵树,且是根结点的子树(sub tree)

这是递归语境下树的定义。如果要把一棵树画在纸上,则“结点”就画成结点,“边”就是根结点指向其子树的根结点的线。我们讨论有序树,即根结点的子树从左到右按一个顺序排列,改换顺序将得到不同的一棵树。

树的常用术语:

术语 定义
结点的度 该结点拥有的非空子树的个数
树的度 树中各结点的度的最大值
叶子结点 leaf node 度为 0 的结点
分支结点 branch node 度非 0 的结点
(孩)子结点 child node 一个结点的子树的根结点,是该结点的子结点
(双亲)父结点 parent node 一个结点是其子结点的父结点
兄弟结点 brother node 拥有同一个父结点的子结点互为兄弟结点
路径 一个结点序列,满足:对其中任一个有后继的结点,该结点是其后继的父结点
路径长度 路径序列的长度
祖先和子孙 从一个结点到另一结点存在一条路径,则前者为后者的祖先,后者为前者的子孙
结点的层数 若规定根结点的层数为 1,对于其他任一个结点,若它在第 $k$ 层,则它的子结点在第 $k + 1$ 层
树的深度 树中所有结点的最大层数
树的宽度 树中每一层结点个数的最大值,显然不小于树的度

二叉树是这样一种树:

  • 一棵二叉树为空树,或者
  • 一棵二叉树包含一个根结点和两个不相交的子树,两个子树都为二叉树,分别称为左子树和右子树

应该注意的一点是:一棵由两个结点组成的树,在二叉树中可以是两棵树(子结点为左子树或右子树),而在树的定义中,它们都是一样的。

二叉树的常见种类:

名称 定义
斜树 一棵二叉树,所有分支结点都只有一边的子树,分为左斜树和右斜树
满二叉树 所有分支结点的度都为 2,且所有叶子结点都在同一层
完全二叉树 对一棵二叉树按层序遍历的顺序编号,任一个编号的结点位置与等深度的满二叉树中同编号的结点相同

二叉树的基本性质:

  • 度为 2 的结点个数比度为 0 的结点数少 1
  • 第 $i$ 层上至多有 $2^{i - 1}$ 个结点
  • 深度为 $k$ 的二叉树至多有 $2^k - 1$ 个结点
  • 结点数为 $n$ 的完全二叉树,深度为 $\lfloor\log_2 n\rfloor + 1$
  • 对一棵有 $n$ 个结点的完全二叉树层序编号,对一个编号 $i$,有
    • 若 $i > 1$,其父结点编号为 $\lfloor i / 2\rfloor$,否则为根结点
    • 若 $2i \le n$,则其左子结点编号为 $2i$,否则无左子节点
    • 若 $2i + 1 \le n$,则其右子结点编号为 $2i + 1$,否则无右子节点

树的存储

如果是二叉树,可以根据完全二叉树的性质来用线性表去存,但是对于稀疏的或者不够平衡的(直观地说,斜的)树而言十分浪费空间。还有一种线性表存法是,对所有结点进行编号,然后开一张表记录每个结点的父结点。

用多叉链表来存树可以说是最灵活的方法。每个结点存一个该节点的值,和若干相关结点的地址。根据相关结点的选择,可以分成几种不同的存储方法。比较常用的是二叉链表(存二叉树),每个结点存储它子结点的地址。还有“孩子兄弟”存储方法(存普通树),也是二叉链表,每个结点存储它的第一个子结点,和它右边同层的第一个结点。

二叉树的二叉链表存法还可以添加一个地址指向父结点,这样查起来会更方便。存的信息越多,往往越省时间。

优先队列和堆

利用二叉堆来实现优先队列,而二叉堆是用二叉树实现的。

优先队列

优先队列是这样一种数据结构,它可以:

  • 压入一个数值
  • 弹出一个数值,这个值是当前队列中最小的

堆的操作和性能分析

这样的一棵二叉树是(二叉)堆:

  • 子结点的值不小于父结点
  • 是完全二叉树

那么显然根结点存储着堆里最小的元素(之一)。

下面简述一下压入和弹出两个操作:

  • 压入一个值时,在堆的末尾插入该值(使堆的结点紧密排列),然后不断和相对的父结点比较,如果小于父结点则交换两个值,直到整个结构再次成为一个堆。
  • 弹出一个值时,显然是弹出根结点,接着将堆的最后一个结点移动到根上,然后不断向下交换直到再次得到一个堆。当有两个交换方向时,和较小的值交换,否则仍然有父结点大于子结点的情况出现。

时间性能上,主要开销在交换元素,而这次数取决于二叉树的高度(深度),如果一共 $n$ 个元素,那么压入和弹出都可以在 $O(\log n)$ 的时间内完成。

堆的实现

首先介绍一下线性表存储二叉树的方法。给一棵满二叉树(每个父结点都恰有两个子结点)由根开始,从左到右从上到下编号,容易发现这样的关系:一个编号为 $i$ 的结点,它的左子结点编号为 $2i + 1$,右子结点编号为 $2i + 2$。可以通过死算来得到同样的结果。

完成了这样的映射,很容易设计出线性存储二叉树的方案。

另外也可以用二叉链表的方式写,更直观一点。

STL 里的优先队列

优先队列可以自定义小顶堆和大顶堆,分别是
priority_queue<int, vector<int>, greater<int>>

priority_queue<int, vector<int>, less<int>>

实际上:
priority_queue<Type, Container, Functional>,分别代表数据类型,容器类型,比较方式,自己写的数据结构需要提供比较符的重载。

常用的方法有压入、弹出、peak 等等。

优先队列应用

优先队列关注的是一个集合中的最值,而忽略其他元素的关系。这里的忽略不代表其他元素可以瞎存。

Expedition (POJ 2431)

一辆车需要行驶 $L$ 单位的距离,每行驶 $1$ 单位距离要消耗 $1$ 单位的汽油。卡车原有 $P$ 单位的汽油。途中共 $N$ 个加油站,给出各加油站距起点的距离和可以提供的汽油总量。假设车的油箱足够大,求到终点时的最少加油次数,如不能到达则输出 $-1$。

想一下可以发现,每经过一个加油站,相当于获得了一个可以在随后任何时刻使用的流量加油包,则一旦油不够时,挑出加油包中最大的那个用掉就行了。加油包用完而未到终点时则输出 $-1$。

最吃性能的显然是“挑出最大的包”这一步。显然用大顶堆实现比较快。

再谈 Fence Repair

之前不断寻找、合并、替换的算法复杂度是二次的,利用优先队列去获得最小值,只需要 $O(n\log n)$。

二叉搜索树

Binary Search Tree,二叉搜索树,又叫二叉查找树,是一种能够较快地进行数值插入、删除和查询的数据结构。它的实现思想与二分查找类似:对于所有的结点,其值总大于左子树内所有结点的值,总小于右子树内所有结点的值。

二叉搜索树的操作和性能分析

在纸上稍微画一遍就可以发现,二叉搜索树的组织结构是一目了然的。下面来看它的插入、查找和删除的实现逻辑。

插入

在纸上,根据 BST 的结构可以很快地找到应该插入的地方。但是对于代码实现来说,只用一个指针,根据待插入元素和当前结点的大小关系去一层一层往下走,最后找到的只是一个空指针,直接分配新结点的话就会丢掉它。需要拿到父结点才可以插入。

可以用另外一个指针去记录前驱。也可以采用递归的插入方法,利用一个接收父结点地址 p 和待插入元素 x 、返回新插入结点地址的函数,从根结点开始,若 x 大于 p 的值,则以 p 的右结点为根结点递归调用。终止条件是接收到了空的指针,此时构建一个新的结点并返回其地址。

查找

查找也可以是递归的。一个接收当前结点和待查找值,返回布尔类型的函数,在接收到空指针时返回 false,接收的指针存值匹配时返回 true,然后按照大小关系递归向下查询。

删除

删除有两种写法。一种是循环删除,一种是递归删除。

循环删除的方案是:

  • 待删结点是叶子结点,则直接用空指针覆盖
  • 待删结点只有一棵子树,则用子树的根结点去向上覆盖待删结点
  • 待删结点有两棵子树,则找到左子树的最大值或右子树的最小值,用其值覆盖待删结点,再删去它。这里可以稍微递归一下。或者考虑边界条件:待删结点的左(右)子结点就是左(右)子树的最大(小)。

想一下就知道上面的操作需要待删结点的父结点,要想按值来删除,还需要做几层包装。

递归删除的方案是:

  • 待删除结点无左子树,则用右子结点覆盖
  • 待删结点的左子树无右子树,则用左子结点覆盖(这里避开了上面提到的边界条件)
  • 以上两种情况都不符合时,用左子树中最大的结点覆盖

三种操作都只会顺着树的高度走一次,因此时间复杂度是 $O(\log n)$,其中 $n$ 是结点数。

二叉搜索树的实现

列一下插入和删除的代码:

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

Node<T>* insert(Node<T>* p, T x) {
if (p == nullptr) {
Node<T>* ret = nullptr;
ret = new Node<T>;
ret->val = x;
ret->lchild = ret->rchild = nullptr;
return ret;
} else {
if (x < p->val) {
p->lchild = insert(p->lchild, x);
} else if (x > p->val) {
p->rchild = insert(p->rchild, x);
// 等于的值不插入
}
return p;
}
}
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
node *remove(node *p, int x) {
if (p == nullptr) return nullptr;
else if (x < p->val) p->lchild = remove(p->lchild, x);
else if (x > p->val) p->rchild = remove(p->rchild, x);
// 开始删除当前结点
else if (p->lchild == nullptr) {
node *q = p->rchild; // 提前保存
delete p;
return q;
} else if (p->lchild->rchild == nullptr) {
node *q = p->lchild;
q->rchild = p->rchild;
delete p;
return q;
} else {
node *q;
// 一行找到左子树最大值的父结点,操作缩在 for 循环里
for (q = p->lchild; q->rchild->rchild != nullptr; q = q->rchild);
node *r = q->rchild; // 左子树最大值结点
q->rchild = r->lchild; // 接上最大值的左子树
// 保留 p 的子树信息
r->lchild = p->lchild;
r->rchild = p->rchild;
delete p;
return r;
}
return p; // 似乎不会被执行
}

STL 中提供了 setmap 这两种基于二叉搜索树的数据结构。实际上由于普通二叉搜索树存在退化成链表的可能性,实现好的二叉搜索树会使用一些方法来防止时间复杂度退化,其中一个方法是平衡二叉树。

平衡二叉树
显然,普通二叉查找树的结构是和元素的插入次序相关的,如果插入控制得好,比如把一个序列按照升序插入到二叉查找树里,那么最终的结构就是一棵右斜树,操作的复杂度也会退化到 $O(n)$。这样的树看上去是不平衡的,它的确就叫非平衡树。
解决非平衡树的方案是,每次插入后进行一次“旋转”,来把不平衡的树变化为尽量平衡的。
定义一个结点的不平衡度为其左右子树的深度差,则不平衡度不大于 1 的情况都是可以接收的。如果插入了一个结点后,某个父结点的不平衡度超过了 1,按照插入位置在这个父结点的左/右子结点的左/右子树上,可以分为 LL、LR、RL、RR 四种情况,对应有四种旋转的方法,此处不提。

并查集 Union Find Set

并查集是一中用来管理元素分组状态的数据结构,它可以在较高的效率下实现:

  • 查询两个给定元素是否在同一组
  • 将两个给定元素所在的组合并为同一个组

需要注意的是,并查集不能用来将一个组分割。从下面的实现来看就很容易明白这个事实。

并查集的结构和实现

并查集使用树实现。若干个元素属于同一组,则从中选择一个元素作为该组的代表。如果两个元素的代表相同,则认为它们在同一组。结合树的结构考虑,把代表安排在根的位置上,其他结点向父结点查询,是比较合适的设计。

并查集的操作和性能分析

初始化

初始状态下,各个点以自己为代表,即它们互相孤立。

合并

合并这个操作需要两个参数,即两个需要合并的元素。注意合并时是将两个组都合起来,而不是增加这两个元素所属的组别(这可以通过容斥的思想解决)。所以,合并两个分组时,是将其中一个的根指向另一个根。一般不采用两个根合并到一个新建根下面的做法,这样会增加处理“非元素根”的相关流程。

查询

查询也需要两个参数。分别查到这两个元素的代表(所在树的根)并比较,若相等则属于同一组。

性能分析

理想情况下,合并和查询的复杂度应该与树的向上寻根相当。但是考虑到树退化的可能,需要进行类似“旋转”的优化。这里提供两个优化方法。

比较高度

对于每棵树,记录它的高度 rank,如果高度不同,将 rank 小的合并到 rank 大的树里,新树的 rank 即较大的那个。

路径压缩

由于并查集只需要考虑“在同一组”的关系,普通树操作里需要维护的大部分结构都可以丢弃。比如子结点不必要固定。同使用 rank 来保持树高度均衡一样,我们可以直接压缩树的高度。对于不限制子结点数量的树来说,这个操作就是:记住起始结点,并在找到根时,把起始结点直接连到根上。这样,在以后查找这个结点时,需要走过的路径至少不会比第一次长。以上操作在查找时可以顺便完成。

实现这两个优化后,并查集进行一次操作的平均复杂度是 $O(\alpha(n))$,其中 $\alpha(n)$ 是阿克曼函数的反函数(这里涉及到计算复杂度方面的知识,我也不会),这个复杂度是优于 $O(\log n)$ 的。

并查集的实现

存储结构上,我们并不需要像多叉链表那样的结构体。前面提到过,并查集只关心树内结点和根的关系,这样的映射可以直接用一维数组存储。

直接附上代码(板子)。

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
31
32
33
34
35
36
37
int fa[100005], rank[100005], n;
void init() {
for (int i = 0; i < n; ++i) {
par[i] = i; // 每个元素初始的代表是自己
rank[i] = 0; // 1 也行,只看相对高度
}
}

// 查找元素 x 所属的集合代表
int find(int x) {
if (par[x] == x) return x;
return par[x] = find(par[x]);
// 此处有一个递归,并且是简写
// 意思是一直找到 x 的根,并把 x 的父结点设为这个根
// 由于语言特性,这个表达式的值就是根的编号,直接返回
}

// 合并
void unite(int x, int y) {
// 实现时注意赋值形式和合并的关系
// 谁赋值给了谁是谁合并到谁
x = find(x), y = find(y);
if (x == y) return; // 异常处理
if (rank[x] < rank[y]) {
par[x] = y;
} else {
// rank[x] >= rank[y]
par[y] = x;
if (rank[x] == rank[y]) rank[x]++;
}
}

// 判断
bool same(int x, int y) {
// 其实可以不用写
return find(x) == find(y);
}

并查集的应用 食物链 (POJ 1182)

有 $N$ 只动物,编号从 1 开始。已知:

  • 所有动物都是 $A$,$B$,$C$ 种类的一种
  • $A$ 吃 $B$,$B$ 吃 $C$,$C$ 吃 $A$ (明明是食物环)

关于编号为 $x$ 和 $y$ 的两个动物,按顺序给出以下两种信息,共 $K$ 条:

  1. $x$ 和 $y$ 属于同一物种
  2. $x$ 吃 $y$

这些信息有可能出错。错误信息是:和之前信息矛盾的,或编号溢出的。求错误信息的数量。
数据规模:$1 \leq N \leq 50000$,$0 \leq K \leq 100000$

题面或题目本质出现从属关系的问题一般考虑使用并查集,尤其是数据规模较大的时候。但是在这道题里存在三个种类,种类之间还有捕食关系,要仔细考虑并查集中“元素”的选择。

将元素定为动物编号显然比较难处理,因为通过并查集我们只知道两个动物是否在同一个“组”,如果把这个“组”考虑成物种的话,我们就不知道捕食关系。

考虑这样选择“元素”:每个元素是:一个编号的动物属于某一物种这个“事实”。每个编号对应三个事实,属于同一分组的两条事实代表:其中一个为真时另一个一定为真。遇到同类关系,则把两个编号的对应关系分别合并;而捕食关系,由于三个种类不必区分名称,可以循环合并一下(就说是食物环吧)。当然,在合并之前要检查这条信息是否错误。

简单数据结构写完了,下一篇是图论。希望来得及。