静态搜索结构动态搜索结构散列可扩充散列

查找 搜索搜索结构 同一数据类型（纪录）的元素 构成的数据集合。搜索 在数据集合中寻找满足条件的对 象（数据元素）。关键字 数据元素中某个字段（数据项） 的值。主关键字 唯一地表示一个纪录 。次关键字 标识若干纪录 搜索成功 找到满足条件的数据对象 报告该对象在结构中的位置 给出整个纪录的信息搜索失败 搜索不成功静态搜索 搜索结构在搜索前后不发生变化动态搜索 搜索的同时执行插入或删除 结构自行调整提高效率 先排序，分类，编目，索引 优化结构 一、静态搜索结构 基于数组的数据表类 顺序表线性表、数组、链表。 (1) 顺序搜索 从头至尾逐个比较 最快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 1012 23 3 3 34 4 41+2*2+4*3+3*4=29 O(29/10) S=1+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 12 23 3 3 34 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)+ 2 2(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)2 k 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)2 k+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) log 2(n+1)-1当n50时 近似于 log2(n+1)-1 n个元素的折半搜索2k-1n2k+1-1搜索成功平均概率时间复杂性 介于 log2(2k)-1 和 log2(2k+1)-1 之间即 k-1 和 k 之间 k=log2(n+1) n个元素的折半搜索成功平均概率时间复杂性 log 2(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平均查找性能优于折半查找 O(log2n) 最坏情况比折半查找差 （3）静态树表的搜索不等概率查找时折半查找不一定好，以每点查找次数（概率）为这点的权wi带权二叉树总路径长度 PH=wihi iPH 最小的二叉树叫静态最优二叉树不同于霍夫曼树：每个结点都有权值，都要查找。 ECA GB D HF I5 4 511 2 343A B C D E F G H I1 1 2 5 3 4 4 3 5 PH=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为左子树 a i+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 7p i 3 1 2 A B C D E F G H I wi 1 1 2 5 3 4 4 3 5FDA HB E IGC 3 421 1 5 534 HP=4*1+5*2+3*2+ 1*3+3*3+4*3+5*3+ 1*4+2*4=7178次最优树平均查找次数 O(HP/sw h) 索引顺序表 分块有序 后一子表中的关键字都大于前一子表中的关键字22 48 86 1 7 1322 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 最大关键字 起始地址索引表 索引顺序表的查找 查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中搜索22 48 86 1 7 1322 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53索引表 索引顺序表的查找成功的平均概率时间复杂性 索引表查找时间+子表查找时间设索引表长为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 log 2(n +1)-1 二、动态搜索表特点 查找过程中生成搜索表 查找失败时插入纪录 二叉搜索树 平衡二叉搜索AVL树 二叉搜索树 （二叉排序树） 其左非空子树上所有结点的值都小于根结点的值 其右非空子树上所有结点的值都大于根结点的值 左右子树也是二叉搜索树4938 6513 97 27 7649二叉搜索树的作用：排序，检索49 38 65 97 76 13 27 49 二叉搜索树的插入过程45 12 8 57 60 20 11 59 50 34512 578 20 603 11 595057 20 8 45 60 59 3 12 50 11 5720 608 45113 12 5059 平衡二叉树AVL树 加快查找排序的速度定义： 左右两子树深度之差不超过1， 左子树和右子树都是平衡二叉树。4512 578 20 603 11 595045128 203 11不平衡平衡 同一个数组的二叉排序树和二叉平衡树20 30 80 40 10 60 50 704920 6597 50 2713 4910 70134030 49 8004910 65 97 602713 4950 70134020 49 8030 AVL树的结点增加一个平衡因子 left data balanceFactor rightbalance=height(right subtree)-height(left subtree)balance=1或-1 4938 6513 1 1平衡因子 左重加左右转结点p左重，还要加一个左结点 不平衡4938 651310 p lc右转：将p作lc的右子结点49 38 651310 p lc 左重加左右转结点p左重，还要加一个左结点 不平衡381310 4020plc 4 381310 4020 plc 4右转：将p作lc的右子结点, 将lc的右子树接成p的左子树 右重加右左转结点p右重，还要加一个右结点 不平衡3813 39 40 45p rc 4 454038 439p rc13左转：将p作rc的左子结点, 将rc的左子树接成p的右子树 左重加左的右双旋 左转再右转结点p左重 lc的右子树加一个结点 不平衡381310 4020plc 26np先以lc np为轴左转381310 4020plc 26np再以p, np为轴右转381310 4020 plc 26np 右重加右的左双旋 右转再左转结点p右重 rc的左子树加一个结点 不平衡3813 5546p rc 41np先以rc np为轴右转3841 674613p rc 55np再以p, np为轴左转553813 6746 npp 41np67 AVL树的生成20 30 80 40 10 60 50 7049 1065 6027 1313 4020 49 8030左转 49 65 271320 49 8030 49 65 271320 49 8030左重加左的右左转再右转 20 30 80 40 10 60 50 7010 60134049 65 271320 49 8030左重加左的右左转再右转10 60134049 65 271320 49 8030左转 10 60134049 65 271320 49 8030右转 20 30 80 40 10 60 50 7010 60134049 65 271320 49 8030 10 60134049 65 271320 49 8030 13701350 AVL树的高度设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 n h = fh-1 nh=(51/2)*(1+ 51/2)/2)h+3 -1 n个结点的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的AVL树至少几个节点。 15个节点的AVL树至多多高？ 二叉搜索树的查找分析平均等概率查找时间(1+2+2+3+3+3)/6=14/6 4512 578 20 6045128 203 11 (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) NhNh-1 Nh-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)除根之外，所有非终端结点至少有m/2 棵子树 ,本节中记为m/2, m=3时 称为2-3树4)所有的非终端结点含有信息 (n,A 0,K1,A1,K2,Kn,An) m/2-1个关键字5) 所有叶结点都在同一层次 ，叫做失败结点。 所有的非终端结点含有信息 n : 有n+1棵子树， K1K2Kn 关键字有序序列, 指针Ai-1指向子树中结点的关键字小于Ki, n A0 K1 A1 K2 Kn An 1 35 1 18 2 43 78 1 11 1 27 1 39 1 99 3 47 53 F F F F F F F F F F F 1 35 1 18 2 43 78 1 11 1 27 1 39 1 99 3 47 53 F F F F F F F F F F FB-树的搜索过程 检索结点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+1N h+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(log 2n) B-树的插入先从底层以大小增加一个关键字 1. 结点中的关键字不超过m时完成。 2.结点中的关键字等于m时： 将该结点分成左右两个结点 中间一个关键字上升至双亲结点 重复2.直至根 1 35 1 18 2 43 78 1 11 1 27 1 39 1 99 3 47 53 F F F F F F F F F F F增加一个关键字60插入底层 1 35 1 18 2 43 78 1 39 1 99 3 47 53 60 F F F F F F F增加一个关键字60将53上移结点分裂 1 35 1 18 2 43 53 78 1 39 1 99 1 47 F F F F F F增加一个关键字60 1 60 F F再将53上移结点分裂 1 35 53 1 18 2 43 1 78 1 39 1 99 1 47 F F F F F F增加一个关键字60 1 60 F F B-树的删除找到要删除的关键字所在结点，删除。若这个结点是最下层结点，并且其中关键字数不少于m/2-1删除完成。若删除的是非终端结点中的关键字Ki，以指针Ai所指子树的最小关键字Y代替Ki,删除Y.重复直至叶结点若这个结点是最下层结点，但是其中关键字数不少于m/2-1，删除完成。 若这个结点是最下层结点，但是其中关键字数少于m/2-1，1.若该结点的左右兄弟结点中有一个关键字数大于m/2-1，则将其兄弟结点中最小或最大的关键字上移至双亲结点中，而将双亲结点中小于或大于且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。2.若该结点的左右兄弟结点的关键字数都等于m/2-1，则将其与一个兄弟结点合并，从双亲结点下移一个关键字被删除关键字的位置。3. 重复2。 1 35 53 1 18 2 43 1 78 1 39 1 99 1 47 F F F F F F删除一个关键字53 1 60 65 F F F 1 35 78 1 18 2 43 1 1 39 1 99 1 47 F F F F F F删除一个关键字53 1 60 65 F F F关键字78上移 1 35 78 1 18 2 43 1 99 1 39 1 1 47 F F F F F F删除一个关键字53 1 60 65 F F F关键字99上移 1 35 78 1 18 2 43 1 65 1 39 1 99 1 47 F F F F F F删除一个关键字53 1 60 F F关键字65上移，99下移， 1 35 65 1 18 2 43 1 78 1 39 1 99 1 47 F F F F F F删除一个关键字53 1 60 F F关键字65继续上移，与78交换，删除完成 1 35 78 1 18 2 43 1 1 39 1 99 1 47 F F F F F F删除一个关键字53 1 60 F F关键字78上移 1 35 53 1 18 2 43 1 78 1 39 1 99 1 47 F F F F F F删除一个关键字53 1 60 F F 1 35 78 1 18 2 43 1 99 1 39 1 1 47 F F F F F F删除一个关键字53 1 60 F F关键字99上移 1 35 78 1 18 2 43 1 1 39 1 47 F F F F删除一个关键字53 1 60 99 F F两个结点合并，关键字99下移F 1 35 1 18 2 43 78 1 39 1 47 F F F F删除一个关键字53 1 60 99 F F两个结点合并，关键字78下移F 1 35 1 18 2 43 60 1 39 1 47 F F F F删除一个关键字53 1 78 99 F F关键字78继续下移，与60交换F B+树B-树的变形根结点(非叶时)至少有两个结点除根外，非叶结点至少有m/2棵子树 最多有m棵子树,非叶结点都是索引， 含有子树中的最大或最少关键字含有n个关键字的非叶结点有n棵子树所有的叶子结点都在同一个层次上，叶子结点中包含全部关键字，以及指向这些关键字的指针 59 97 15 44 59 72 9710 15 21 37 44 51 59 85 91 9763 72B+树根叶两种查找：从根开始，从叶起始 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=(log m/2(n/2)+1)m/2 O(log2n) B+树的插入和删除 与B-树类似 键树_ 数字查找树 Trie树(Digital Search Tree)度2的树，每个结点只包含组成关键字的部分符号。为查找方便，约定简述为有序树，同层兄弟有序排列。 键树的例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 以集合,子集,元素的层次组成树C L W Y ZA H A I O A E U A U H$ $ $ A O $I O A E N $ U N N N $G $ N N AN O$G $G$ $ $ N 键树的孩子兄弟表示双链树C L W Y ZA H A I O A E U A U H$ $ $ A O $I O A E N $ U N N N $G $ N N AN O$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是选定的常数 return a*key+b;1993 1994 1996 1999 2001 1993 1994 1996 1999 2001 留余数法int HF(int key)/模一个素数得到的余数 return key%11; 23 35 18 48 107 9 43 6023 35 48 60 107 18 9 43 数字分析法1939 1949 1969 1999 2001 以第三位定位2001 1939 1949 1969 1999 int HF(char *key)/首末字母法，首末字母之和模101 int len=strlen(key), hashf=0; if(len=11; /右移11位，去掉末尾11位 return key%1024;/去掉前面11位 处理冲突的方法冲突collision: 不同的关键字得到同一个地址 1.开放定址法线性探查法 23 35 48 17 60 29 38 4023 35 48 60 17 29 38 40 开放定址法 查找成功平均查找次数(1+1+1+1+1+4+3)/8=12/8=3/2 23 35 48 60 17 29 38 40 哈希表的装填因子 表中填入的纪录数= 哈希表的长度开放定址法的查找成功的平均查找次数 (1+1/(1-)/2查找不成功的平均查找次数 (1+1/(1-)2)/2 开放定址法的缺点容易引起“二次聚集”发生冲突的点引起再一次冲突的可能性增加使冲突点聚集可以用再哈希法改进即定义一个哈希函数序列发生冲突的关键字用下一个哈希函数确定位置避免聚集 链地址法19 14 23 01 68 20 84 27 55 11 10 79 0 1 2 3 4 5 6 7 8 9 10 11 12 01 14 27 79 55 68 19 84 20 10 23 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-