《提高组(高中组)初赛复习资料4.ppt》由会员分享，可在线阅读，更多相关《提高组(高中组)初赛复习资料4.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、提高提高组(高中高中组)初初赛复复习资料料4查找与排序n查找顺序查找折半查找分块查找哈希查找n排序插入排序交换排序选择排序归并排序基数排序查找查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字是数据元素中某个数据项的值，它可以标识一个数据元素。查找方法评价n查找速度；n占用存储空间多少；n算法本身复杂程度；n平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的。3n1 静态查找表静态查找表n1.1顺序查找顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较
2、。算法描述i例例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5 比较次数：查找第n个元素：1查找第n-1个元素：2.查找第1个元素：n查找第i个元素：n+1-i查找失败：n+14int seqsrch(JD r,int n,int k)/数据元素存在r中，r0不用；/n为数据元素个数；/k为给定值 r0.key=k;/给定值放在r0中 int i=n;while(ri.key!=k)i-;return(i);/找不到时，返回0#define M 500typedef struct int
3、key;/关键字项 float info;/其他数据项JD;5顺序查找方法的ASL改进：将数据元素按访问频度升序排列，可降低ASL6n2.2折半查找查找过程：每次将待查记录所在区间缩小一半；适用条件：采用顺序存储结构的有序表；算法实现n设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值n初始时，令low=1,high=n,mid=(low+high)/2n让k与mid指向的记录比较若若k=rmid.key，查找成功查找成功若若krmid.key，则则low=mid+1n重复上述操作，直至lowhigh时，查找失败7int binsrch(JD r,int
4、 n,int k)/数据元素存在r中，r0不用 int low=1,high=n,mid,found=0;/found为寻找标志，found=0,未找到；found=1,找到 while(lowrmid.key)low=mid+1;else if(k=rmid.key)found=1;else high=mid-1;if(found=1)return(mid);else return(0);8算法描述lowhighmid例例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13
5、19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid9例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1
6、 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid101 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 9211算法评价v判定树：描述查找过程的二叉树叫；v有n个结点的判定树的深度为log2n+1 ；(P220注)v折半查找法在查找过程中进行的比较次数最多不超过其判定树的深度；v折半查找的ASL。层次为k的结点数
7、为2 k-1,和关键字比较次数为k次 12n1.3 分块查找索引顺序表的查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找。适用条件：分块有序表。算法实现n用数组存放待查记录,每个数据元素至少含有关键字域；n建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针。算法描述typedef struct int key;int link;SD;typedef struct int key;float info;JD;13int blocksrch(JD r,SD nd,int n,int b,int k)/b索引表的长度 int i=1,j;while
8、(kndi.key)&(ib)printf(nNot found);return(0);j=ndi.link;while(jn)&(k!=rj.key)&(rj.key=ndi.key)j+;if(k!=rj.key)printf(nNot found);j=0;return(j);141 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38例例15分块查找方法评价16ASL最大最小两者之间表结构有序表、无序表 有序表分块
9、有序表存储结构顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找折半查找分块查找17查找算法优点缺点适用于顺序查找算法简单且对表的结构无任何要求查找效率低n较小的表的查找和查找较少但改动较多的表(用链表作存储结构)折半查找查找效率高关键字要有序且只能用顺序存储结构实现特别适用于一经建立就很少改动又经常需要查找的线性表分块查找在表中插入或删除记录时就只要在该记录所属块内操作，因为块内记录的存放是随意的，所以插入和删除比较容易要增加一个辅助数组的存储空间，并要进行将初始表分块排序运算适用于有分块特点的记录，如一个学校的学生登记表可按系号或班号分块。18n2 哈希查找基本思想
10、：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。定义n哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象哈希函数可写成：addr(ai)=H(ki)ai是表中的一个元素addr(ai)是ai的存储地址ki是ai的关键字关键字集合存储地址集合hash19n哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫。n哈希查找又叫散列查找，利用哈希函数进行查找的过程叫。例 32个地区的各民族人口统计表编号 地区别 总人口 汉族 回族
11、.1 北京2 上海.以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区别作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shandong)=1920从例子可见：哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。冲突：key1key2，但H(key1)=H(key2)的现象叫。同义词：具有相同函数值的两个关键字，叫该哈希函数的。哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法。21哈希函数的构造方法
12、v直接定址法l构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+bl特点u直接定址法所得地址集合与关键字集合大小相等，不会发生冲突。u实际中能用这种哈希函数的情况很少。22n数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6
13、 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5.分析：只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址23n平方取中法构造：取关键字平方后中间几位作哈希地址。适于不知道全部关键字情况。n折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址。种类移位叠加：将分割后的几部分低位对齐相加；间界叠加：从一端沿分割界来回折送，然后对齐相加；适于关键字位数很多，且每一位上数字分布大致均匀情况。例 关键字为：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8
14、8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加24n除留余数法构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm特点简单、常用，可与上述几种方法结合使用；p的选取很重要；p选的不好，容易产生同义词；n随机数法构造：取关键字的随机函数值作哈希地址，即H(key)=random(key)。适于关键字长度不等的情况。25v选取哈希函数，考虑以下因素：l计算哈希函数所需时间l关键字长度l哈希表长度（哈希地址范围）l关键字分布情况l记录的查找频率26处理冲突的方法n开放定址法方法：
15、当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1)其中：H(key)哈希函数 m哈希表表长 di增量序列分类线性探测再散列：di=1,2,3,m-1二次探测再散列：di=1,-1,2,-2,3,k(km/2)伪随机探测再散列：di=伪随机数序列27例：表长为例：表长为11的哈希表中已填有关键字为的哈希表中已填有关键字为17，60，29的记录，的记录，H(key)=key MOD 11,现有第现有第4个记录，其关键字为个记录，其关键字为38，按三种处理冲突的方法
16、，将它填入表中按三种处理冲突的方法，将它填入表中0 1 2 3 4 5 6 7 8 9 1060 17 29(1)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5+2)MOD 11=7 冲突 H3=(5+3)MOD 11=8 不冲突 38(2)H(38)=38 MOD 11=5 冲突 H1=(5+1)MOD 11=6 冲突 H2=(5-1)MOD 11=4 不冲突38(3)H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则：H1=(5+9)MOD 11=3 不冲突3828n再哈希法方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地
17、址，即：Hi=Rhi(key)i=1,2,k其中：Rhi不同的哈希函数特点：计算时间增加n链地址法方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针。29例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 1412779685519842023101130哈希查找过程及分析n哈希查找过程给定k值计算H(k)此地址为空关键字=k查找失败查找成功按处理冲突方法计算HiYNYN31n哈希查找分析哈希查找过程仍是一个给
18、定值与关键字进行比较的过程评价哈希查找效率仍要用ASL哈希查找过程与给定值进行比较的关键字的个数取决于：哈希函数处理冲突的方法哈希表的填满因子=表中填入的记录数/哈希表长度32例例：已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函数为：H(key)=key MOD 13,哈希表长为m=16，设每个记录的查找概率相等。(1)用线性探测再散列处理冲突，即用线性探测再散列处理冲突，即Hi=(H(key)+di)MOD mH(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5H(79)=1 冲突，H1=(1+1)MOD16
19、=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=90 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15ASL=(1*6+2+3*3+4+9)/12=2.514 1 68 27 55 19 20 84 79 23 11 10H(19)=6H(14)=1H(23)=10H(1)=1 冲突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6
20、 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4H(11)=11H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=1233(2)用链地址法处理冲突用链地址法处理冲突0 1 2 3 4 5 6 7 8 9 10 11 12 14127796855198420231011ASL=(1*6+2*4+3+4)/12=1.75关键字(19,14,23,1,68,20,84,27,55,11,10,79)3
21、4哈希查找算法实现n用线性探测再散列法处理冲突实现查找过程：同前删除：只能作标记，不能真正删除插入：遇到空位置或有删除标记的位置就可以插入算法描述：35#define M 100int h(int k)return(k%13);int slbxxcz(int t,int k)/查找 int i,j=0;i=h(k);while(jM)&(t(i+j)%M!=k)&(t(i+j)%M!=0)j+;i=(i+j)%M;if(ti=k)return(i);else return(-1);36int slbxxcr(int t,int k)/散列表线性探测插入 int i,j=0;i=h(k);whi
22、le(j0)j+;if(j=M)return(0);i=(i+j)%M;if(ti=0)ti=k;return(1);if(ti=k)return(1);/已有此元素37int slbxxsc(int t,int k)/散列表线性探测删除 int i,j=0;i=h(k);while(jM)&(t(i+j)%M!=k)&(t(i+j)%M!=0)j+;i=(i+j)%M;if(ti=k)ti=-1;return(1);return(0);383 动态查找表特点特点：用于频繁进行插入、删除、查找的所谓动态查找表。：用于频繁进行插入、删除、查找的所谓动态查找表。二叉排序树二叉排序树n定义：二叉排序
23、树或是一棵空树，或是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；它的左、右子树也分别为二叉排序树。3945125333724100619078按中序遍历：按中序遍历：3，12，24，37，45，53，61，78，90，100递增中序遍历二叉排序树可得到一个关键字的有序序列401、查找过程：若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，查其左子树。若大于根结点的关键字值，查其右子树。在左右子树上的操作类似。1222503001102009910523021641显
24、然，在二叉排序树中查找某结点其实是从根结点出显然，在二叉排序树中查找某结点其实是从根结点出发走了一条从根到待查结点的路径。发走了一条从根到待查结点的路径。考虑如下两种不同插入次序的序列构成的二叉排序树，考虑如下两种不同插入次序的序列构成的二叉排序树，插入次序分别为：插入次序分别为：4024551237122437405540，24，12，37，55 12，24，37，40，5542插入次序分别为：4024551237122437405540，24，12，37，55 12，24，37，40，55显然，第I层结点需比较I次。在等概率的前提下，上述两图的平均查找长度为：43由上例分析易知：在二叉排序
25、树中进行查找的平均查找长度和二叉树在二叉排序树中进行查找的平均查找长度和二叉树的形态有关的形态有关，即，最坏:（n+1)/2（单支树）最好：log2n（形态匀称，与二分查找的判定树相似）442.二叉排序树的插入l插入原则：若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至某个结点的左子树或右子树为空为止，则插入结点应为该结点的左孩子或右孩子4512533372410061907820例如：在右图给定的二叉排序树中插入结点2045例 10，18，3，8，12，2，7，310101810183101838101838 12101838 122101838 122710
26、1838 12273l二叉排序树生成：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树46#include#include#define Null 0typedef int datatype;typedef struct btnodedatatype data;struct btnode*lchild,*rchild;bitnode,*bitree;生成排序二叉树的算法生成排序二叉树的算法47bitree create_ordbt()/生成二叉排序树bitree ins_node(bitree s,bitree t);bitree t,s;datatype x;t=Null;s
27、canf(%d,&x);while(x!=0)/输入0表示结束s=(bitree)malloc(sizeof(bitnode);s-data=x;s-lchild=Null;s-rchild=Null;t=ins_node(s,t);scanf(%d,&x);return t;48bitree ins_node(bitree s,bitree t)/插入新结点函数if(t=Null)t=s;else if(s-datadata)t-lchild=ins_node(s,t-lchild);else t-rchild=ins_node(s,t-rchild);return t;49void mai
28、n()bitree r=Null;r=create_ordbt();inorder(r);输入数据：10 18 3 8 12 2 7 3输出结果：2 3 3 7 8 10 12 18 50检索排序二叉树的算法检索排序二叉树的算法bitree bstsrch(bitree t,datatype k)/查找,返回结点地址 if(t=Null)|(t-data=k)return(t);else if(t-datarchild,k);else return(bstsrch(t-lchild,k);51void main()bitree r=Null,p;datatype k;r=create_ordb
29、t();inorder(r);printf(n);scanf(%d,&k);p=bstsrch(r,k);if(p!=Null)printf(n%dn,p-data);else printf(nnot found%dn,k);523.二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点，只需修改p双亲f的指针f-lchild=NULL 或 f-rchild=NULLp只有左子树或右子树p只有左子树，用p的左孩子代替p (1)(2)p只有右子树，用p的右孩子代替p (3)(4)p左、右子树均非空沿p左子树的根C的右子树分支找到S，S的右子树为空，S的左子树成为S的双亲Q的右子树，
30、用S取代p (5)若C无右子树，用C取代p (6)53SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)63421815634215删除1854中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP6342181215删除126342181555FPCPRCLQQLSSL中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：CL C QL Q SL S PR F(5)找P中序遍历的
31、前驱S1036241812156342181215删除1056FPCPRCL中序遍历：CL C P PR FFCPRCL中序遍历：CL C PR F(6)57 平衡二叉树（又称AVL树）起因：提高查找速度，避免最坏情况出现。如右图情况的出现。虽然完全二叉树的树型最好，但构造困难。常使用平衡二叉树。4024551237122437405558平衡因子（平衡度）：结点的左子树的高度结点的右子树的高度。平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉树。或者说每个结点的左右子树的高度最多差一的二叉树。注意：完全二叉树必为平衡树，平衡树不一定是完全二叉树。14125392863536050171
32、8730+1+1-1-1-100000000145392863536050171830+1+2-1-100000+1-1是平衡树不是完全二叉树是平衡树不是完全二叉树不是平衡树不是平衡树59在左图所示的平衡树中插入数据域为 2 的结点。插入之后仍应保持平衡二叉树的性质不变。141253928635360501718730+1+1-1-1-100000000平衡树平衡树141253928635360501718730+1+1-1-1-1000000002+1+1+2危机结点危机结点如何用最简单、最有效的办法保持如何用最简单、最有效的办法保持平衡二叉树的性质不变？平衡二叉树的性质不变？6014125
33、3928635360501718730+1+1-1-1-1000000002+1+1+2危机结点危机结点解决方案：解决方案：不涉及到危机结点的父亲结点，即以不涉及到危机结点的父亲结点，即以危机结点为根的子树的高度应保持不危机结点为根的子树的高度应保持不变（左图为变（左图为 3）。）。新结点插入后，找插入前第一个平衡新结点插入后，找插入前第一个平衡度不为度不为 0 的结点（如左图结点的结点（如左图结点9）即）即可。新插入的结点和第一个平衡度不可。新插入的结点和第一个平衡度不为为 0 的结点（也可能是危机结点）之的结点（也可能是危机结点）之间的结点其平衡度皆为间的结点其平衡度皆为 0。在调整中，仅
34、调整那些在平衡度变化在调整中，仅调整那些在平衡度变化的路径上的结点的路径上的结点(如如3,5,9)，其它结点，其它结点不予调整。不予调整。仍应保持二叉排序树的性质不变。仍应保持二叉排序树的性质不变。61141253928635360501718730+1+1-1-1-1000000002+1+1+2危机结点危机结点关键：将导致出现关键：将导致出现危机结点的情况危机结点的情况全部分析清除，全部分析清除，就可以使得平衡二叉排序树的性质保持不变！就可以使得平衡二叉排序树的性质保持不变！14932528635360501718730+1+1-1-1-10000000120062 左改组（新插入结点出现
35、在危机结点的左子树上进行的调整）的情况分析：1、LL 情况：(LL：表示新插入结点在危机结点的 左子树的左子树上)AB+1h-10+2+1hh-1h-1LL 改组改组BLBRARBA0h0h-1h-1BLBRAR危机结点危机结点改组前：高度为改组前：高度为 h+1 中序序列：中序序列：ABBLBRAR改组后：高度为改组后：高度为 h+1 中序序列：中序序列：ABBLBRAR注意：改组后注意：改组后 平衡度为平衡度为 0AB632、LR 情况：（LR：表示新插入结点在危机结点的 左子树的右子树上）情况A：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点CCLCRh-2h-2h
36、-10+1CB0h-1h-1BLARACRh-2CLh-1-10改组前：改组前：高度为高度为 h+1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为 0,0,-1CBABBLARCCLCR改组后：改组后：高度为高度为 h+1 中序序列：中序序列：ABBLARCCLCRA64情况B：AB+1h-10+2-1h-1LR 改组改组BLAR危机结点危机结点CCRCLh-1h-2h-20-1CB0h-1h-1BLARACLh-1CRh-2+10改组前：改组前：高度为高度为 h+1 中序序列：中序序列：注意：改组后注意：改组后 平衡度为平衡度为+1,0,0CBABBLARCCRCL改组后：
37、改组后：高度为高度为 h+1 中序序列：中序序列：AABBLARCCRCL65三种情况的区分：如果B的平衡度为1 则为 LL型改组；否则为 LR型改组：若C的平衡度为：1:则为LRA型改组；1:则为LRB型改组。66 右改组（新插入结点出现在危机结点的右子树上进行的调整）的情况分析：1、RR 情况：（RR：表示新插入结点在危机结点的右子树的右子树上）处理图形和 LL 镜象相似2、RL 情况：（RL：表示新插入结点在危机结点的右子树的左子树上）A、处理图形和 LRA 镜象相似 B、处理图形和 LRB 镜象相似 67平衡二叉排序树查找的分析平衡树上进行查找的时间复杂度为：O(log2n)68 B-
38、树树(平衡多叉树平衡多叉树)11009482112146236168902101 11021211B-树中不存在相同的关键字树中不存在相同的关键字69一棵一棵 m 阶阶 B-树树或者是一棵空树，或者是满足下列条件的平衡 m 叉树：树中每个结点至多有 m 棵子树；除根结点之外，其他每个结点至少有 m/2 棵子树；若根结点不是叶结点，则至少有两棵子树；所有叶结点都在同一层上，叶结点不包含任何信息；每个非叶结点包含下列信息：(n,P0,K1,P1,K2,P2,Kn,Pn)K1 K2 KnP0 所指子树中所有结点的关键字均小于 K1Pi 所(1in)指子树中所有结点的关键字均大于 Ki且小于 Ki+1
39、Pn 所指子树中所有结点的关键字均大于 Kn m/2 n+1 m m/2 1 n m 170B-树结点的结构类型：typedef struct mbsint keynum;keytype Keym;/*0 号单元未用*/struct mbs*linkm;71查找查找3636查找查找10810811001129482146236168902101 11021211367210020 605 108025 40120 180110 116132189 2003 阶阶 B-树插入：树插入：插入插入909010020 605 1080 9025 40120 180110 116132189 20073
40、插入插入19519510020 605 1080 9025 40120 180110 116132 189 195 20010020 605 1080 9025 40120 180 195110 11613218920074100 18020 605 1080 9025 40195110 116 132 189200120753 阶阶 B-树删除树删除删除删除353510020 605 1080 9025 35120 180110 116 132189 200直接删除10020 605 1080 9025120 180110 116 132189 2001.被删关键字所在结点中的关键字数目不少
41、于 m/2 。2.被删关键字所在结点中的关键字数目等于 m/2-1。删除删除25257610020 605 1080 90120 180110 116 132189 200 2.1若被删关键字结点的左兄弟结点关键字数目大于 m/2-1 。删除删除2525方法一方法一10010 60580 90120 180110 116 132189 200207710020 805 1090120 180110 116 132189 20060删除删除2525方法二方法二2.2若被删关键字结点的右兄弟结点关键字数目大于 m/2-1 。10020 80590120 180110 116 132189 2006
42、02.3若被删关键字结点的左、右兄弟结点关键字数目不大于 m/2-12.3.1父结点关键字数目大于 m/2-1。删除删除606078删除删除6060方法一方法一100805 2090120 180110 116 132189 20010020580 90120 180110 116 132189 200删除删除6060方法二方法二79删除删除5方法一方法一2.3.2 父结点关键字数目不大于 m/2-1。10020580120110 116189 200100 12020 80110 116189 200删除删除58010020580120 180110 116189 200132删除删除5方法二方法二20 80100 120 180110 116189 20013220 80100110 116189 200132120180删除删除581删除删除606010020 605 1025 35120 180110 116189 20013280 9010020 805 1025 35120 180110 116189 20013290被删关键字为非叶结点。82谢谢！