“最优二叉搜索树”上机报告

1、.“最优二叉搜索树”上机报告1 问题描述和分析设Sx1,x2,xn是有序集，且x1<x2<.<xn，表示有序集S的二叉搜索树利用二叉树的结点存储有序集中的元素。它具有下述性质：存储于每个结点中的元素x大于其左子树中任一结点所存储的元素，小于其右子树中任一结点所存储的元素。二叉树的叶结点是形如(xi,xi+1)的开区间，在表示S的二叉搜索树中搜索元素x，返回的结果有两种情况：(1) 在二叉搜索树的内结点中找到xxi(2) 在二叉搜索树的叶结点中确定x(xi,xi+1)设在第(1)中情形中找到元素xxi的概率为bi；在第(2)种情形中确定x(xi,xi+1)的概率为ai。其中约定

2、x0=，xn+1=。显然有 ai0, 0in; bj0, 1jn, ai+bj=1(a0,b1,a1,.,bn,an)称为集合S的存取概率分布。在表示S的二叉搜索树T中，设存储元素xi的结点深度为ci；叶结点(xi,xi+1)的结点深度为dj，则pbi(1+ci)+ ajdj表示在二叉搜索树T中进行一次搜索所需要的平均比较次数，p又成为二叉搜索树T的平均路长。在一般情况下，不同的二叉搜索树的平均路长是不相同的。最优二叉搜索树问题是对于有序集S及其存取概率分布(a0,b1,a1,.,bn,an)，在所有表示有序集S的二叉搜索树中找到一棵具有最小平均路长的二叉搜索树。2 问题的分解二叉搜索树T的一

3、棵含有结点xi,.,xj和叶结点(xi-1,xi),.(xj,xj+1)的子树可以看作是有序集xi,.,xj关于全集合(xi-1,xi,.,xj,xj+1)的一棵二叉搜索树，其存取概率为以下的条件概率： bk=bk/wij, ikj; ah=ah/wij, i-1hj其中wijai-1+bi+bj+aj, 1ijn。3 问题的分解具有最优子结构性质证明：设Tij是有序集xi,.,xj关于存取概率(ai-1,bi,.,bj,aj)的一棵最优二叉搜索树，其平均路长为pij。Tij的根结点存储元素xm，其左右子树Tl和Tr的平均路长分别为pl和pr。由于Tl和Tr中结点深度为它们在Tij中的结点深度

4、减1，故有wi,jpi,j=wi,j+wi,m-1pl+wm+1pr 由于Tl是关于集合xi,.,xm+1的一棵二叉搜索树，故plpi,m-1，若plpi,m-1，则用Ti,m-1替代Tl 可得到平均路长比Tij 更小的二叉搜索树。这与Tij 是最优二叉搜索树矛盾。故Tl 是一棵最优二叉搜索树。同理可证Tr 也是一棵最优二叉搜索树。 因此，最优二叉搜索树问题具有最优子结果性质。4 规划方程最优二叉搜索树Tij 的平均路长为pij，则所求的最优值为p1,n 。由最优二叉搜索树问题的最优子结构性质可建立计算pij 的递归式如下： wi,jpi,j=wi,j+minwi,k-1pi,k-1+wk+1

5、,jpk+1,j ikj 初始时，pi,i-10 , 1in记wi,jpi,j 为m(i,j)，则m(1,n)= w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为： m(i,j)=wi,j+min m(i,k-1)+ m(k+1,j) ikj m(i,i-1)=0 1in据此，可得出解最优二叉搜索树问题的动态规划算法。5 算法设计(递归和非递归)【动态规划】子问题的求解：非递归：void obst(float *a,float *b,int n,float *m,int *s,float *w)for(int i=0;i<=n;i+)wi+1i=ai;mi+1i=0;

6、for(int r=0;r<n;r+)for(int i=1;i<=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij=mi+1j;sij=i;for(int k=i+1;k<=j;k+)float t=mik-1+mk+1j;if(t<mij)mij=t;sij=k;mij+=wij;递归：double obst(double *a,double *b,int i,int j)if(mij>=0)return mij;if(j=i-1)wij=ai;mij=0;return mij;wij=wij-1+aj+bj;mij=obst(a,b,

7、i+1,j);sij=i;for(int k=i+1;k<=j;k+)double t=obst(a,b,i,k-1)+obst(a,b,k+1,j);if(t<mij)mij=t;sij=k;mij+=wij;return mij;构造最优解：void traceback(int i,int j,int *s)if(i-1=j)return;traceback(i,sij-1,s);traceback(sij+1,j,s);cout<<sij<<ends;完整的程序实现：data.txt：110.03 00.02 0.030.05 0.030.02 0.0

8、80.05 0.100.07 0.050.02 0.060.08 0.020.07 0.030.06 0.030.08 0.02最优二叉搜索树.cpp：#include "iostream.h"#include "make2db.h"#include "fstream.h"int *s;double *w,*m;/非递归void obst(double *a,double *b,int n,double *m,int *s,double *w)int i1,j1;for(int i=0;i<=n;i+)wi+1i=ai;mi+1

9、i=0;si+1i=0;for(int r=0;r<n;r+)for(int i=1;i<=n-r;i+)int j=i+r;i1=sij-1>i?sij-1:i;j1=si+1j>i?si+1j:j;wij=wij-1+aj+bj;mij=mii1-1+mi1+1j;sij=i1;for(int k=i1+1;k<=j1;k+)double t=mik+1+mk+1j;if(t<=mij)mij=t;sij=k;mij+=wij;/*void obst(double *a,double *b,int n,double *m,int *s,double *w

10、)for(int i=0;i<=n;i+)wi+1i=ai;mi+1i=0;for(int r=0;r<n;r+)for(int i=1;i<=n-r;i+)int j=i+r;wij=wij-1+aj+bj;mij=mi+1j;sij=i;for(int k=i+1;k<=j;k+)double t=mik-1+mk+1j;if(t<mij)mij=t;sij=k;mij+=wij;/递归double obst(double *a,double *b,int i,int j)if(mij>=0)return mij;if(j=i-1)wij=ai;mij=

11、0;return mij;wij=wij-1+aj+bj;mij=obst(a,b,i+1,j);sij=i;for(int k=i+1;k<=j;k+)double t=obst(a,b,i,k-1)+obst(a,b,k+1,j);if(t<mij)mij=t;sij=k;mij+=wij;return mij;*/void traceback(int i,int j,int *s)if(i-1=j)return;traceback(i,sij-1,s);traceback(sij+1,j,s);cout<<sij<<ends;void main()in

12、t n;double *a,*b;int k=5;ifstream fin("data.txt");fin>>n;make2DArray(w,n+2,n+2);make2DArray(m,n+2,n+2);make2DArray(s,n+2,n+2);a=new double n+1;b=new double n+1; for(int i=0;i<n;i+)fin>>ai>>bi;for(int l=0;l<n;l+)for(int i=0;i<n;i+)mli=0;for(int j=0;j<n;j+)for(i

13、nt i=0;i<n;i+)sij=0;obst(a,b,n,m,s,w);/obst(a,b,1,n);traceback(1,n,s);cout<<endl;运行结果：最优的搜索路径：1 2 3 4 5 6 7 8 9 11 10【数据结构】tnode.h：#ifndef Tnode#define Tnodetypedef char DataType;typedef struct tnodeDataType data;tnode *left,*right;TNode;void SetTNode(TNode *root,DataType item);TNode *GetTN

14、ode(DataType item,TNode *left,TNode *right);void SetTNode(TNode *root,DataType item)root->data=item;root->left=NULL;root->right=NULL;TNode *GetTNode(DataType item,TNode *left,TNode *right)TNode *ptr;ptr=(TNode *)malloc(sizeof(TNode);ptr->data=item;ptr->left=left;ptr->right=right;re

15、turn (ptr);#endifbstree.h：#include"tnode.h"typedef structTNode *root;int size;BSTree;void DeleteTree(TNode *root);void SetBST(BSTree *T);void FreeBST(BSTree *T);int BSTSize(BSTree *T);TNode *GetRoot(BSTree *T);int BSTEmpty(BSTree *T);TNode *BSTLocate(BSTree *T,DataType item);void BSTInsert

16、(BSTree *T,DataType item);void BSTDelete(BSTree *T,DataType item);void clearBST(BSTree *T);void DeleteTree(TNode *root)if(root=NULL)return;if(root->left!=NULL)DeleteTree(root->left);if(root->right!=NULL)DeleteTree(root->right);free(root);void SetBST(BSTree *T)T->root=NULL;T->size=0

17、;void FreeBST(BSTree *T)DeleteTree(T->root);int BSTSize(BSTree *T)return (T->size);TNode *GetRoot(BSTree *T)return (T->root);int BSTEmpty(BSTree *T)if(T->size=0)return (1);return (0);TNode *BSTLocate(BSTree *T,DataType item)TNode *t;t=T->root;while(t!=NULL)if(item=t->data)break;if(

18、item<t->data)t=t->left;elset=t->right;return (t);void BSTInsert(BSTree *T,DataType item)TNode *t,*p,*n;n=GetTNode(item,NULL,NULL);if(T->size=0)T->root=n;T->size+;return;t=T->root;p=NULL;while(t!=NULL)p=t;if(item<t->data)t=t->left;elset=t->right;if(item<p->da

19、ta)p->left=n;elsep->right=n;T->size+;void BSTDelete(BSTree *T,DataType item)TNode *t,*p,*r,*pr;t=T->root;p=NULL;while(t!=NULL)if(item=t->data)break;elsep=t;if(item<t->data)t=t->left;elset=t->right;if(t=NULL)return;if(t->left=NULL)if(p=NULL)T->root=t->right;elsep-&

20、gt;right=t->right;free(t);elsepr=t;r=t->left;while(r->right!=NULL)pr=r;r=r->right;t->data=r->data;if(pr=t)pr->left=r->left;elsepr->right=r->left;free(r);T->size-;void clearBST(BSTree *T)DeleteTree(T->root);T->root=NULL;T->size=0;printq.h：#include "iostr

21、eam.h"#include "stdlib.h"typedef structPDateType *data;int max;int front,rear,size;PQueue;void SetPQueue(PQueue *Q,int n);void FreePQueue(PQueue *Q);int PQSize(PQueue *Q);int PQEmpty(PQueue *Q);int PQFull(PQueue *Q);PDataType PQGetData(PQueue *Q,int pos);void PQInsert(PQueue *Q,PDataT

22、ype item);PDataType PQDelete(PQueue *Q);void ClearPQueue(PQueue *Q);void SetPQueue(PQueue *Q,int n)Q->data=(PDataType *) malloc(n *sizeof(PDataType);if(Q->data=NULL)cout<<"overflow!"exit(1);Q->max=n;Q->front=0;Q->rear=0;Q->size=0;void FreePQueue(PQueue *Q)free(Q->

23、;data);int PQSize(PQueue *Q)return (Q->size);int PQEmpty(PQueue *Q)if(Q->size=0)return (1);return (0);int PQFull(PQueue *Q)if(Q->size=Q->max)return (1);return (0);PDataType PQGetData(PQueue *Q,int pos)if(Q->size=0)cout<<"Queue is Empty!"<<endl;exit(1);return (Q-&

24、gt;dataQ->front);void PQInsert(PQueue *Q,PDataType item)if(Q->size=Q->max)cout<<"Queue is full!"<<endl;exit(1);Q->dataQ->rear=item;Q->rear=(Q->rear+1)%Q->max;Q->size+;PDataType PQDelete(PQueue *Q)PDataType item;if(Q->size=0)cout<<"Deleti

25、ng from an empty queue!"<<endl;exit(1);item=Q->dataQ->front;Q->front=(Q->front+1)%Q->max;Q->size-;return (item);void ClearPQueue(PQueue *Q)Q->front=0;Q->rear=0;Q->size=0;print.h：#include "conio.h"#include "printq.h"#include "tnode.h"

26、;typedef structTNode *ptr;int xindent,ylevel;PDataType;void PrintTree(TNode *root,int screenwidth)int level=1,offset=screenwidth/2;PDataType p,c;PQueue Q;if(root=NULL)return;SetPQueue(&Q,50);p.ptr=root;p.xindent=offset;p.ylevel=level;PQInsert(&Q,p);while(!PQEmpty(&Q)p=PQDelete(&Q);go

27、toxy(p.xindent,p.ylevel);cout<<(p.ptr->data);if(p.ylevel!=level)level+;offset=offset/2;if(p.ptr->left!=NULL)c.ptr=p.ptr->left;c.ylevel=p.ylevel+1;c.xindent=p.xindent-offset/2;PQInsert(&Q,c);if(p.ptr->right!=NULL)c.ptr=p.ptr->right;c.ylevel=p.ylevel+1;c.xindent=p.xindent+offs

28、et/2;PQInsert(&Q,c);FreePQueue(&Q);主函数：bst.cpp：#include "print.h"#include "iostream.h"void main(void)int i;char test50;BSTree T;SetBST(&T);cout<<"input data"<<endl;gets(test);for(i=0;testi!='0'i+)BSTInsert(&T,testi);PrintTree(GetRoot(

29、&T),80);cout<<"Press any key and find"<<endl;getch();TNode *BSTLocate(&T,'D'); PrintTree(GetRoot(&T),80);getch();FreeBST(&T);6 算法复杂度分析a). 二叉搜索树的定义：（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3）它的左、右子树也分别为二叉排序树在随机的情况下，二叉查找树的平均查找长度

30、和logn是等数量级的b). 上述的动态规划算法中用到3个二维数组m，s和w，故所需的空间为O(n2)，算法的主要计算量主要在于计算min m(i,k-1)+ m(k+1,j)，对于固定的r，它需要计算的时间为O(j-i+1)=O(r+1)，因此算法所耗费的总时间为O(r+1)=O(n3) 0rn-1,1in-r。但事实上，在上述算法中可以证明 min m(i,k-1)+ m(k+1,j) (ikj)min m(i,k-1)+ m(k+1,j) (sij-1ksi+1j) 而改进后算法obst所需的计算时间为O(n2)，所需的空间为O(n2)。 改进后的算法如下：void obst(float

31、 *a,float *b,int n,float *m,int *s,float *w)int i1,j1;for(int i=0;i<=n;i+)wi+1i=ai;mi+1i=0;si+1i=0;for(int r=0;r<n;r+)for(int i=1;i<=n-r;i+)int j=i+r;i1=sij-1>i?sij-1:i;j1=si+1j>i?si+1j:j;wij=wij-1+aj+bj;mij=mii1-1+mi1+1j;sij=i1;for(int k=i1+1;k<=j1;k+)int t=mik+1+mk+1j;if(t<=mi

32、j)mij=t;sij=k;mij+=wij;c) 二叉搜索树是改进的双向链表，其中每个结点的值不小于左孩子的值，不大于右孩子的值。二叉搜索树可显著改善搜索性能，找到一个数据的路径最长不超过树的深度，而在二叉搜索树上进行查找时的平均路长与二叉树的形态有关，搜索性能最优的是完全二叉树。设二叉搜索树有n个结点，当为完全二叉树时，其平均查找性能最佳为log2n，当退化为一棵单支树时，二叉搜索树时通过把一个有序表的n个结点依次搜索，平均查找性能最差为(n+1)/2d).二叉搜索树的期望耗费：1搜索成功与不成功的概率：2二叉搜索树的期望耗费：有n个结点的二叉树的期望耗费为：穷举搜索法的时间复杂度为指数级

33、：e). 最优二叉搜索树的搜索效率对于有n个关键码的集合，其关键码有n!种不同的排列，可构成的不同二叉搜索树有棵，而评价这些二叉搜索树，可以用树的搜索效率来衡量。例如，已知关键码集合 a1, a2, a3 = do, if, to ，对应的搜索概率为 p1=0.5, p2=0.1, p3=0.05, 在各个搜索不成功的间隔内搜索概率又分别为 q0=0.15, q1=0.1, q2=0.05, q3=0.05。可能的二叉搜索树如下所示。 (a) (b) (c)(d)(e)在二叉搜索树中：表示内部结点，包含了关键码集合中的某一个关键码；表示外部结点，代表了造成搜索失败的各关键码间隔中的不在关键码集合中的关键码。在每两个外部结点之间必然存在一个内部结点。设二叉树的内部结点有 n 个，外部结点有 n+1 个。如果定义每个结点的路径长度为该结点的层次，并用 I 表示所有 n 个内部结点的路