最新静态搜索结构动态搜索结构散列可扩充散列课件.ppt

1、静态搜索结构动态搜索结构散静态搜索结构动态搜索结构散列可扩充散列列可扩充散列ppt课件课件查找 搜索搜索结构 同一数据类型（纪录）的元素 构成的数据集合。搜索 在数据集合中寻找满足条件的对 象（数据元素）。关键字 数据元素中某个字段（数据项）的值。主关键字 唯一地表示一个纪录。次关键字 标识若干纪录 k f(k)=s=j2j-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个数据的总查找次

2、数：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搜索成功平均概率时间复杂性 介于 log2(2k)-1 和 log2(2k+1)-1 之间即 k-1 和 k 之间 k=log2(n+1)n个元素的折半搜索成功平均概率时间复杂性 log2(n+1)-1/2 斐波那契搜索根据斐波那契序

3、列的特点对有序表分割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平均查找性能优于折半查找 O(log2n)最坏情况比折半查找差（3）静态树表的搜索不等概率查找时折半查找不一定好，以每点查找次数（概率）为这点的权wi带权二叉树总路径长度 PH=wihi iPH 最小的二叉树叫静态最优二叉树

4、不同于霍夫曼树：每个结点都有权值，都要查找。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,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-

5、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 5FDAHBEIGC342115534HP=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 1

6、32212138920334244382448605874498653 最大关键字 起始地址索引表索引顺序表的查找 查找 关键字key=38 1.先检索索引表 确定子表位置 2.再在子表中搜索22 48 86 1 7 132212138920334244382448605874498653索引表索引顺序表的查找成功的平均概率时间复杂性 索引表查找时间+子表查找时间设索引表长为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 有序索引顺序表当索

7、引顺序表已经排序时，子块搜索可以用折半搜索。平均查找时间：(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二、动态搜索表特点 查找过程中生成搜索表 查找失败时插入纪录 二叉搜索树 平衡二叉搜索AVL树二叉搜索树二叉搜索树（二叉排序树）（二叉排序树）其左非空子树上所有结点的值都小于根结点的值 其右非空子树上所有结点的值都大于根结点的值 左右子树也是二叉搜索树4938651397277649二叉搜索

8、树的作用：排序，检索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树 加快查找排序的速度定义：左右两子树深度之差不超过1，左子树和右子树都是平衡二叉树。4512578206031159504512820311不平衡平衡同一个数组的二叉排序树和二叉平衡树20 30 80 40 10 60 50 70492065975027134910701340304980604

9、9106597602713495070134020498030AVL树的结点增加一个平衡因子 left data balanceFactor rightbalance=height(right subtree)-height(left subtree)balance=1或-149386513 1 1平衡因子左重加左右转结点p左重，还要加一个左结点 不平衡4938651310 p lc右转：将p作lc的右子结点4938651310 p lc左重加左右转结点p左重，还要加一个左结点 不平衡3813104020plc 43813104020plc 4右转：将p作lc的右子结点,将lc的右子树接成p的

10、左子树右重加右左转结点p右重，还要加一个右结点 不平衡3813394045prc 4454038439prc13左转：将p作rc的左子结点,将rc的左子树接成p的右子树左重加左的右双旋 左转再右转结点p左重 lc的右子树加一个结点 不平衡3813104020plc26np先以lc np为轴左转3813104020plc26np再以p,np为轴右转3813104020plc26np右重加右的左双旋 右转再左转结点p右重 rc的左子树加一个结点 不平衡38135546prc41np先以rc np为轴右转3841674613prc55np再以p,np为轴左转5538136746npp41np67AV

11、L树的生成20 30 80 40 10 60 50 70491065602713134020498030左转49652713204980304965271320498030左重加左的右左转再右转20 30 80 40 10 60 50 70106013404965271320498030左重加左的右左转再右转106013404965271320498030左转106013404965271320498030右转20 30 80 40 10 60 50 7010601340496527132049803010601340496527132049803013701350AVL树的高度设AVL树高度

12、为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个结点的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

13、.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的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个关

14、键字的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)NhNh-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 可以得到

15、h.h就是最大查找次数 等概率平均查找成功时间复杂性O(log2n)B-树 平衡的多路搜索树 B-树的定义 空树 或 m叉树每个结点至多有m棵子树，如根结点不是叶，至少有两棵子树，除根之外，所有非终端结点至少有m/2 棵子树,本节中记为m/2,m=3时 称为2-3树所有的非终端结点含有信息 (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 3

16、91 99347 53FFFFFFFFFFF 1 35 1 18 2 43 78 1 111 271 391 99347 53FFFFFFFFFFFB-树的搜索过程 检索结点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)/

17、2)+1n个结点的B-树的最大查找次数 为 hm/2 (logm/2(n+1)/2)+1)m/2 O(log2n)B-树的插入先从底层以大小增加一个关键字 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 991

18、47FFFFFF增加一个关键字601 60FF再将53上移结点分裂 1 35 53 1 18 2 43 1 78 1 391 99147FFFFFF增加一个关键字601 60FFB-树的删除找到要删除的关键字所在结点，删除。若这个结点是最下层结点，并且其中关键字数不少于m/2-1删除完成。若删除的是非终端结点中的关键字Ki，以指针Ai所指子树的最小关键字Y代替Ki,删除Y.重复直至叶结点若这个结点是最下层结点，但是其中关键字数不少于m/2-1，删除完成。若这个结点是最下层结点，但是其中关键字数少于m/2-1，若该结点的左右兄弟结点中有一个关键字数大于m/2-1，则将其兄弟结点中最小或最大的关键

19、字上移至双亲结点中，而将双亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。若该结点的左右兄弟结点的关键字数都等于m/2-1，则将其与一个兄弟结点合并，从双亲结点下移一个关键字被删除关键字的位置。1.重复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关键字9

20、9上移 1 35 78 1 18 2 43 1 65 1 391 99147FFFFFF删除一个关键字531 60FF关键字65上移，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 391147FFFFF

21、F删除一个关键字531 60FF关键字99上移 1 35 78 1 18 2 43 1 1 39147FFFF删除一个关键字531 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个关键字的非叶结点

22、有n棵子树所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字，以及指向这些关键字的指针 5997 1544597297101521374451598591976372B+树根叶两种查找：从根开始，从叶起始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的树，

23、每个结点只包含组成关键字的部分符号。为查找方便，约定简述为有序树，同层兄弟有序排列。键树的例16个关键字CAI,CAO,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以集合,子集,元素的层次组成树CLWYZAHAIOAEU

24、AUH$AO$IOAEN$UNNN$G$NNANO$G$G$N键树的孩子兄弟表示双链树CLWYZAHAIOAEUAUH$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为哈希函数。哈

25、希函数的例 int HF(int key)/直接定址法 a,b是选定的常数 return a*key+b;1993 1994 1996 1999 2001 1993 1994199619992001留余数法int HF(int key)/模一个素数得到的余数 return key%11;35 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

26、=0;if(len=11;/右移11位，去掉末尾11位 return 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 27 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-94 结束语结束语