当前位置：文档之家 › 最优查找树-实验报告

最优查找树-实验报告

  • 格式：doc
  • 大小：37.00 KB
  • 文档页数：8

计算机算法设计与分析实验报告实验名称：最优树查找班级：08211306姓名：刘宇轩学号：08211312一、一般原理二叉排序树（Binary Sort Tree）又称二叉查找树。

它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；问题描述给定一个有序序列K={k1<k2<k3<,……,<kn}和他们被查询的概率P={p1,p2,p3,……,pn}，要求构造一棵二叉查找树T，使得查询所有元素的总的代价最小。

对于一个搜索树，当搜索的元素在树内时，表示搜索成功。

当不在树内时，表示搜索失败，用一个“虚叶子节点”来标示搜索失败的情况，因此需要n+1个虚叶子节点{d0<d1<……<dn}。

其中d0表示搜索元素小于k1的失败结果，dn表示搜索元素大于kn的失败情况。

di（0<i<n）表示搜索节点在ki和k(i+1)之间时的失败情况。

对于应di的概率序列是Q={q0,q1,……,qn}。

二、算法的复杂度下面是对于查找期望代价的解释：对于键值ki, 如果其在构造的二叉查找树里的深度（离开树根的分支数）为depthT(ki)，则搜索该键值的代价= depthT(ki) +1（需要加上深度为0 的树根节点）。

由于每个键值被查找的概率分别为pi，i=1,2,3…,n。

在二叉树中T内搜索一次的期望代价为：E[T] = (depth(ki)+1)*pi //对每个i=1~n，搜索成功情况+ (depth(di)+1)*qi //对每个i=0~n，搜索失败情况时间复杂度1、穷举穷举构造最优二叉查找树，其实就是这样的一个问题：给一个拥有n 个数的已排序的节点，可以将其构造成多少种不同的BST（用来找到一个最优的二叉查找树）？设可以构造成T(n)个，那么枚举每一个元素作为根节点的情况，当第一个元素作为根节点时，其余n-1 个构成右子树，无左子树，是n-1 情况时的子问题，共T(n-1)种；当第二个元素作为根节点时，左子树有1 个元素，右子树有n-2 个元素，根据乘法原理共有T(1)T(n-2)种情况……依此类推得到：T(n)= T(0)T(n-1) + T(1)T(n-2) + T(2)T(n-3) + ...... + T(n-2)T(1) + T(n-1)T(0)；此外，有T(0)=T(1)=1。

下面来求解T(n)：定义函数f(x) = T(0) + T(1)*x + T(2)*x2 + ......那么有：f(x)2 = (T(0)2) + (T(0)T(1) + T(1)T(0)) ·x + (T(0)T(2) + T(1)T(1) + T(2)T(0)) ·x2 + ......= T(1) + T(2) ·x + T(3) ·x2 + ......= (f(x) - T(0)) / x= (f(x) - 1) / x这样解方程得到f(x) = [1 - (1 - 4x)1/2] / 2x右边进行泰勒展开，再与定义式比较最终得到：T(n) = (2n)! / (n!(n+1)!)然后根据Stirling 公式：n! ～(2πn)1/2*(n/e)n于是有(2n)!/n!(n+1)!～(4n1/2*2n2n)/(2n1/2*nn*(2(n+1))1/2*(n+1)n)～4n*(n+1)-3/2*(n/(n+1))n ～4n*n-3/2因此最后得到穷举方法构造最优二叉查找树的时间复杂度：T(n) = Ο(4n*n-3/2)2、递归实际上左右子树是互不影响的，不需要穷举所有左右子树的组合，所以不需要用乘法原理，加法原理就可以了，这样式子变为：T(n) = T(0) + T(n-1) + T(1) + T(n-2) + T(2) + T(n-3) + ...... + T(n-2) + T(1) + T(n-1) + T(0)= 2(T(0) + T(1) + T(2) + ...... + T(n-1))= 3T(n-1)所以得到T(n) = O(3n)，还是指数级的一个算法三、动态规划上面得到指数级算法的原因在于，计算了很多重复的子树情况，一些子树的查找代价被计算了很多遍；而一棵树如果是最优二叉搜索树，那么要么它是空树，要么它的左、右子树也是最优二叉搜索树，因此只需要将子树的查找代价记录下来，采用记忆化搜索或者是自底向上的动态规划的方法，虽然需要消耗一定的空间，但可以把时间复杂度从指数级降到多项式级，这些空间消耗也是可以接受的。

步骤一：寻找最优子结构。

一个最优二叉树的子树必定包含连续范围的关键字ki~kj，1<=i<=j<=n，同时也必须含有连续的虚叶子节点di-1~dj。

如果一棵最优二叉查找树T有一棵含有关键字ki~kj的子树T'，那么，T'也是一棵最优查找树，这通过剪贴思想可以证明。

现在开始构造最优子结构：在ki~kj中，选定一个r,i<=r<=j，使以kr为根，ki~k(r-1)和k(r+1)~kj为左右孩子的最优二叉树。

注意r=i 或者r=j的情况，表示左子树或右子树只有虚叶子节点。

步骤二：一个递归解定义e[i,j]为一棵包含关键字ki~kj的最优二叉树的期望代价。

当j=i-1时没有真实的关键在，只有虚叶子节点d(i-1)。

于是：当j=i-1时，e[i,i-1]=q(i-1)。

当j>=i时，需要选择合适的kr作为根节点，然后其余节点ki~K(r-1)和k(r+1)~kj构造左右孩子。

这时要考虑左右孩子这些节点成为一个节点的子树后，它的搜索代价的变化：根据E[T]的计算，得知它们的期望代价增加了“子树中所有概率的总和”w。

w[i,j] = pl // 对每个l=i~j+ql //对每个l=i-1~j于是当j>=i时，e[i,j]=pr + (e[i,r-1]+w[i,r-1])+(e[r+1,j]+w[r+1,j]) = e[i,r-1] + e[r+1,j]+w[i,j];步骤三：计算最优二叉树的期望代价e[i,j] = q(i-1) //如果j=i-1min(e[i,r-1] + e[r+1,j]+w[i,j])//如果i<=j，其中i<=r<=j w[i,j] = q(i-1) // 如果j=i-1w[i,j]=w[i,j-1]+pj+qj //如果i<=j四、算法实现#include <iostream>using namespace std;#define MAX_COUNT 100#define MAX_NUM 65536//p中为有序关键字k1到k5的搜索概率，k1<k2<k3<k4<k5double p[MAX_COUNT] = {0.22 , 0.13 , 0.03 , 0.26 , 0.36};double q[MAX_COUNT] = {0.04 , 0.06 , 0.04 , 0.06 , 0.09};void optimal_bst(double e[][MAX_COUNT] ,int root[][MAX_COUNT],double w[][MAX_COUNT],int n) {int i =0,j=0;//针对左或右孩子为空树情况初始化for(i = 1;i<=n+1;i++){e[i][i-1] = q[i-1];w[i][i-1] = q[i-1];}int l = 0;/*计算顺序如下：根据计算式：e[i,j] = e[i,r-1]+e[r+1,j首先计算节点个数为1的最优二叉树的代价e[1,1],e[2,2]……接着计算节点个数为1的最优二叉树的代价e[1,2],e[2,3]…………最后计算结点个数为n的最优二叉树的代价e[1,n]，利用之前保存的较少结点最优二叉树的结果。

*/for(l = 1;l<=n;l++){for(i = 1;i<=n-l+1;i++){j = i+l-1;e[i][j] = MAX_NUM;w[i][j] = w[i][j-1] + p[j]+q[j];for(int r = i;r<=j;r++){double t = 0;t = e[i][r-1]+e[r+1][j] + w[i][j];if(t<e[i][j]){e[i][j]= t;root[i][j] = r;}}}}}int main(){double e[MAX_COUNT][MAX_COUNT];int r[MAX_COUNT][MAX_COUNT];double w[MAX_COUNT][MAX_COUNT];optimal_bst(e,r,w,5);for(int i =1;i<=6;i++) {for(int j = 0;j<=5;j++){cout << r[i][j] << " ";}cout << endl;}system("pause");return 0;}五、实验总结通过这次试验，使得我对最优查找树重新进行了认识与更加深入的了解。

虽然以往在数据结构的课程中曾接触过类似内容，但是当时并没有深究。

在一开始理解中，感觉最优查找树与哈弗曼树十分相似。

但经过仔细的比对，发现二者还是有很大的差别的，最大的不同就是最优查找树要求左叶子的值必须比右叶子小，通过这一个研究对比，我对最有查找树的理解又上升了一个层次。

合集下载

二叉树的建立与先序,中序,后序,层次遍历,图的深度优先搜索和广度优先搜索 实验报告

二叉树的建立与先序,中序,后序,层次遍历,图的深度优先搜索和广度优先搜索 实验报告

树和图的遍历实验报告2011-4-9实验题目：树和图的遍历实验目的：1.实现二叉树的建立与先序，中序，后序，层次遍历2.选择建立图的类型；根据所选择的类型用邻接矩阵的存储结构构建图；对图进行深度优先搜索和广度优先搜索；实验内容:一、算法描述：（1）二叉树的建立要建立一棵树就要有根节点和两棵子树。

两棵子树的建立同样需要这样的过程。

建立二叉树的过程也是遍历树的过程，实验要求以前序遍历的方式输入数据，因此我们也应按前序遍历的顺序，动态申请存储空间的方式建立这棵树并返回根节点的指针。

BiTNode *CreateBiTree(BiTNode *T){char ch;if((ch=getchar())==' ') T=NULL;else if(ch!='\n'){if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))exit(1);T->data=ch;T->lchild=CreateBiTree(T->lchild);T->rchild=CreateBiTree(T->rchild);}return T;}（2）二叉树的遍历遍历作为二叉树所有操作的基础，因此我把它放在二叉树建立的前面。

前序遍历：即按照根节点，左子树，右子树的顺序访问。

具体操作：遇到节点，立即打印根节点的值，然后访问左子树，再访问右子树。

对左子树和右子树的访问也进行相同的操作。

void PreOrderTraverse(BiTree T){if(T){putchar(T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}同理，易得中序遍历，后序遍历的操作。

//中序遍历二叉树void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);putchar(T->data);InOrderTraverse(T->rchild);}}//后序遍历二叉树void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);putchar(T->data);}}层次遍历：先访问的节点，其孩子节点也必然优先访问，这就用到了队列的思想。

动态规划-最优二叉搜索树

动态规划-最优二叉搜索树

动态规划-最优⼆叉搜索树摘要： 本章介绍了⼆叉查找树的概念及操作。

主要内容包括⼆叉查找树的性质，如何在⼆叉查找树中查找最⼤值、最⼩值和给定的值，如何找出某⼀个元素的前驱和后继，如何在⼆叉查找树中进⾏插⼊和删除操作。

在⼆叉查找树上执⾏这些基本操作的时间与树的⾼度成正⽐，⼀棵随机构造的⼆叉查找树的期望⾼度为O(lgn)，从⽽基本动态集合的操作平均时间为θ(lgn)。

1、⼆叉查找树 ⼆叉查找树是按照⼆叉树结构来组织的，因此可以⽤⼆叉链表结构表⽰。

⼆叉查找树中的关键字的存储⽅式满⾜的特征是：设x为⼆叉查找树中的⼀个结点。

如果y是x的左⼦树中的⼀个结点，则key[y]≤key[x]。

如果y是x的右⼦树中的⼀个结点，则key[x]≤key[y]。

根据⼆叉查找树的特征可知，采⽤中根遍历⼀棵⼆叉查找树，可以得到树中关键字有⼩到⼤的序列。

介绍了⼆叉树概念及其遍历。

⼀棵⼆叉树查找及其中根遍历结果如下图所⽰：书中给出了⼀个定理：如果x是⼀棵包含n个结点的⼦树的根，则其中根遍历运⾏时间为θ(n)。

问题：⼆叉查找树性质与最⼩堆之间有什么区别？能否利⽤最⼩堆的性质在O(n)时间内，按序输出含有n个结点的树中的所有关键字？2、查询⼆叉查找树 ⼆叉查找树中最常见的操作是查找树中的某个关键字，除了基本的查询，还⽀持最⼤值、最⼩值、前驱和后继查询操作，书中就每种查询进⾏了详细的讲解。

（1）查找SEARCH 在⼆叉查找树中查找⼀个给定的关键字k的过程与⼆分查找很类似，根据⼆叉查找树在的关键字存放的特征，很容易得出查找过程：⾸先是关键字k与树根的关键字进⾏⽐较，如果k⼤⽐根的关键字⼤，则在根的右⼦树中查找，否则在根的左⼦树中查找，重复此过程，直到找到与遇到空结点为⽌。

例如下图所⽰的查找关键字13的过程：（查找过程每次在左右⼦树中做出选择，减少⼀半的⼯作量）书中给出了查找过程的递归和⾮递归形式的伪代码：1 TREE_SEARCH(x,k)2 if x=NULL or k=key[x]3 then return x4 if(k<key[x])5 then return TREE_SEARCH(left[x],k)6 else7 then return TREE_SEARCH(right[x],k)1 ITERATIVE_TREE_SEARCH(x,k)2 while x!=NULL and k!=key[x]3 do if k<key[x]4 then x=left[x]5 else6 then x=right[x]7 return x（2）查找最⼤关键字和最⼩关键字 根据⼆叉查找树的特征，很容易查找出最⼤和最⼩关键字。

最优二叉搜索实验

最优二叉搜索实验

最优二叉搜索树实验一、实验目的求二叉搜索树最小平均路长二、实验内容设 S={x1, x2, ···, xn} 是一个有序集合，且x1, x2, ···, xn 表示有序集合的二叉搜索树利用二叉树的顶点存储有序集中的元素，而且具有性质：存储于每个顶点中的元素x 大于其左子树中任一个顶点中存储的元素，小于其右子树中任意顶点中存储的元素。

二叉树中的叶顶点是形如(xi, xi+1) 的开区间。

在表示S的二叉搜索树中搜索一个元素x，返回的结果有两种情形：(1) 在二叉树的内部顶点处找到： x = xi(2) 在二叉树的叶顶点中确定： x∈ (xi , xi+1)三、实验步骤构建最优二叉树，递归计算最优值，构造最优解，求得最小平均路长四、实现提示Java运行Java Application 以下代码public class TwoTree {public void TwoSearchTree(float[] a,float[] b,float[][] m,int[][] s,float[][] w){int n=a.length-1;for(int i=0;i<=n;i++){w[i+1][i]=a[i];m[i+1][i]=0;s[i+1][i]=0;}for(int r=0;r<n;r++){for(int i=1;i<=n-r;i++){int j=i+r;int i1=s[i][j-1]>i?s[i][j-1]:i;int j1=s[i+1][j]>i?s[i+1][j]:j;w[i][j]=w[i][j-1]+a[j]+b[j];m[i][j]=m[i][i1-1]+m[i1+1][j];s[i][j]=i1;for(int k=i1+1;k<=j1;k++){float temp=m[i][k-1]+m[k+1][j];if(temp<m[i][j]){m[i][j]=temp;s[i][j]=k;}}m[i][j]+=w[i][j]; }}}public void backtrace(int[][] s,int n,int i,int j,int p,String str){ int k=s[i][j];if(k>0){if(p==0){System.out.println("root is:"+k);}else{System.out.println(str+" of "+p+" is "+k+"; and (i:j) is "+i+":"+j);}int t=k-1;if(t>=i&&t<=n)backtrace(s,n,i,t,k,"left");t=k+1;if(t<=j)backtrace(s,n,t,j,k,"right");}}public static void main(String[] args) {float a[] = {0.15f,0.5f,0.05f,0.05f};float b[] = {0.00f,0.5f,0.1f,0.05f};int n=a.length-1;float[][] m=new float[n+2][n+2];int[][] s=new int[n+2][n+2];float[][] w=new float[n+2][n+2];TwoTree bi = new TwoTree();bi.TwoSearchTree(a, b, m, s, w);System.out.println("二叉搜索树最小平均路长为："+m[1][n]);bi.backtrace(s, n, 1, n, 0, "0");}}实验结果：二叉搜索树最小平均路长为：2.3root is:1right of 1 is 2; and (i:j) is 2:3right of 2 is 3; and (i:j) is 3:3五、思考与提高无。

最优二叉树检索树动态规划算法分析

最优二叉树检索树动态规划算法分析

最优二叉树检索树动态规划算法分析最优二叉树，也被称为Huffman树，是一种特殊的二叉树，用于优化数据的检索过程。

动态规划算法被广泛应用于解决最优二叉树的构建问题。

在本文中，我们将分析最优二叉树的动态规划算法，并探讨其时间复杂度、空间复杂度以及应用场景。

一、最优二叉树的定义和性质1.最优二叉树的叶子节点存储着需要检索的数据元素；2.最优二叉树的非叶子节点存储着计算概率权值的中间结果；3.最优二叉树中每个非叶子节点的左子树和右子树的平均检索时间之差不超过1二、动态规划算法基本思路1.首先，对于给定的n个数据元素的集合，需要计算每个元素的概率权值p[i]和检索频率f[i]；2. 然后，定义一个二维数组dp来记录子问题的最优解，其中dp[i][j]表示从第i个元素到第j个元素的最优二叉树的平均检索时间；3. 接下来，使用一个三维数组root来记录每个子问题的最优解对应的根节点，在构建最优二叉树时需要使用；4. 最后，通过填充dp数组和root数组的方式，逐步解决子问题，得到最优二叉树。

三、最优二叉树动态规划算法实现1. 初始化dp数组和root数组：- 设置一个二维数组dp和一个三维数组root，大小均为n+2；- dp[i][j] = 0，表示从第i个元素到第j个元素的最优二叉树的平均检索时间初始化为0；- root[i][j] = 0，表示从第i个元素到第j个元素的最优解的根节点初始化为0。

2. 填充dp数组和root数组：- 根据子问题求解的方式，逐步计算dp[i][j]和root[i][j]的值，其中i<=j；- 外层循环从j=1到n，内层循环从i=j到i=1，依次填充dp[i][j]和root[i][j]的值；- 填充时，通过遍历所有可能的根节点位置k，计算dp[i][j]和root[i][j]的值；- 具体计算方式为dp[i][j] = min{dp[i][k-1] + dp[k+1][j] +Σp[i][j]}；- 同时，记录根节点root[i][j] = k。