博客为参考《啊哈！算法》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.开启“树”之旅
树和图的区别：树其实就是不包含回路的连通无向图。
上面这个例子中左边的是一棵树，而右边的是一个图。因为左边的没有回路，而右边的存在1->2->5->3->1这样的回路。
正是因为树有着“不包含回路”这个特点，所以树就被赋予了很多特性。
- 一棵树中的任意两个结点有且仅有唯一的一条路径连通。
- 一棵树如果有n个结点，那么它一定恰好有n-1条边。
- 在一棵树中加一条边将会构成一个回路。
树中的每个点称为结点或节点。上方左边这棵树的1号结点为根结点，上方右边这棵树的3号结点为根结点。一棵树有且只有一个根结点。根结点有时候也称为祖先。此外，还有父结点和子结点。如果一个结点没有子结点，那么这个结点称为叶结点。没有父结点的结点即为根结点（祖先）。如果一个结点既不是根结点也不是叶结点，则称为内部结点。每个结点还有深度，比如4号结点（上图右）的深度是4。深度是指从根到这个结点的层数（根为第一层）。
2.二叉树
二叉树是一种特殊的树。二叉树的特点是每个结点最多有两个儿子，左边的叫做左儿子，右边的叫做右儿子，或者说每个结点最多有两棵子树。更加严格的递归定义是：二叉树要么为空，要么由根结点、左子树和右子树组成，而左子树和右子树分别是一棵二叉树。下面这棵树就是一棵二叉树。
一棵多叉树也可以转化为二叉树。二叉树中还有两种特殊的二叉树，叫做满二叉树和完全二叉树。如果二叉树中每个内部结点都有两个儿子，这样的二叉树叫做满二叉树。或者说满二叉树所有的叶结点都有同样的深度。满二叉树的严格的定义是一棵深度为$h$且有$2^h-1$个结点的二叉树：
如果一棵二叉树除了最右边位置上有一个或者几个叶结点缺少外，其他是丰满的，那么这样的二叉树就是完全二叉树。严格的定义是：若设二叉树的高度为$h$，除第$h$层外，其他各层（$1\sim h-1$）的结点数都达到最大个数，第$h$层从右向左连续缺若干结点，则这个二叉树就是完全二叉树。也就是说如果一个结点有右子结点，那么它一定也有左子结点。例如下面这三棵树都是完全二叉树。其实可以将满二叉树理解成是一种特殊的或者极其完美的完全二叉树。
将完全二叉树进行从上到下，从左到右编号。
通过上图可以发现，如果完全二叉树的一个父结点编号为$k$，那么它左儿子的编号就是$2k$，右儿子的编号就是$2k+1$。如果已知儿子（左儿子或右儿子）的编号是$x$，那么它父结点的编号就是$x/2$，注意这里只取商的整数部分。另外如果一棵完全二叉树有$N$个结点，那么这个完全二叉树的高度为$\log _2 N$，简写为$\log N$，即最多有$\log N$层结点。完全二叉树的最典型应用就是——堆。
3.堆——神奇的优先队列
堆是一种特殊的完全二叉树，就像下面这棵树一样。
其所有父结点都比子结点要小（注意：圆圈里面的数是值，圆圈上面的数是这个结点的编号）。符合这样特点的完全二叉树我们称为最小堆。反之，如果所有父结点都比子结点要大，这样的完全二叉树称为最大堆。
假如有14个数，分别是99、5、36、7、22、17、46、12、2、19、25、28、1和92，要找出这14个数中最小的数。最简单的方法就是将这14个数从头到尾依次扫一遍，用一个循环就可以解决。这种方法的时间复杂度是$O(14)$，也就是$O(N)$。
1
2
3
4
5
for(i=1;i<=14;i++)
{
if(a[i]<min)
min=a[i];
}
现在我们需要删除其中最小的数，并增加一个新数23，再次求这14个数中最小的一个数。请问该怎么办呢？只能重新扫描所有的数，才能找到新的最小的数，这个时间复杂度也是$O(N)$。假如现在有14次这样的操作（删除最小的数后再添加一个新数），那么整个时间复杂度就是$O(14^2)$，即$O(N^2)$。那有没有更好的方法呢？堆这个特殊的结构恰好能够很好地解决这个问题。
首先我们把这14个数按照最小堆的要求（就是所有父结点都比子结点要小）放入一棵完全二叉树，就像下面这棵树一样。
很显然最小的数就在堆顶，假设存储这个堆的数组叫做$h$的话，最小数就是$h[1]$。接下来，我们将堆顶部的数删除。将新增加的数23放到堆顶。显然加了新数后已经不符合最小堆的特性，我们需要将新增加的数调整到合适的位置。
向下调整！我们需要将这个数与它的两个儿子2和5比较，选择较小的一个与它交换，交换之后如下。
一直向下调整，直到符合最小堆的特性为止。
向下调整的代码如下。
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
void siftdown(int i) //传入一个需要向下调整的结点编号i，这里传入1，即从堆的顶点开始向下调整
{
int t, flag=0; //flag用来标记是否需要继续向下调整
//当i结点有儿子（其实是至少有左儿子的情况下）并且有需要继续调整的时候，循环就执行
while(i*2<=n && flag==0)
{
//首先判断它和左儿子的关系，并用t记录值较小的结点编号
if( h[i] > h[i*2] )
t=i*2;
else
t=i;
//如果它有右儿子，再对右儿子进行讨论
if( i*2+1 <= n)
{
//如果右儿子的值更小，更新较小的结点编号
if( h[t] > h[i*2+1] )
t=i*2+1;
}
//如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的
if(t!=i)
{
swap(t,i); //交换它们，注意swap函数需要自己来写
i=t; //更新i为刚才与它交换的儿子结点的编号，便于接下来继续向下调整
}
else
flag=1; //否则说明当前的父结点已经比两个子结点都要小了，不需要再进行调整了
}
}
我们刚才在对23进行调整的时候，竟然只进行了3次比较，就重新恢复了最小堆的特性。现在最小的数依然在堆顶，为2。而使用之前从头到尾扫描的方法需要14次比较，现在只需要3次就够了。现在每次删除最小的数再新增一个数，并求当前最小数的时间复杂度是$O(3)$，这恰好是$O(\log _2 14)$，即$O(\log _2 N)$，简写为$O(\log N)$。假如现在有1亿个数（即N=1亿），进行1亿次删除最小数并新增一个数的操作，使用原来扫描的方法计算机需要运行大约1亿的平方次，而现在只需要1亿乘log1亿次，即27亿次。假设计算机每秒钟可以运行10亿次，那原来的方法需要一千万秒大约115天！而现在只要2.7秒。
如果只是想新增一个值，而不是删除最小值，又该如何操作呢？即如何在原有的堆上直接插入一个新元素呢？只需要直接将新元素插入到末尾，再根据情况判断新元素是否需要上移，直到满足堆的特性为止。如果堆的大小为$N$（即有$N$个元素），那么插入一个新元素所需要的时间为$O(\log N)$。例如我们现在要新增一个数3。
向上调整至满足最小堆的特性：
向上调整的代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void siftup(int i) //传入一个需要向上调整的结点编号i
{
int flag=0; //用来标记是否需要继续向上调整
if( i==1 )
return; //如果是堆顶，就返回，不需要调整了
//不在堆顶，并且当前结点i的值比父结点小的时候就继续向上调整
while( i!=1 && flag==0 )
{
//判断是否比父结点的小
if( h[i] < h[i/2] )
swap(i, i/2); //交换它和它爸爸的位置
else
flag=1; //表示已经不需要调整了，当前结点的值比父结点的值要大
i=i/2; //这句话很重要，更新编号i为它父结点的编号，从而便于下一次继续向上调整
}
}
那如何建立堆呢？可以从空的堆开始，然后依次往堆中插入每一个元素，直到所有数都被插入（转移到堆中）为止。因为插入第i个元素所用的时间是$O(\log i)$，所以插入所有元素的整体时间复杂度是$O(N \log N)$，代码如下。
1
2
3
4
5
6
7
n=0;
for(i=1;i<=m;i++)
{
n++;
h[n]=a[i]; //或者写成scanf("%d", &h[n]);
siftup();
}
其实我们还有更快的方法来建立堆。直接把99、5、36、7、22、17、46、12、2、19、25、28、1和92这14个数放入一个完全二叉树中（这里我们还是用一个一维数组来存储完全二叉树）。
在这棵完全二叉树中，我们从最后一个结点开始，依次判断以这个结点为根的子树是否符合最小堆的特性。如果所有的子树都符合最小堆的特性，那么整棵树就是最小堆了。
首先我们从叶结点开始。因为叶结点没有儿子，所以所有以叶结点为根结点的子树都符合最小堆的特性，因此所有叶结点都不需要处理，直接跳过。从7号结点开始向下调整：
同理向下调整以6号、5号、4号结点为根的子树：
下面是已经对7号、6号、5号和4号结点为根结点的子树调整完毕之后的状态。
当然目前这棵树仍然不符合最小堆的特性，我们需要继续调整以3号结点为根的子树，即将3号结点向下调整。
同理，继续调整以2号结点为根的子树，最后调整以1号结点为根的子树。调整完毕之后，整棵树就符合最小堆的特性了。
上述流程的实现只需要两行代码：
1
2
for(i=n/2;i>=1;i--)
siftdown(i);
用这种方法来建立一个堆的时间复杂度是$O(N)$。
堆还有一个作用就是堆排序，与快速排序一样，堆排序的时间复杂度也是$O(N \log N)$。
像这样支持插入元素和寻找最大（小）值元素的数据结构称为优先队列。如果使用普通队列来实现这两个功能，那么寻找最大元素需要枚举整个队列，这样的时间复杂度比较高。如果是已排序好的数组，那么插入一个元素则需要移动很多元素，时间复杂度依旧很高。而堆就是一种优先队列的实现，可以很好地解决这两种操作。
另外Dijkstra算法中每次找离源点最近的一个顶点也可以用堆来优化，使算法的时间复杂度降到$O((M+N)\log N)$。堆还经常被用来求一个数列中第$K$大的数，只需要建立一个大小为$K$的最小堆，堆顶就是第$K$大的数。举个例子，假设有10个数，要求第3大的数。第一步选取任意3个数，比如说是前3个，将这3个数建成最小堆，然后从第4个数开始，与堆顶的数比较，如果比堆顶的数要小，那么这个数就不要，如果比堆顶的数要大，则舍弃当前堆顶而将这个数做为新的堆顶，并再去维护堆，用同样的方法去处理第5～10个数。
如果求一个数列中第$K$小的数，只需要建立一个大小为$K$的最大堆，堆顶就是第$K$小的数，这种方法的时间复杂度是$O(N \log K)$。
4.擒贼先擒王——并查集
上一节讲解了树在优先队列中的应用——堆的实现。本节讲述树的另一种用法：并查集。
在计算机科学中，并查集（disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（disjoint sets，一系列没有重复元素的集合）的合并及查询问题。并查集支持如下操作：
- 查询：查询某个元素属于哪个集合，通常是返回集合内的一个“代表元素”。这个操作是为了判断两个元素是否在同一个集合之中。
- 合并：将两个集合合并为一个。
- 添加：添加一个新集合，其中有一个新元素。添加操作不如查询和合并操作重要，常常被忽略。
由于支持查询和合并这两种操作，并查集在英文中也被称为联合-查找数据结构（union-find data structure）或者合并-查找集合（merge-find set）。
比如警方想查清楚现在有几个犯罪团伙，线索如下：
- 现在有10个强盗。
- 1号强盗与2号强盗是同伙。
- 3号强盗与4号强盗是同伙。
- 5号强盗与2号强盗是同伙。
- 4号强盗与6号强盗是同伙。
- 2号强盗与6号强盗是同伙。
- 8号强盗与7号强盗是同伙。
- 9号强盗与7号强盗是同伙。
- 1号强盗与6号强盗是同伙。
- 2号强盗与4号强盗是同伙。
有一点需要注意：强盗同伙的同伙也是同伙。那怎么查出有多少个独立的犯罪团伙呢？
第一步：我们申请一个一维数组f，我们用数组下标1～10来表示这10个强盗，用每个下标所对应的单元格来存储每个强盗的老板（即“代表元素”）是谁。
第二步：初始化。每个强盗的老板就是自己。
第三步：开始“合并同伙”。我们制定一个规则：合并之后，左边的强盗是右边强盗的老板。比如线索“1号强盗与2号强盗是同伙”，1号强盗和2号强盗合并后，1号强盗做为团伙的老板，即“靠左”原则。
接着处理线索“3号强盗与4号强盗是同伙”：
下一条线索是“5号强盗与2号强盗是同伙”，根据“靠左”原则，5号强盗会成为团伙的老板，但是2号强盗已经所属的团伙的老板是1号强盗，那该怎么办呢？我们就让1号强盗也归顺于5号强盗，让新来的5号强盗做为该团伙的老板，即“擒贼先擒王”。
我们这里把f[2]的值也改为了5，这不是必须的，只不过是为了提高今后找到团伙最高领导人（即树的祖先）的速度。
下一条线索是“4号强盗与6号强盗是同伙”，我们让6号强盗加入3号犯罪团伙，将f[6]改为3。
下一条线索是“2号强盗与6号强盗是同伙”。f[2]的值是5，f[6]的值是3。根据“靠左”原则和“擒贼先擒王”原则，让6号强盗的老板3号强盗归顺2号强盗的老板5号强盗。因此我们需要将f[3]的值改为5，另外将f[6]的值也改为5。
f[4]还是3，因为将其改成5是需要多花费时间的，这不值得。其实f[6]的值不改成5也不会影响结果。
下一条线索是“8号强盗与7号强盗是同伙”：
下一条线索是“9号强盗与7号强盗是同伙”：
下一条线索“1号强盗与6号强盗是同伙”属于是冗余线索。最后一条线索是“2号强盗与4号强盗是同伙”也是冗余线索：
很显然，结果就是这里有3个犯罪团伙。如果f[i]=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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h>
int f[1000]={0}, n, m, k, sum=0;
//这里是初始化，非常地重要，数组里面存的是自己数组下标的编号就好了
void init()
{
int i;
for(i=1;i<=n;i++)
f[i]=i;
}
//这是找爹的递归函数，不停地去找爹，直到找到祖宗为止，其实就是去找犯罪团伙的最高领导人，“擒贼先擒王”原则。
int getf(int v)
{
if(f[v]==v)
return v;
else
{
//这里是路径压缩，每次在函数返回的时候，顺带把路上遇到的人的老板改为最后找到的祖宗编号，也就是犯罪团伙的最高领导人编号。
//这样可以提高今后找到犯罪团伙的最高领导人（其实就是树的祖先）的速度。
f[v] = getf(f[v]);
return f[v];
}
}
//这里是合并两子集合的函数
void merge(int v, int u)
{
int t1, t2;
t1=getf(v);
t2=getf(u);
if(t1!=t2) //判断两个结点是否在同一个集合中，即是否为同一个祖先。
{
f[t2]=t1;
//“靠左”原则，左边变成右边的老板。即把右边的集合，作为左边集合的子集合。
//经过路径压缩以后，将f[u]的根的值也赋值为v的祖先f[t1]。
}
}
int main()
{
int i,x,y;
scanf("%d %d",&n, &m);
//初始化是必须的
init();
for(i=1;i<=m;i++)
{
//开始合并犯罪团伙
scanf("%d %d",&x, &y);
merge(x,y);
}
//最后扫描有多少个独立的犯罪团伙
for(i=1;i<=n;i++)
{
if(f[i]==i)
sum++;
}
getchar();getchar();
printf("%d\n", sum);
return 0;
}
可以输入以下数据进行验证。第一行n m，n表示强盗的人数，m表示警方搜集到的m条线索。接下来的m行每一行有两个数a b，表示强盗a和强盗b是同伙。
1
2
3
4
5
6
7
8
9
10
10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4
运行结果是：
1
3
树还有很多其他复杂的用法，比如：线段树、数状数组、Trie树（字典树）、二叉搜索树、红黑树（是一种平衡二叉搜索树）等等。
