优化调整次优查找树的探讨

宋景平

(扬州职业大学，江苏扬州 225009)

查找是计算机软件设计的一种重要操作，简单比对查找常常会占有整个软件设计工作的25%。如何查找才能使得查找的总次数更少一直是软件设计人员孜孜以求的。查找分为查找成功(数据表中存在这个关键字等于给定值的记录)［1］和查找不成功(数据表中不存在这个关键字等于给定值的记录)［2］。对于大部分查找一般采用哈希(Hash)散列方法，能够有效地降低查找总次数。而等概率的有序表采用折半查找［3］，查找性能最优。如果对于查找非等概率的有序表采用折半查找，其查找性能未必最好。查找成功的判定树是带权路径之和PH值

其中:n为二叉树上的结点个数;Wi为(i=1，2，…，n)结点的权;Di为(i=1，2，…，n)第 i个结点在二叉树上的层次数。

由于构造静态最优查找树需要花费相当高的时间代价。计算机资源就是时间和空间，耗费过多的时间用于构造静态最优查找树，不符合软件设计减少软件运行时间和节省软件占用空间的理念。故转而构造时间代价较少的次优查找树［4］。次优查找树查找性能只比最优查找树差1%～2%，很少差3%以上。

1 次优查找树概念

次优查找树，它或者是一棵空树，或者是具有下列性质的二叉树:

(1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;

(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;

(3)它的左、右子树也分别为二叉排序树。

次优查找树的查找过程类似折半查找，首先将给定值KEY与根结点关键字相比，若相等，则查找成功，该结点的记录即为所求;否则根据给定值KEY小于或大于根结点关键字而分别在左子树或右子树继续查找直至查找成功或查找不成功为止。这种查找比较的关键字个数不超过树的高度。构造次优查找树的方法如下:

已知一个按关键字有序的记录序列

其中 RL.key＜RL+1.key＜ … ＜RH.key与每个记录相对应的权值为

具体方法:首先在式(1)所示的记录序列中取第i(l≤i≤h)个记录构造根记录使得

然后分别对子序列{RL，RL+1，…，Ri－1} 和{Ri+1，Ri+2，…，RH}构造两棵次优查找树，并且分别设为的左子树和右子树。

2 优化实例和计算

2.1 仅考虑查找成功的次优查找树

例1:已知含有7个关键字的有序表及其相应权值表(见表1)，关键字ASCII码:C＜F＜I＜L＜P＜S＜W，为一非等概率有序表。按照式(3)的方法构造次优查找树。

表1 含有7个关键字的有序表及其相应权值表

按照式(3)的方法构造得到如图1经典次优查找树，查找成功的总次数PHS1=(3)×1+(4+5)×2+(24+40+21+36)×3=384。

人工优化处理后得如图2优化调整次优查找树，查找成功的总次数PHS2=(40)×1+(24+36)×2+(4+21)×3+(3+5)×4=267。

图1 经典次优查找数

图2 优化调整的次优查找树

两种次优查找树的总查找次数PHS1=384和PHS2=267可以相差很大。优化调整后次优查找树优越性明显。我们当然选择更少的(次优查找树)，但是不能选择最少的(静态最优查找树)，花费时间代价太大。

这种次优查找树的人工调整应遵循两个原则:

(1)最先访问的结点应是访问概率较大的靠近中央的结点;

(2)每次访问应使结点两边尚未访问的结点的被访概率之差尽可能相等。

如果结点个数较少，可以凭经验而为之;如果结点个数较多，则需要采用类似构造Huffman树的理念进行构造这棵次优查找树。即权重的结点尽量靠近树根，仍然保持有序表。

2.2 考虑查找成功和查找不成功次优查找树

考虑等概率查找不成功，如图3经典等概率查找不成功(^表示查找不成功)所示。查找不成功的总次数为

考虑等概率查找不成功，如图4调整后等概率查找不成功所示。

PHL3=32和PHL4=34相差不大。考虑非等概率查找不成功，则如图5非等概率查找不成功经典次优查找树、图6非等概率查找不成功优化调整次优查找树所示。

图3 经典等概率查找不成功次优查找树

图4 优化调整后等概率查找不成功的次优查找树

例2 已知含有7个关键字的有序表(表1)和8个区间查找不成功的表(表2)，区间ASCII码:″＜C″＜″C—F″＜″F—I″＜″I—L″＜″L—P″＜″P—S″＜″S—W″＜″S—W″＜″＞W″并且它们的查找概率不相等。以7个关键字构造次优查找树。

表2 8个查找不成功的区间相应权值表

把查找成功关键字权值累加 WS=24+4+40+3+21+5+36=133，把查找不成功关键字权值累加WL=15+20+12+9+11+8+10+30=115，则总查找权值W=WS+WL=248。

非等概率查找不成功的总次数的计算就是用权值乘以次优查找树的对应层次的累加和。

计算图5的平均查找长度ASL5:

计算图6的平均查找长度ASL6:

看到ASL6小于ASL5。优化调整次优查找树效果非常明显。

图5 非等概率查找不成功经典次优查找树

图6 非等概率查找不成功调整后次优查找树

3 结论

对于查找成功概率不等的有序表和对于查找不成功概率不等的有序表使用次优查找树能够最大节省总的查找次数。灵活地采用构造类似Huffman树的理念进行优化调整次优查找树可以降低查找总次数，科学地计算平均查找长度ASL。

［1］黄刘生.数据结构［M］.合肥:经济科学出版社，1999.

［2］李春葆.数据结构教程［M］.2版.北京:清华大学出版社，2007.

［3］陈小平.数据结构［M］.南京:南京大学出版社，1997.

［4］严蔚敏，吴伟民.数据结构:C语言版［M］.北京:清华大学出版社，2007.