关于次优查找树的构造刘文予解惑
====================================================
From: Wenyu Liu
Subject: Re: Fw: 请刘老师解惑
Date: 04-10-25 23:39:53
====================================================
刘玉老师,您好！
注意我们讨论的是次最优查找树，什么是次最优并没有一个严格的定义，与我们的实际工程的要求有关。
1. 调整是必须的，否则按上述的构造方法构造的查找树离次最优有距离，但是，调整的工作量不能太大，否则，我们可以直接构造最优查找树（用次最优查找树是为了降低构造最优查找树的时间复杂度），显然调整的结果与最优查找树的误差精度与时间复杂度有关，精度越高，时间复杂度越大。书上所说的“适当”比较模糊，没有统一的说法，根据实际的要求选择一个“适当”的调整标准。
2. 书上也不是标准答案，你的答案也是正确的，一个是只对根结点进行调整，书上的方法是对所有的子树的根结点进行调整，显然书上的方法精度更优，但是时间复杂度增大，具体，你的方法是O(log2n),书上的方法是O(n*log2n)，但我们注意构造次最优查找树的时间复杂度是O(n*log2n)，即我们对所有的子树的根结点进行调整不会增加构造算法的时间复杂度（会增加一些时间，如增加30％），说明对所有的子树的根结点进行调整是可行的。需强调一点，两种方法都是正确的，没有标准的答案。 检验自己得到的PH值究竟是不是最小没有意义，最小是最优查找树，已证明不可能在O(n*log2n)的复杂度下构造出。同理，精确的判知哪一步调整哪一步不调整也是没有意义的，我们已有最优的构造算法。但是我们可以讨论几种常用的调整方法以及他们的特点。
3. 我的一些想法
a）数据结构中的一些问题没有标准答案，需要根据具体的要求进行设计，很多算法时间和空间复杂度是相互制约的，一个减小，另一个会增大，这就需要我们根据实际的情况进行综合设计和平衡。这也是数据结构课程的特点。
b）算法的复杂度是非常重要的，否则，你不能得出正确的分析结果。
c）除了上面的2种调整方法，我还可以提出一种新的方法，把根结点与查找树中的最大PH值结点调整一次，他的时间复杂度是O(n),介于2种方法之间，他的精度是否在2者之间呢？你可以研究一下。
d）学生提的问题很好，如果不是已解答，可以作为考试题让他们分析，我们缺乏这类分析问题的题目！
不知回答你是否满意，如有问题，不要犹豫请提出！
刘文予
======= 2004-10-25 20:36:00 您在来信中写道：=======
>刘文予老师, 您好！
>
> 我学生提的这个问题，也是我自己
困惑的问题，一并请赐教！
>
>
>************下面是转发邮件************
>原邮件发件人名字: tsttu
>原邮件发件人地址：[email protected]
>
>>刘老师:
>> 您好!关于次优查找树的构造我有一些困惑，希望能帮忙指点一下迷津。
>> 书上说构造方法是：先取第i个记录构造根结点r(i)，使得△P(i)取最小值，然后分别
>>对子序列{r(l),...,r(i-1)}和{r(i+1),...,r(h)}构造两棵次优查找树，并分别设为根结点r(i)的左子树和右子树。[书P223]
>> 书中P224还提到：“由于在构造次优查找树的过程中，没有考察单个关键字的相应权值，则有可能出现被选为根的关键字的权值比与它相邻的关键字的权值小。此时应作适当调整：选取邻近的权值较大的关键字作次优查找树的根结点。”
>> 问：这里所说的“适当”比较模糊，有无一个较为明确的说法？
>> 严蔚敏老师的习题集里9.8题便是一例。若按P224的那段话作“全部”调整，则答案不对，PH值不是最小。若按书后标准答案，则意味着做本题过程中有的步骤要调整，而有的不要。疑问：如何精确的判知哪一步调整哪一步不调整呢？且如何检验自己得到的PH值究竟是不是最小呢？
>> 9.8 题我的解题步骤：
>> j 1 2 3 4 5 6 7 8 9 10 11 12
>> key(j) A B C D E F G H I J K L
>> W(j) 8 2 3 4 9 3 2 6 7 1 1 4
>> SW(j) 8 10 13 17 26 29 31 37 44 45 46 50
>> △P(j) 42 32 27 20 7 5 10 18 31 39 41 46
>> 根 i
>> △P(j) 9 1 6 13 21 16 8 5 13 15 20
>> 根 i i
>> △P(j) 7 2 5 8 3 5 5 3 2
>> 根 i i i
>> △P(j) 3 2 2 3 1 1
>> 根 i i i
>> △P(j) 3 3 1
>> 根 i i i
>>
>>故次优查找树为： E
>> A I
>> D H L
>> C F J
>> B G K
>>PH=134
>>
>>但标准答案是： E
>> A I
>> C H L
>> B D F J
>> G K
>>PH=133
>>
>>请刘老师解惑。谢谢。
>> 电信1班： 涂尚坦
>> 2004.10.24
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>-----------------------------------------------------------
>>网易126专业电子邮局，为您提供卓越电子邮件服务，http://www.126.com/
>>全
国最大的免费邮箱，260兆空间12兆附件，强力杀毒反垃圾，界面无广告
>
>= = = = = = = = = = = = = = = = = = = =
>
>
> 致
>礼！
>
> 刘玉
> 2004-10-25
= = = = = = = = = = = = = = = = = = = =
致
礼！
Wenyu Liu
2004-10-25
====================================================
From: tsttu
Subject: 感激涕零
Date: 04-10-26 10:16:02
====================================================
刘老师：
在这么短的时间内，收到您这么详细的解答，我感激不尽！
本以为您工作特别繁忙，所以本已做好了短期内不会收到答复的准备，但我万万没有想到，在不到一天的时间内您不仅亲自阅读了我的邮件，认真思考了我的问题，还为了我和刘文予老师一起讨论了我的问题，您这种敬业的精神，这种对学生无微不至关怀的师德，带给我的不仅仅是感激，还有自豪－－为我能在这么好的大学向这么好的老师求学而自豪！同样，刘文予老师身为课程组组长，也在第一时间对我的问题做了如此详细的分析和建议，我感动不已！
师者，不仅传之以道，而且授之以德！您的师德将会激励着我在求知的路上充满信心，大步前进！
再谢！
涂尚坦
２００４.１０.２６
-----------------------------------------------------------
网易126专业电子邮局，为您提供卓越电子邮件服务，http://www.126.com/
全国最大的免费邮箱，260兆空间12兆附件，强力杀毒反垃圾，界面无广告