0%

写在前面

莫里斯遍历(Morris Traversal)是一种时间复杂度为O(n),空间复杂度为O(1),且不改变树的结构的二叉树遍历算法。

阅读全文 »

写在前面

假如有一个由若干村庄组成的小镇,现在需要修建一条能够连接所有村庄的路,如何才能在达到目的的条件下使修路的成本最小?这个问题实际上就是图的最小生成树(MinimumSpanningTree)问题。

阅读全文 »

写在前面

打开高德地图,查找从A地点到B地点的地铁线路图时,结果页面会有“时间最短”,“价格最低”,“步行最少”等选项。如果把地铁站点看作图的顶点,地铁站之间的连接看作边并且边的权重是地铁经过这条边时需要的时间或者票价的话,就可以把地铁线路的查找抽象为一个图的最短路径问题。
即:在网络(带权图)中,求两个不同顶点之间的所有路径中,边的权值和最小的那条路径。这条路径就叫最短路径(Shortest Path),这条路径的起点叫做源点(Source),路径的最后一个顶点叫做终点(Destination)
最短路径问题不是一个孤立的问题,它是一系列问题的集合,可以分为单源最短路径问题多源最短路径问题

阅读全文 »

巴芬岛附近的一群独角鲸,加拿大努纳武特 (© Eric Baccega/Minden Pictures)

阅读全文 »

写在前面

图的遍历就是把图中的每个顶点不重复地访问一遍,它可以用来解决很多图的问题。

阅读全文 »

写在前面

现实世界中很多事物往往不是线性的一对一关系,还有许多问题是多对多的关系。如地图,互联网等等,为了抽象表示这些关系以便于处理这些网状拓扑的问题,聪明的科学家发明了(Graph)这种数据结构。

阅读全文 »

写在前面

编码

计算机能够直接读取的数据是一串二进制数,人类能够直接读取的数据是各种字符。为了能够在计算机中储存字符,聪明的科学家发明了各种编码(encode)方式将字符编码到二进制数。比如众所周知的ASCII编码,就是一套基于拉丁语字母的编码方式。它的每个字符由8 bits二进制编数码而成,因此也是一种等长码
考虑这样一种情形:在一篇若干字符组成的文章中,各个字符出现的频率一般是不同的。假如我们可以设计出一种不等长编码,让出现频率较高的字符使用更短的编码,出现频率较低的字符使用较长的编码,这样可以实现对文章的无损压缩。
哈夫曼编码就是这样一种压缩编码。

哈夫曼树(Huffman Tree)

考虑下面这种判定树:

1
2
3
4
5
6
7
8
9
10
11
if(num<60){
return 1;
}else if(num <70){
return 2;
}else if(num<80){
return 3;
}else if(num<90){
return 4;
}else{
return 5;
}

如果对小规模的学生成绩进行5分制取整,可以使用上面这段愚蠢的程序。如果要处理的是较大规模的数据,那么上面的判断过程还有优化的空间。
根据上面的判断过程,对于60以下的数据,需要判断一次,60-70的数据,需要判断两次,70-80的数据,需要判断三次。。。。假如要处理的数据集对不同分段的数据有个出现频率的信息,比如:

数据段 <60 60-70 70-80 80-90 >90
频率 0.05 0.15 0.4 0.3 0.1

那么上面的判断过程平均判断次数为:

根据上面的频率表可以查看出,70-90的占比较大,而他们需要判断3,4次。如果让占比较大的只判断一次,而让占比较小的<60分段判断4次,似乎可以减少平均判断次数,提高效率。例如改进为如下判断:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(num<80){
if(num<70){
if(num<60){
return 1;
}else{
return 2;
}
}else{
return 3;
}
}else{
if(num<90){
return 4;
}else{
return 5;
}
}

则平均判断次数为:次,优化了不少。这就是哈夫曼树的思想:根据元素出现的频率构造搜索树。

带权路径长度(WPL)

假设二叉树有n叶子节点,每个叶子节点的权值为,从根节点到每个叶子节点的长度为,则每个叶子节点的带权路径和就是
哈夫曼树就是WPL最小的二叉树,又叫最优二叉树。

阅读全文 »