SeOpiamal静态树表的查找

静态树表的查找

9.1.3 静态树表的查找

上一小节对有序表的查找性能的讨论是在“等概率”的前提下进行的，即当有序表中各记录的查找概率相等时，按图9.2所示判定树描述的查找过程来进行折半查找，其性能最优。如果有序表中各记录的查找概率不等，情况又如何呢?

先看一个具体例子。假设有序表中含5个记录，并且已知各记录的查找概率不等，分别为p1=0.1，p2=0.2，p3=0.1，p4=0.4和p5=0.2。则对此有序表进行折半查找，查找成功时的平均查找长度为

∑PiCi = 0.1* 2+0.2* 3+0.1*1+0.4* 2+0.2* 3 = 2.3

i=1

但是，如果在查找时令给定值先和第4个记录的关键字进行比较，比较不相等时再继续在左子序列或右子序列中进行折半查找，则查找成功时的平均查找长度为

∑PiCi=0.1* 3+0.2* 2+0.1* 3+0.4*1+0.2* 2=1.8 i=1

这就说明，当有序表中各记录的查找概率不等时，按所示判定树进行折半查找，其性能未必是最优的。那末此时应如何进行查找呢? 换句话说，描述查找过程的判定树为何类二叉树时，其查找性能最佳?

如果只考虑查找成功的情况，则使查找性能达最佳的判定树是其带权内路径长度之和PH 值 n

PH=∑wihi (9-7)

i=1

取最小值的二叉树。其中：n 为二叉树上结点的个数(即有序表的长度) ；hi 为第i 个结点在二叉树上的层次数；结点的权wi=cpi(i=1，2，…，n) ，其中pi 为结点的查找概率，c 为某个常量。称PH 值取最小的二叉树为静态最优查找树(Static Optimal Search Tree)。由于构造静态最优查找树花费的时间代价较高，因此在此介绍一种构造近似最优查找树的有效算法。

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

(rl, rl+1, …, rh) (9-8)

其中 rl.key

wl, wl+1, …, wh (9-9) 现构造一棵二叉树，使这棵二叉树的带权内路径长度PH 值在所有具有同样权值的二叉树中近似为最小，称这类二叉树为次优查找树(Nearly Optimal Search Tree)。构造次优查找树的方法是：

首先在式(9-8)所示的记录序列中取第i(l≤i ≤h) 个记录构造根结点ri ，使得 h i-1

△Pi=|∑wj-∑wj| (9-10)

j=i+1 j=l

取最小值(△Pi=Min{△Pj})，然后分别对子序列{rl,rl+1, …ri-1}和{ri+1,.., rh} 两棵次优查找树，并分别设为根结点ri 的左子树和右子树。 //构造次优查找树SeOpiamal.CPP 2010.11.29 #include

#include #include #include typedef struct treenode { struct treenode *lchild,*rchild; char data; int weight; }BiTNode,*BiTree;

void SecondOptimal(BiTree &T,char R[],int sw[],int low,int high)

{ //由有序表R[low....high]及其累积权值表sw(其中sw[0]==0)递归构造次优查找树T int i=low;

int min=fabs(sw[high]-sw[low]); //给min 赋比较基数 int dw=sw[high]+sw[low-1];

for(int j=low+1;j

min=fabs(dw-sw[j]-sw[j-1]); } }

T=(BiTree)malloc(sizeof(BiTNode)); T->data=R[i]; //生成节点

if(i==low) T->lchild=NULL; //左子树为空

else SecondOptimal(T->lchild,R,sw,low,i-1); //构造左子树 if(i==high) T->rchild=NULL; //右子树为空

else SecondOptimal(T->rchild,R,sw,i+1,high); //构造右子树 }//SecondOptimal

void pre_order(BiTree &T)//前序遍历二叉树 { if(T!=NULL)

{ coutdatalchild); pre_order(T->rchild); } }

int seach_tree(BiTree &T,char key)//查找二叉树中是否存在某元素 { if(T==NULL) return 0; else

{ if(T->data==key) return 1;

else

{ if(seach_tree(T->lchild,key)||seach_tree(T->rchild,key)) return 1; //如果左右子树有一个搜索到，就返回1 else return 0; //如果左右子树都没有搜索到，返回0 } }

}

void main()

{ BiTree root=NULL;

int low=1,high=10; char *R;

int *weight,*sw;

R=(char *)malloc(high*sizeof(char)); //分配R 数组空间 for(int i=low;i

for(i=low-1;i

weight=(int *)malloc(high*sizeof(int)); //分配权数组空间 weight[0]=0; weight[1]=1; weight[2]=1; weight[3]=2; weight[4]=5; weight[5]=3; weight[6]=4; weight[7]=4; weight[8]=3; weight[9]=5;

cout

sw=(int *)malloc(high*sizeof(int));

sw[0]=0;

for(i=low;i

SecondOptimal(root,R,sw,low,high-1);//创建次优查找二叉树 cout

cout>ch;

//查找二叉树中是否存在某元素

if(seach_tree(root,ch)==1) cout

运行程序结果如下：

构造次优查找树的点R[]:

？ A B C D E F G H I 构造次优查找树的点的权值weight[]: 0 1 1 2 5 3 4 4 3 5 构造次优查找树的点累积权值sw[]: 0 1 2 4 9 12 16 20 23 28 前序遍历序列是:

F D B A C E H G I

输入要查找的元素! F yes!

例9-1 已知9个关键字的有序表及其相应权值为：

关键字 A B C D E F G H I 权值 1 1 2 5 3 4 4 3 5

则按算法9.3构造次优二叉查找树的过程中累计权SW 和△P 的值如图9.4（a ）所示，构造所得次优二叉查找树如图9.4(b)所示。

(a)

(b)

图9.4 构造次优二叉查找树示图 (a)累计权值和△P 值； (b) 次优查找树

由于在构造次优查找树的过程中，没有考察单个关键字的相应权值，则有可能出现被选为根的关键字的权值比与它相邻的关键字的权值小。此时应作适当调整：选取邻近的权值较大的关键字作次优查找树的根结点。

大量的实验研究表明，次优查找树和最优查找树的查找性能之差仅为1％~2％，很少超过3％，而且构造次优查找树的算法的时间复杂度为O (nlogn)，因此它是构造近似最优二叉查找树的有效算法。