最优二叉树在程序中的应用有什么？
最优二叉树在程序中的应用有什么？
程序优化杂谈——最优二叉树在程序中的应用
( 作者：mikespook |发布日期：2003-4-13|浏览次数：180)
| 关键字：程序,优化,哈夫曼,最优二叉树 |
|
首先呢，我想和大家讨论一个非常简单的问题：分类。 假设这里有100个物品。其中属于A类的物品有20个；B类10个；C类45个；D类15个；E类10个。现在要求写一个程序对这100个物品进行分类。啊！这个问题是不是很简单呢？你闭着眼睛也应该能写出来。这里我用伪C语言来写这个程序。先约定：x[0]~x[99]是这100个物品。“in”操作判断物品是否属于该类。“put”操作是将物品放入这个分类的中。 程序： 10 for(i=0;i<100;i++) 20 { 30 if(x[i] in a) 40 x[i] put a; 50 else 60 if(x[i] in b) 70 x[i] put b; 80 else 90 if(x[i] in c) 100 x[i] put c; 110 else 120 if(x[i] in d) 130 x[i] put d; 140 else 150 x[i] put e; 160 } “啊哈！多么漂亮的程序埃” 的确，这段代码从某个方面来说是非常不错的。很工整。但是这是最好的么？让我们计算一下看看。 不论如何优化“x[i] put x;”这句肯定要执行100次，因为一个物品必须放入一个分类。且只能放一次。那么能变化的就是比较的次数。先看下面这个图，是上面这段程序的一个树型结构图：  我们很容易能计算出来这个结构在进行比较的时候，需要进行275次比较。那么怎么样才能减少比较的次数呢？ 实际上这是一个权值的问题。属于A类的物品有20个；B类10个；C类45个；D类15个；E类10个。那么我们不防设A的权值为0.2，B的权值为0.1，C的权值为0.45 ，D的权值为0.15，E的权值为0.1。那么根据最优二叉树的概念，应该把权值大的深度减到最小（详细的情况请参看清华大学出版的《数据结构》，关于哈夫曼编码那部分）。根据这个原则，我们应该将B、E向下调整，而C向上调整。于是又了下面这个新的结构：  按照这个结构从新写这个程序，再运行试试？比较次数被减少到了210次。很有意思不是么？ 10 for(i=0;i<100;i++) 20 { 30 if(x[i] in c) 40 x[i] put c; 50 else 60 if(x[i] in a) 70 x[i] put a; 80 else 90 if(x[i] in d) 100 x[i] put d; 110 else 120 if(x[i] in b) 130 x[i] put b; 140 else 150 x[i] put e; 160 } 为什么会这样呢？前面我只说了怎么做，没说为什么这么做。下面我和大家一起做个简单的分析。 首先看这两段程序有什么不同的地方。 第一段程序和第二段程序唯一不同之处就是判断的顺序不同。第一段程序判断的顺序是A、B、C、D、E。而第二段程序的判断顺序是C、A、D、B、E。奇怪的顺序不是么？其实一点都不奇怪，如果你按第二种顺序排列的时候写上权值你就发现其中的奥妙了： C | A | D | B | E 0.45 | 0.2 | 0.15 | 0.1 | 0.1 是的，它的权值是从大到小排列的。 为了说明得更透彻些，下面再来分析一下程序运行的过程。 行30那段程序不论怎么调整，总是要运行100次的。而后面的程序是否执行则受前面的程序条件判断的结果影响。如果判断为真，则不执行后面的程序。如果将权值大的比较放的深度深，那么无形之中就将整棵比较树的权值加大了。反过来，整棵树的权值就校而这种优化的思想就是在这——尽量降低整体的权值。 学过数据结构的朋友一定会说：“你这个优化并不是最优二叉树。”是的，最优二叉树的结构应该是这样的：  但是程序优化有它的特殊性。如果你完全按照最优二叉树来优化，会发现判断条件非常复杂，并且判断次数没有减少(在本例中是这样，别的情况但并不一定。)。实际上是增加了程序的运行时间。 我给大家给了一个C#做的例子。大家可以比较一下之间的差异。可以到我的站上去下载 www.xxiyy.com。 |