鉴于上篇笔记写完了才发现有相当巨大的篇幅，以后的笔记以一章的每节为单位。
这一节是数据结构基础，简单介绍了树，进而讲了堆、二叉搜索树和并查集的简单使用。
数据结构里会添加一些教材的内容，权当复习。
啊我咕了这么久吗。
树和二叉树
树又称半线性结构，所以线性表显然是线性结构，图是非线性结构。树是 $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 |
|
1 | node *remove(node *p, int x) { |
STL 中提供了 set 和 map 这两种基于二叉搜索树的数据结构。实际上由于普通二叉搜索树存在退化成链表的可能性，实现好的二叉搜索树会使用一些方法来防止时间复杂度退化，其中一个方法是平衡二叉树。
平衡二叉树
显然，普通二叉查找树的结构是和元素的插入次序相关的，如果插入控制得好，比如把一个序列按照升序插入到二叉查找树里，那么最终的结构就是一棵右斜树，操作的复杂度也会退化到 $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 | int fa[100005], rank[100005], n; |
并查集的应用 食物链 (POJ 1182)
有 $N$ 只动物，编号从 1 开始。已知：
- 所有动物都是 $A$，$B$，$C$ 种类的一种
- $A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$ （明明是食物环）
关于编号为 $x$ 和 $y$ 的两个动物，按顺序给出以下两种信息，共 $K$ 条：
- $x$ 和 $y$ 属于同一物种
- $x$ 吃 $y$
这些信息有可能出错。错误信息是：和之前信息矛盾的，或编号溢出的。求错误信息的数量。
数据规模：$1 \leq N \leq 50000$，$0 \leq K \leq 100000$
题面或题目本质出现从属关系的问题一般考虑使用并查集，尤其是数据规模较大的时候。但是在这道题里存在三个种类，种类之间还有捕食关系，要仔细考虑并查集中“元素”的选择。
将元素定为动物编号显然比较难处理，因为通过并查集我们只知道两个动物是否在同一个“组”，如果把这个“组”考虑成物种的话，我们就不知道捕食关系。
考虑这样选择“元素”：每个元素是：一个编号的动物属于某一物种这个“事实”。每个编号对应三个事实，属于同一分组的两条事实代表：其中一个为真时另一个一定为真。遇到同类关系，则把两个编号的对应关系分别合并；而捕食关系，由于三个种类不必区分名称，可以循环合并一下（就说是食物环吧）。当然，在合并之前要检查这条信息是否错误。
简单数据结构写完了，下一篇是图论。希望来得及。