《静态搜索结构动搜索结构散列可扩充散列ppt课件》由会员分享，可在线阅读，更多相关《静态搜索结构动搜索结构散列可扩充散列ppt课件（93页珍藏版）》请在金锄头文库上搜索。
1、n n静态搜索结构n n动态搜索结构n n散列n n可扩充散列查找 搜索搜索结构 同一数据类型（纪录）的元素 构成的数据集合。搜索 在数据集合中寻找满足条件的对 象（数据元素）。关键字 数据元素中某个字段（数据项） 的值。主关键字 唯一地表示一个纪录 。次关键字 标识若干纪录 搜索成功 找到满足条件的数据对象 报告该对象在结构中的位置 给出整个纪录的信息搜索失败 搜索不成功静态搜索 搜索结构在搜索前后不发生变化动态搜索 搜索的同时执行插入或删除 结构自行调整提高效率 先排序，分类，编目，索引 优化结构一、静态搜索结构 基于数组的数据表类 顺序表线性表、数组、链表。 (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 1012233334441+2*2+4*3+3*4=29 O(29/10) S=1+2*2+4*3+8*4+2k-1*k
3、= 1+2*2+3*4+4*8+k*2k-1 k s =j2j-1 其中 n=2k-1 j=11223333444满二叉树n个数据的总查找次数：44444满二叉树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(1+2+4+2k-3)+2k-2(1+2)+2k-1 =2k-1+2(2
4、k-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-1 其中 n=2k-1 j=1 f(k)-1=(k-1)2k证明 1) f(
5、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时 近似于 log2(n+1)-1n个元素的折半搜索2k-1n2k+1-1搜索成功平均概率时
6、间复杂性 介于 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.618处 以下序列中查找元素10的过程1 2 3 4 5 6 7 8 9 10 11 12 13 14 15平
7、均查找性能优于折半查找 O(log2n) 最坏情况比折半查找差（3）静态树表的搜索不等概率查找时折半查找不一定好，以每点查找次数（概率）为这点的权wi带权二叉树总路径长度 PH=wihi iPH 最小的二叉树叫静态最优二叉树不同于霍夫曼树：每个结点都有权值，都要查找。ECAGBDHF I545112343A B C D E F G H I1 1 2 5 3 4 4 3 5PH=31+22+24+13+53+43+33+14+54=78不是静态最优二叉树查找次数权值次优查找树 Nearly Optimal Search数据 al,al+1,ai-1,ai, ai+1,ah权值 wl,wl+1,w
8、i-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 5s wi 1 2 4 9 12 16 20 23 28 pi 27 25 22 15 7 0 8 15 23 pi 11 9 3 1 9 8 1 7pi 3 1 2 A B C D E F G H I wi 1 1 2 5 3 4 4 3 5FDAHB
9、EIGC342115534HP=4*1+5*2+3*2+ 1*3+3*3+4*3+5*3+ 1*4+2*4=7178次最优树平均查找次数 O(HP/swh)索引顺序表 分块有序 后一子表中的关键字都大于前一子表中的关键字22 48 86 1 7 132212138920334244382448605874498653 最大关键字 起始地址索引表索引顺序表的查找 查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中搜索22 48 86 1 7 132212138920334244382448605874498653索引表索引顺序表的查找成功的平均概率时间复杂性 索引表查找
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当s= n 时 2 log2(n +1)-1二、动态搜索表特点
11、 查找过程中生成搜索表 查找失败时插入纪录 二叉搜索树 平衡二叉搜索AVL树二叉搜索树二叉搜索树 （二叉排序树）（二叉排序树） 其左非空子树上所有结点的值都小于根结点的值 其右非空子树上所有结点的值都大于根结点的值 左右子树也是二叉搜索树4938651397277649二叉搜索树的作用：排序，检索49 38 65 97 76 13 27 49二叉搜索树的插入过程二叉搜索树的插入过程45 12 8 57 60 20 11 59 50 345125782060311595057 20 8 45 60 59 3 12 50 11572060845113125059平衡二叉树AVL树 加快查找排序的速
12、度定义： 左右两子树深度之差不超过1， 左子树和右子树都是平衡二叉树。4512578206031159504512820311不平衡平衡同一个数组的二叉排序树和二叉平衡树20 30 80 40 10 60 50 704920659750271349107013403049806049106597602713495070134020498030AVL树的结点增加一个平衡因子 left data balanceFactor rightbalance=height(right subtree)-height(left subtree)balance=1或-149386513 1 1平衡因子左重加左右
13、转结点p左重，还要加一个左结点 不平衡4938651310 p lc右转：将p作lc的右子结点4938651310 p lc左重加左右转结点p左重，还要加一个左结点 不平衡3813104020plc 43813104020plc 4右转：将p作lc的右子结点, 将lc的右子树接成p的左子树右重加右左转结点p右重，还要加一个右结点 不平衡3813394045prc 4454038439prc13左转：将p作rc的左子结点, 将rc的左子树接成p的右子树左重加左的右双旋 左转再右转结点p左重 lc的右子树加一个结点 不平衡3813104020plc26np先以lc np为轴左转3813104020
14、plc26np再以p, np为轴右转3813104020plc26np右重加右的左双旋 右转再左转结点p右重 rc的左子树加一个结点 不平衡38135546prc41np先以rc np为轴右转3841674613prc55np再以p, np为轴左转5538136746npp41np67AVL树的生成20 30 80 40 10 60 50 70491065602713134020498030左转49652713204980304965271320498030左重加左的右左转再右转20 30 80 40 10 60 50 70106013404965271320498030左重加左的右左转再右转
15、106013404965271320498030左转106013404965271320498030右转20 30 80 40 10 60 50 7010601340496527132049803010601340496527132049803013701350AVL树的高度设AVL树高度为h, 这棵树至少多少结点？设至少有nh个结点n0=0, n1=1 , n2=2,nh+1=nh+nh-1+1,nh+1+1=nh+1+nh-1+1,令 fh= nh+1, 则 f0=1, f1=2 , fh+1=fh+fh-1 nh = fh-1 nh=(51/2)*(1+ 51/2)/2)h+3 -1n个
16、结点的AVL树的高度h至多是多少？ n=(51/2)*(1+ 51/2)/2)h+3 -1 (n+1)/(51/2)=(1+ 51/2)/2)h+3 log2 (n+1)-log251/2= (h+3 )(log2 (1+ 51/2)/2) log2 (1+ 51/2)/2)0.694 h+3= (log2 (n+1)-log251/2)/0.694 h(3/2) log2 (n+1)-1练习一. 画出以下输入所对应AVL树： 1）R,O,T,A,R,Y,C,L,U,B 2）60，25，7，99，15，3，10 38，59，62，34二. 分别给出这两棵树的前序，中序，后序遍历输出三、高度为5
17、的AVL树至少几个节点。 15个节点的AVL树至多多高？二叉搜索树的查找分析平均等概率查找时间(1+2+2+3+3+3)/6=14/6451257820604512820311(1+2+3+4+5+6)/6=7/2随机二叉搜索树等概率平均查找时间 P(n)2(1+1/n)lnn O(log2n)最坏 O(n/2)平衡二叉搜索AVL树的查找分析求含有n个关键字的AVL树的最大深度？设深度h的AVL树的最小结点数为Nh N0=0, N1=1, N2=2 Nh= Nh-1+ Nh-2+1 Nh+1= Nh-1+1+ Nh-2+1 令 F(h)= Nh+1， 则 F(h)=F(h-1)+F(h-2)N
18、hNh-1Nh-2深度h的AVL树的最小结点数Nh F(h)= Nh+1， F(h)=F(h-1)+F(h-2)F(h)是斐波那契数列 F(1)=1 F(2)=2 F(3)=3 F(4)=5 F(5)=8 N1=0, N2=1, N3=2, N4=4, N5=7, N6=12, 平衡二叉搜索AVL树的查找分析设 n个结点的AVL树的最大深度为h， 则 Nh=n F(h)=n+1 可以得到h. h就是最大查找次数 等概率平均查找成功时间复杂性O(log2n)B-树 平衡的多路搜索树 B-树的定义 空树 或 m叉树1)每个结点至多有m棵子树，2)如根结点不是叶，至少有两棵子树，3)除根之外，所有非
19、终端结点至少有m/2 棵子树 ,本节中记为m/2, m=3时 称为2-3树4)所有的非终端结点含有信息 (n,A0,K1,A1,K2,Kn,An) m/2-1个关键字5) 所有叶结点都在同一层次 ，叫做失败结点。 所有的非终端结点含有信息 n : 有n+1棵子树， K1K2Kn 关键字有序序列, 指针Ai-1指向子树中结点的关键字小于Ki, nA0K1A1K2KnAn 1 35 1 18 2 43 78 1 111 271 391 99347 53FFFFFFFFFFF 1 35 1 18 2 43 78 1 111 271 391 99347 53FFFFFFFFFFFB-树的搜索过程 检索
20、结点53每增加一个关键字增加一个结点最底层空结点有n+1个B-树的查找分析n个关键字，m阶B-树的最大深度h, 深度h的m阶B-树的最少结点数=n, 设第i层最少结点数Ni N1=1, N2=2, N3=2 m/2 N4= 2 m/22, N5= 2m/23 Nh= 2m/2h-2 Nh+1= 2m/2h-1 底层叶结点都是空结点 n+1Nh+1 Nh+1= 2m/2h-1 n+1 h-1 logm/2(n+1)/2) h logm/2(n+1)/2)+1n个结点的B-树的最大查找次数 为 hm/2 (logm/2(n+1)/2)+1)m/2 O(log2n)B-树的插入先从底层以大小增加一个
21、关键字 1. 结点中的关键字不超过m时完成。 2.结点中的关键字等于m时： 将该结点分成左右两个结点 中间一个关键字上升至双亲结点 重复2.直至根 1 35 1 18 2 43 78 1 111 271 391 99347 53FFFFFFFFFFF增加一个关键字60插入底层 1 35 1 18 2 43 78 1 391 99347 5360FFFFFFF增加一个关键字60将53上移结点分裂 1 35 1 18 2 43 53 78 1 391 99147FFFFFF增加一个关键字601 60FF再将53上移结点分裂 1 35 53 1 18 2 43 1 78 1 391 99147FFF
22、FFF增加一个关键字601 60FFB-树的删除找到要删除的关键字所在结点，删除。若这个结点是最下层结点，并且其中关键字数不少于m/2-1删除完成。若删除的是非终端结点中的关键字Ki，以指针Ai所指子树的最小关键字Y代替Ki,删除Y.重复直至叶结点若这个结点是最下层结点，但是其中关键字数不少于m/2-1，删除完成。 若这个结点是最下层结点，但是其中关键字数少于m/2-1，1.若该结点的左右兄弟结点中有一个关键字数大于m/2-1，则将其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。2.若该结点的左右兄弟结点的关键字数
23、都等于m/2-1，则将其与一个兄弟结点合并，从双亲结点下移一个关键字被删除关键字的位置。3. 重复2。 1 35 53 1 18 2 43 1 78 1 391 99147FFFFFF删除一个关键字531 60 65FFF 1 35 78 1 18 2 43 1 1 391 99147FFFFFF删除一个关键字531 60 65FFF关键字78上移 1 35 78 1 18 2 43 1 99 1 391147FFFFFF删除一个关键字531 60 65FFF关键字99上移 1 35 78 1 18 2 43 1 65 1 391 99147FFFFFF删除一个关键字531 60FF关键字65
24、上移，99下移， 1 35 65 1 18 2 43 1 78 1 391 99147FFFFFF删除一个关键字531 60FF关键字65继续上移，与78交换，删除完成 1 35 78 1 18 2 43 1 1 391 99147FFFFFF删除一个关键字531 60FF关键字78上移 1 35 53 1 18 2 43 1 78 1 391 99147FFFFFF删除一个关键字531 60FF 1 35 78 1 18 2 43 1 99 1 391147FFFFFF删除一个关键字531 60FF关键字99上移 1 35 78 1 18 2 43 1 1 39147FFFF删除一个关键字5
25、31 60 99FF两个结点合并，关键字99下移F 1 35 1 18 2 43 78 1 39147FFFF删除一个关键字531 60 99FF两个结点合并，关键字78下移F 1 35 1 18 2 43 60 1 39147FFFF删除一个关键字531 78 99FF关键字78继续下移，与60交换FB+树B-树的变形根结点(非叶时)至少有两个结点除根外，非叶结点至少有m/2棵子树 最多有m棵子树,非叶结点都是索引， 含有子树中的最大或最少关键字含有n个关键字的非叶结点有n棵子树所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字，以及指向这些关键字的指针 5997 1544597297
26、101521374451598591976372B+树根叶两种查找：从根开始，从叶起始B+树查找成功的时间复杂性设第i层最少结点数Ni N1=m/2, N2=2m/2, N3=2 m/22 Nh= 2m/2h-1 nNh n 2m/2h-1 h-1=logm/2(n/2) h=logm/2(n/2)+1 hm/2=(logm/2(n/2)+1)m/2 O(log2n) B+树的插入和删除 与B-树类似键树_ 数字查找树 Trie树(Digital Search Tree)度2的树，每个结点只包含组成关键字的部分符号。为查找方便，约定简述为有序树，同层兄弟有序排列。键树的例16个关键字CAI,C
27、AO,LI,LAN,CHA,CHANG,WEN,CHAO,YUN,YANG,LONG,WANG,ZHAO,LIU,WU,CHEN以首字符分组：CAI,CAO, CHA,CHANG, CHAO,CHENLI,LAN, LONG, LIUWEN,WANG,WUYANG,YUNZHAO继续以第二,第三字符分组直到每组一个关键字CAI,CAO, CHA,CHANG, CHAO,CHENLAN , LIU, LONGWANG, WEN,WUYANG,YUN以集合,子集,元素的层次组成树CLWYZAHAIOAEUAUH$AO$IOAEN$UNNN$G$NNANO$G$G$N键树的孩子兄弟表示双链树CLWY
28、ZAHAIOAEUAUH$AO$IOAEN$UNNN$G$NNANO$G$G$N键树的查找成功时间复杂性键树的结点的最大度d由基决定: 关键字是英文单词： d=27 数字： d=11 查找每一位的平均长度 (1+d)/2设键树的深度为h 假设关键字的位数都相等 则查找一个字的平均长度 h(1+d)/2三、哈希表 Hashing table_散列一种搜索结构 不经过任何比较，一次存取就能得到所查的纪录： 每个记录和存储位置之间建立一个一一对应关系 f , 对每个关键字K, f(K)就是K的存储位置 称f为哈希函数。哈希函数的例 int HF(int key)/直接定址法 a,b是选定的常数 re
29、turn a*key+b;1993 1994 1996 1999 2001 1993 1994199619992001留余数法int HF(int key)/模一个素数得到的余数 return key%11; 2335 18 48 107 9 43 6023 35 486010718 9 43数字分析法1939 1949 1969 1999 2001 以第三位定位2001 1939194919691999int HF(char *key)/首末字母法，首末字母之和模101 int len=strlen(key), hashf=0; if(len=11; /右移11位，去掉末尾11位 retur
30、n key%1024;/去掉前面11位处理冲突的方法冲突collision: 不同的关键字得到同一个地址 1.开放定址法线性探查法 23 35 48 17 60 29 38 4023 35 486017 293840开放定址法 查找成功平均查找次数(1+1+1+1+1+4+3)/8=12/8=3/2 23 35 486017 2938 40哈希表的装填因子 表中填入的纪录数= 哈希表的长度开放定址法的查找成功的平均查找次数 (1+1/(1-)/2查找不成功的平均查找次数 (1+1/(1-)2)/2 开放定址法的缺点容易引起“二次聚集”发生冲突的点引起再一次冲突的可能性增加使冲突点聚集可以用再哈希法改进即定义一个哈希函数序列发生冲突的关键字用下一个哈希函数确定位置避免聚集链地址法19 14 23 01 68 20 8427 55 11 10 79 0 1 2 3 4 5 6 7 8 9 10 11 12 01142779 5568 1984 20 1023 11 查找成功的平均查找次数（1+2+3+4+1+2+1+2+1+1+2+1）/12 =21/12 =12/12=1 1+1/2=1.5链地址法查找成功的平均查找次数 1+/2查找不成功的平均查找次数 +e-
