宋景平

(扬州职业大学，江苏扬州 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小于或大于根结点关键字而分别在左子树或右子树继续查找直至查找成功或查找不成功为止。……