1、概念引入
　　基于统计先验知识，我们可统计出一个数表（集合）中各元素的查找概率，理解为集合各元素的出现频率。比如中文输入法字库中各词条（单字、词组等）的先验概率，针对用户习惯可以自动调整词频&&所谓动态调频、高频先现原则，以减少用户翻查次数。这就是最优二叉查找树问题：查找过程中键值比较次数最少，或者说希望用最少的键值比较次数找到每个关键码（键值）。为解决这样的问题，显然需要对集合的每个元素赋予一个特殊属性&&查找概率。这样我们就需要构造一颗最优二叉查找树。
2、问题给出
　　n个键{a1,a2,a3......an},其相应的查找概率为{p1,p2,p3......pn}。构成最优BST,表示为T1n ，求这棵树的平均查找次数C[1, n]（耗费最低)。换言之，如何构造这棵最优BST，使得
C[1, n] 最小。
3、分段方法
　　　　动态规划法策略是将问题分成多个阶段，逐段推进计算，后继实例解由其直接前趋实例解计算得到。对于最优BST问题，利用减一技术和最优性原则，如果前n-1个节点构成最优BST，加入一个节点an&后要求构成规模n的最优BST。按 n-1, n-2 , ... , 2, 1 递归，问题可解。自底向上计算：C[1, 2]&C[1, 3] &... &C[1, n]。为不失一般性用
C[i, j] 表示由{a1,a2,a3......an}构成的BST的耗费。其中1&i &j &n。这棵树表示为Tij。从中选择一个键ak作根节点，它的左子树为Tik-1，右子树为Tk+1j。要求选择的k 使得整棵树的平均查找次数C[i, j]最小。左右子树递归执行此过程。（根的生成过程）
&4、递推计算式
　　5、基本算法如下
6、具体实现代码（其中所有数据都存放在2.txt中，其内容为：
其中5表示有5个节点，其他数据表示各个节点出现的概率；
1 #include&stdio.h&
2 #include&stdlib.h&
3 #define max 9999
4 void OptimalBST(int,float*,float**,int**);
5 void OptimalBSTPrint(int,int,int**);
6 void main()
//所有数据均从2.txt中获取，2.txt中第一个数据表示节点个数；从第二个数据开始表示各个节点的概率
point=fopen("2.txt","r");
if(point==NULL)
printf("cannot open 2.txt.\n");
fscanf(point,"%d",&num);
printf("%d\n",num);
float *p=(float*)malloc(sizeof(float)*(num+1));
for(i=1;i&num+1;i++)
fscanf(point,"%f",&p[i]);
//创建主表；
float **c=(float**)malloc(sizeof(float*)*(num+2));
for(i=0;i&num+2;i++)
c[i]=(float*)malloc(sizeof(float)*(num+1));
//创建根表；
int **r=(int**)malloc(sizeof(int*)*(num+2));
for(i=0;i&num+2;i++)
r[i]=(int*)malloc(sizeof(int)*(num+1));
//动态规划实现最优二叉查找树的期望代价求解。。
OptimalBST(num,p,c,r);
printf("该最优二叉查找树的期望代价为：%f \n",c[1][num]);
//给出最优二叉查找树的中序遍历结果；
printf("构造成的最优二叉查找树的中序遍历结果为：");
OptimalBSTPrint(1,4,r);
38 void OptimalBST(int num,float*p,float**c,int**r)
int d,i,j,k,s,
float temp,
for(i=1;i&num+1;i++)//主表和根表元素的初始化
c[i][i-1]=0;
c[i][i]=p[i];
r[i][i]=i;
c[num+1][num]=0;
for(d=1;d&=num-1;d++)//加入节点序列
for(i=1;i&=num-d;i++)
for(k=i;k&=j;k++)//找最优根
if(c[i][k-1]+c[k+1][j]&temp)
temp=c[i][k-1]+c[k+1][j];
r[i][j]=//记录最优根
for(s=i+1;s&=j;s++)
sum+=p[s];
c[i][j]=temp+
72 //采用递归方式实现最优根的输出，最优根都是保存在r[i][j]中的。。。
73 void OptimalBSTPrint(int first,int last,int**r)
if(first&=last)
k=r[first][last];
printf("%d
OptimalBSTPrint(first,k-1,r);
OptimalBSTPrint(k+1,last,r);
7、最终运行结果：
8、参考文献：
（1）算法导论
（2）数据结构 严蔚敏
（3）网上下载的一个ppt（算法设计与分析，第八章）
阅读(...) 评论()3918人阅读
Data Struct（16）
即二叉搜索树：
1.所有非叶子结点至多拥有两个儿子（Left和Right）；
2.所有结点存储一个关键字；
3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；
B-树（B树）
是一种多路搜索树（并不是二叉的）：
1.定义任意非叶子结点最多只有M个儿子；且M&2；
2.根结点的儿子数为[2, M]；
3.除根结点以外的非叶子结点的儿子数为[M/2, M]；
4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5.非叶子结点的关键字个数=指向儿子的指针个数-1；
6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] & K[i+1]；
7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1],
K[i])的子树；
8.所有叶子结点位于同一层；
如：（M=3）
B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；
B-树的特性：
1.关键字集合分布在整颗树中；
2.任何一个关键字出现且只出现在一个结点中；
3.搜索有可能在非叶子结点结束；
4.其搜索性能等价于在关键字全集内做一次二分查找；
5.自动层次控制；
由于限制了除根结点以外的非叶子结点，至少含有M/2个儿子，确保了结点的至少利用率，其最底搜索性能为O(LogN)
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[ K[i], K[i+1] )的子树（B-树是开区间）；
5.为所有叶子结点增加一个链指针；
6.所有关键字都在叶子结点出现；
如：（M=3）
B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；
B+的特性：
1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.不可能在非叶子结点命中；
3.非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；
4.更适合文件索引系统；
B+树比B-树的优势：
1 不同于B-树只适合随机检索，B+树同时支持随机检索和顺序检索，在实际中应用比较多。
2 为什么说B+树比B-树更适合实际应用中操作系统的文件索引和数据库索引？
<span style="color:#) B&#43;树的磁盘读写代价更低
B&#43;树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree（一个结点最多8个关键字）的内部结点需要2个盘块。而B&#43;树内部结点只需要1个盘快（全部关键字都在叶结点的缘故？）。当需要把内部结点读入内存中的时候，B-树就比B&#43;树多一次盘块查找时间（在磁盘中就是盘片旋转的时间）。
<span style="color:#) B&#43;树的查询效率更加稳定
由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
<span style="color:# B&#43;树和B-树最大的不同点是：
<span style="color:#）B-树的关键字和记录是放在一起的，叶子节点可以看作外部节点，不包含任何信息；B&#43;树的非叶子节点中只有关键字和指向下一个节点的索引，记录只放在叶子节点中。
<span style="color:#）在B-树中，越靠近根节点的记录查找时间越快，只要找到关键字即可确定记录的存在；而B&#43;树中每个记录的查找时间基本是一样的，都需要从根节点走到叶子节点，而且在叶子节点中还要再比较关键字。从这个角度看B-树的性能好像要比B&#43;树好，而在实际应用中却是B&#43;树的性能要好些。因为B&#43;树的非叶子节点不存放实际的数据，这样每个节点可容纳的元素个数比B-树多，树高比B-树小，这样带来的好处是减少磁盘访问次数。尽管B&#43;树找到一个记录所需的比较次数要比B-树多，但是一次磁盘访问的时间相当于成百上千次内存比较的时间，因此实际中B&#43;树的性能可能还会好些，而且B&#43;树的叶子节点使用指针连接在一起，方便顺序遍历（例如查看一个目录下的所有文件，一个表中的所有记录等），这也是很多数据库和文件系统使用B&#43;树的缘故。
是B&#43;树的变体，在B&#43;树的非根和非叶子结点再增加指向兄弟的指针；
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B&#43;树的1/2）；
B&#43;树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B&#43;树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
所以，B*树分配新结点的概率比B&#43;树要低，空间使用率更高；
BST树：二叉搜索树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
B-树（B树）：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
B&#43;树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B&#43;树总是到叶子结点才命中；
B*树：在B&#43;树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：246208次
积分：3316
积分：3316
排名：第6315名
原创：78篇
转载：13篇
评论：61条
(4)(10)(7)(11)(6)(13)(17)(20)(1)(1)(1)2504人阅读
数据结构（19）
未完成。。
在数据结构课本中，查找，作为倒数的章节介绍，不是因为它不重要，而是它本身作为一种数据结构比较简单。但实用用性较强。
按照查找的引出的先后顺序介绍：
<span style="font-family:KaiTi_GB2312; font-size:32 color:#. 静态查找(树)表
以下介绍的是有序表查找，无序表只能顺序查找
作为有序表查找的一种非常普通且实用的方法。大家并不陌生。
思想：先确定待查记录所在的范围（区间），然后逐步缩小范围找到或找不到该记录为止。如果mid对应&#20540;大于key，high = 密度-1；如果mid对应&#20540;小于key，low
= mid &#43; 1；否则找到结果。
性能分析：对于任意的n，当较大（n&50)时，假设表中每个记录的查找概率相等（1/n），则查找成功时折半查找的近&#20284;平均查找长度为=
log2(n&#43;1)-1。
斐波那契查找
原理:根据斐波那契序列的特点对表进行分割。
假设开始时数组A中记录个数比某个斐波那契数小1，即n=Fu-1，然后将给定&#20540;key和查找序列中A[Fu-1]进行比较，
若相等，则查找成功
若key & A[Fu-1]，则在A[Fu-1&#43;1]至A[Fu-1]区间的数组中进行查找；
若key & A[Fu-1]，则继续在A[0]至A[Fu-1-1]区间的数组中进行查找；
性能分析：斐波那契查找的平均性能比折半查找好，但最坏情况下的性能 (虽然仍为O(lgn)) 却比折半查找差。
小小优点：分割时只需进行加、减运算。
插&#20540;查找
原理：是根据给定&#20540;key来确定进行比较关键字A[i]的查找方法。
其中，A[l]和A[h]分别为有序表中具有最小关键字和最大关键字的下标
性能比较：它只适合于关键字均匀分布的数组，在这种情况下，对数组较长的数组来说，其平均性能比折半查找好。
由于上面讨论的查找都是等概率的查找，如果待查找数为非等概率出现，那么上述的方法并非是使平均查找长度最短
静态最优查找树（SOST）
提出背景：
性能分析：由于构造的代价比较大，达到O(n^3)
次优查找树（NOST）
提出背景：对于上述查找的所有结点来说，它们的出现是等概率的；
& & & & &&当它们被查找的概率不同时，这时原来的为了使整体的ASL(平均查找长度)最小
定义：递归定义，推到公式
构造过程：1、按照元素&#20540;大小进行排序，并记录每个元素的概率
& & & & & 2、每次选择最小的P&#20540;作为该子树的根
性能分析：
索引顺序表
提出背景：
原理：缩小区间的查找过程
性能：可以折半查找
2. 动态查找(树)表
二叉排序树或平衡二叉树-BST
提出背景：对于有序表的查找来说，在进行二分查找时，
平衡二叉查找树-AVL
提出背景：
定义：对于树中每个结点来说，它的左右子树高度差的绝对&#20540;不超过1
B树、B&#43;、B-
提出背景：
引入原因：
最优二叉树—huffman树—不是查找树的一种，可以做对比
<span style="font-family:KaiTi_GB2312; font-size:32 color:#. 哈希表
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：127426次
积分：1911
积分：1911
排名：第13312名
原创：55篇
转载：34篇
评论：41条
(1)(2)(11)(24)(8)(5)(12)(1)(2)(2)(5)(12)(5)各种查找方法比较_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
各种查找方法比较
上传于||文档简介
&&折&#8203;半&#8203;查&#8203;找&#8203;法&#8203;、&#8203;平&#8203;衡&#8203;二&#8203;叉&#8203;树&#8203;查&#8203;找&#8203;法&#8203;、&#8203;B&#8203;-&#8203;树&#8203;查&#8203;找&#8203;法&#8203;三&#8203;种&#8203;算&#8203;法&#8203;查&#8203;找&#8203;效&#8203;率&#8203;比&#8203;较
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
下载文档到电脑，查找使用更方便
还剩13页未读，继续阅读
你可能喜欢搜索树_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
||文档简介
总评分4.7|
浏览量65717
&&山&#8203;东&#8203;大&#8203;学&#8203;软&#8203;件&#8203;学&#8203;院&#8203;
&#8203;
&#8203;数&#8203;据&#8203;结&#8203;构&#8203;、&#8203;算&#8203;法&#8203;与&#8203;应&#8203;用&#8203;课&#8203;程&#8203;
&#8203;
&#8203;教&#8203;学&#8203;专&#8203;用&#8203;演&#8203;示&#8203;文&#8203;稿&#8203;
&#8203;
&#8203;配&#8203;套&#8203;机&#8203;械&#8203;工&#8203;业&#8203;出&#8203;版&#8203;社&#8203;权&#8203;威&#8203;教&#8203;材&#8203;使&#8203;用
大小：2.62MB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢