静态搜索结构动态搜索结构散列可扩充散列ppt课件.ppt
《静态搜索结构动态搜索结构散列可扩充散列ppt课件.ppt》由会员分享,可在线阅读,更多相关《静态搜索结构动态搜索结构散列可扩充散列ppt课件.ppt(93页珍藏版)》请在三一文库上搜索。
1、静态搜索结构 动态搜索结构 散列 可扩充散列,第十章 搜索,查找 搜索,搜索结构 同一数据类型(纪录)的元素 构成的数据集合。 搜索 在数据集合中寻找满足条件的对 象(数据元素)。 关键字 数据元素中某个字段(数据项) 的值。 主关键字 唯一地表示一个纪录 。 次关键字 标识若干纪录,搜索成功 找到满足条件的数据对象 报告该对象在结构中的位置 给出整个纪录的信息 搜索失败 搜索不成功 静态搜索 搜索结构在搜索前后不发生变化 动态搜索 搜索的同时执行插入或删除 结构自行调整 提高效率 先排序,分类,编目,索引 优化结构,一、静态搜索结构,基于数组的数据表类 顺序表线性表、数组、链表。 (1) 顺
2、序搜索 从头至尾逐个比较 最快O(1) 最慢O(n) 搜索成功的等概率平均时间复杂性 O(n+1)/2) (1+2+3+n) /n=(n+1)/2 搜索失败O(n+1) 搜索的等概率平均时间复杂性 O(3(n+1)/4) 搜索成功失败各半 (1+2+n)+n(n+1) /2n =3(n+1)/4,(2)有序表的搜索,折半搜索 对已排序的搜索结构先确定中点,比较待查关键字与中点关键字的大小,反复直到成功。 求n个数据折半查找的等概率成功搜索的平均时间复杂性 1 2 3 4 5 6 7 8 9 10,1,2,2,3,3,3,3,4,4,4,1+2*2+4*3+3*4=29 O(29/10),S=1
3、+2*2+4*3+8*4+2k-1*k = 1+2*2+3*4+4*8+k*2k-1 k s =j2j-1 其中 n=2k-1 j=1,1,2,2,3,3,3,3,4,4,4,满二叉树n个数据的总查找次数:,4,4,4,4,4,满二叉树n个数据的总查找次数: k s =j2j-1 其中 n=2k-1 j=1,S=1+22+34+4*8+5*16+k2k-1 = 1+2+4+8+16+2k-1+ 2+24+38+416+(k-1)2k-1 = 1+2+4+8+16+2k-1+ 2(1+22+34+4*8+5*16+(k-1)2k-2) = 1+2+4+2k-1+2(1+2+4+2k-2)+ 22
4、(1+2+4+2k-3)+2k-2(1+2)+2k-1 =2k-1+2(2k-1-1)+22(2k-2-1)+2k-2(22-1)+ 2k-1(2-1) =k2k-(1+2+4+2k-1)=k2k-(2k-1)=(k-1)2k+1,满二叉树n个数据的总查找次数: k s =j2j-1 其中 n=2k-1 j=1,令s=f(k), k=1,2,3,4, f(1)=1 f(2)=5 f(3)=17 f(4)=49 f(5)=129 f(k)-1= 0, 22, 24, 324,27, = 021, 122, 223, 324,425 猜想 f(k)-1=(k-1)2k,k f(k)= s =j2j
5、-1 其中 n=2k-1 j=1,f(k)-1=(k-1)2k 证明 1) f(1)-1=0 2) f(k+1)-1=f(k)+(k+1)2k 1 = (k-1)2k+ (k+1)2k =2k2k=k2k+1 =(k+1-1)2k+1 S=(k-1)2k+1,满二叉树n个数据的总查找次数: k s =j2j-1 其中 n=2k-1 j=1,S= (k-1)2k+1 由 n=2k-1 得 k=log2(n+1) S=(n+1)(log2(n+1)-1)+1 = (n+1)log2(n+1)-n 满二叉树n个数据的搜索成功平均概率时间复杂性 (n+1)/n) log2(n+1)-1 当n50时 近
6、似于 log2(n+1)-1,n个元素的折半搜索,2k-1n2k+1-1 搜索成功平均概率时间复杂性 介于 log2(2k)-1 和 log2(2k+1)-1 之间 即 k-1 和 k 之间 k=log2(n+1) n个元素的折半搜索成功平均概率时间复杂性 log2(n+1)-1/2,斐波那契搜索,根据斐波那契序列的特点对有序表分割 0.618法 斐波那契序列 1 2 3 5 8 13 21 34 55f(n) f(n+2)=f(n)+f(n+1) 从20个数的数表中查找一个纪录 先找比较第13个,如果小,再比较第8个, 如果大 比较后几个数的第5个 每次都比较位于这个数列的黄金分割点0.61
7、8处,以下序列中查找元素10的过程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15,平均查找性能优于折半查找 O(log2n) 最坏情况比折半查找差,(3)静态树表的搜索,不等概率查找时折半查找不一定好, 以每点查找次数(概率)为这点的权wi 带权二叉树总路径长度 PH=wihi i PH 最小的二叉树叫静态最优二叉树 不同于霍夫曼树:每个结点都有权值,都 要查找。,E,C,A,G,B,D,H,F,I,5,4,5,1,1,2,3,4,3,A B C D E F G H I 1 1 2 5 3 4 4 3 5,PH=31+22+24+13 +53+43+33+14+54
8、=78,不是静态最优二叉树,查找次数,权值,次优查找树 Nearly Optimal Search,数据 al,al+1,ai-1,ai, ai+1,ah 权值 wl,wl+1,wi-1,wi,wi+1,wh 令 h i-1 pi= wj-wj j=i+1 j=l 取最小值: pi=minpj: ljh,以ai为根, al+1,ai-1为左子树 ai+1,ah 为右子树 构造次优查找树,i 令swi= wj , pi = swh-swi-swi-1 j=l,A B C D E F G H I wi 1 1 2 5 3 4 4 3 5 s wi 1 2 4 9 12 16 20 23 28 pi
9、 27 25 22 15 7 0 8 15 23,pi 11 9 3 1 9 8 1 7,pi 3 1 2,A B C D E F G H I wi 1 1 2 5 3 4 4 3 5,F,D,A,H,B,E,I,G,C,3,4,2,1,1,5,5,3,4,HP=4*1+5*2+3*2+ 1*3+3*3+4*3+5*3+ 1*4+2*4=7178,次最优树,平均查找次数 O(HP/swh),索引顺序表,分块有序 后一子表中的关键字都大于前一子表中的关键字,最大关键字 起始地址,索引表,索引顺序表的查找,查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中搜索,索引表,索
10、引顺序表的查找成功的平均概率时间复杂性,索引表查找时间+子表查找时间 设索引表长为s,搜索表长为n,被平均分成s块, 每块长n/s, 索引表平均查找时间 (s+1)/2 子表平均查找时间 (n/s+1)/2 (s+1)+ (n/s+1)= (s+n/s)+1 当 s=n 时 有最小值 n +1,有序索引顺序表,当索引顺序表已经排序时,子块搜索可以用折半搜索。 平均查找时间: (s+1)/2 +log2(1+n/s)-1/2 = log2(1+n/s)+s/2 索引也用折半查找,平均查找时间 log2(s+1)-1/2 +log2(1+n/s)-1/2 = log2(s+1)(1+n/s)-1
11、当s= n 时 2 log2(n +1)-1,二、动态搜索表,特点 查找过程中生成搜索表 查找失败时插入纪录 二叉搜索树 平衡二叉搜索AVL树,二叉搜索树 (二叉排序树),其左非空子树上所有结点的值都小于根结点的值 其右非空子树上所有结点的值都大于根结点的值 左右子树也是二叉搜索树,49,38,65,13,97,27,76,49,二叉搜索树的作用:排序,检索,49 38 65 97 76 13 27 49,二叉搜索树的插入过程,45 12 8 57 60 20 11 59 50 3,45,12,57,8,20,60,3,11,59,50,57 20 8 45 60 59 3 12 50 11,
12、57,20,60,8,45,11,3,12,50,59,平衡二叉树AVL树 加快查找排序的速度,定义: 左右两子树深度之差不超过1, 左子树和右子树都是平衡二叉树。,45,12,57,8,20,60,3,11,59,50,45,12,8,20,3,11,不平衡,平衡,同一个数组的二叉排序树和二叉平衡树,20 30 80 40 10 60 50 70,49,20,65,97,50,27,13,49,10,70,13,40,30,49,80,60,49,10,65,97,60,27,13,49,50,70,13,40,20,49,80,30,AVL树的结点,增加一个平衡因子,balance=hei
13、ght(right subtree)-height(left subtree),balance=1或-1,49,38,65,13,1,1,平衡因子,左重加左右转,结点p左重,还要加一个左结点 不平衡,49,38,65,13,10,p,lc,右转: 将p作lc的右子结点,49,38,65,13,10,p,lc,左重加左右转,结点p左重,还要加一个左结点 不平衡,38,13,10,40,20,p,lc,4,38,13,10,40,20,p,lc,4,右转:将p作lc的右子结点, 将lc的右子树接成p的左子树,右重加右左转,结点p右重,还要加一个右结点 不平衡,38,13,39,40,45,p,rc
14、,4,45,40,38,4,39,p,rc,13,左转:将p作rc的左子结点, 将rc的左子树接成p的右子树,左重加左的右双旋 左转再右转,结点p左重 lc的右子树加一个结点 不平衡,38,13,10,40,20,p,lc,26,np,先以lc np为轴左转,38,13,10,40,20,p,lc,26,np,再以p, np为轴右转,38,13,10,40,20,p,lc,26,np,右重加右的左双旋 右转再左转,结点p右重 rc的左子树加一个结点 不平衡,38,13,55,46,p,rc,41,np,先以rc np为轴右转,38,41,67,46,13,p,rc,55,np,再以p, np为
15、轴左转,55,38,13,67,46,np,p,41,np,67,AVL树的生成,20 30 80 40 10 60 50 70,49,10,65,60,27,13,13,40,20,49,80,30,左转,49,65,27,13,20,49,80,30,49,65,27,13,20,49,80,30,左重加左的右 左转再右转,20 30 80 40 10 60 50 70,10,60,13,40,49,65,27,13,20,49,80,30,左重加左的右 左转再右转,10,60,13,40,49,65,27,13,20,49,80,30,左转,10,60,13,40,49,65,27,13
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 静态 搜索 结构 动态 散列可 扩充 ppt 课件
链接地址:https://www.31doc.com/p-2549614.html