《第七查找学习.pptx》由会员分享，可在线阅读，更多相关《第七查找学习.pptx（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1typedefstruct KeyTypekey；/关键字字段，可以是整型，字符串型、构造类型等 /其它字段 ElemType；数据元素类型说明数据元素类型说明第1页/共105页2查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的查找方法评价查找方法评价第2页/共105页3静态查找表结构静态查找表结构静态查找表是数据元素的线性表，可以是静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。基于数组的顺序存储或以线性链表存储。静态查找表结构静态查找表结
2、构第3页/共105页4顺序存储结构 typedefstructElemType*elem；/数组基址intlength；/表长度 S_TBL；静态查找表的顺序存储结构静态查找表的顺序存储结构第4页/共105页5链式存储结构typedefstructNODEElemTypeelem；/结点的值域 structNODE*next；/下一个结点指针域NodeType；静态查找表的链式存储结构静态查找表的链式存储结构第5页/共105页6查找过程从表的一端开始逐个进行记录的关键字和给定值的比较i i找找646401234567891011012345678910115131921375664758088
3、925131921375664758088926464监视哨监视哨i ii ii ii i比较次数比较次数=5=5比较次数：比较次数：查找第查找第n n个元素：个元素：11查找第查找第n-1n-1个元素：个元素：2 2.查找第查找第1 1个元素：个元素：n n查找第查找第i i个元素：个元素：n+1-in+1-i查找失败查找失败：n+1n+1静态查找静态查找顺序查找顺序查找第6页/共105页7顺序查找方法的顺序查找方法的ASLASL第7页/共105页8条件有序表表中数据元素按关键字升序或降序排列 折半查找的思想每次将待查记录所在区间缩小一半静态查找静态查找折半查找折半查找第8页/共105页9例
4、：例：0505，1313，1919，2121，3737，5656，6464，7575，8080，8888，9292查找的关键字查找的关键字K=21K=21。05，13，19，21，37，56，64，75，80，88，9205，13，19，21，37，56，64，75，80，88，9205，13，19，21，37，56，64，75，80，88，92第9页/共105页10 mid=mid=折半查找的基本思想折半查找的基本思想条件(1)确定查找区间的中点位置mid(2)将待查的K值与seqlistmid.key比较(3)若相等，查找成功并返回此位置(4)若不相等，确定新的查找区间,返回(1),重新开
5、始二分法查找(5)当上下界相等时,结束查找过程第10页/共105页11lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid折半查找的算法折半查找的算法例1234567891011513192137566475808892找21第11页/共105页121234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid折半查找的算法折半查找的算法例
6、1234567891011513192137566475808892lowhighmid找70第12页/共105页131234567891011513192137566475808892lowhigh1234567891011513192137566475808892low highmid折半查找的算法折半查找的算法第13页/共105页14插值查找通过下列公式求取中点，插值查找通过下列公式求取中点，其中其中lowlow和和highhigh分别为表的两个端点下标，分别为表的两个端点下标，kxkx为给为给定值。定值。若若 kxtbl.elemmid.keykxtbl.elemmid.keykxtb
7、l.elemmid.key，则则low=mid+1low=mid+1，继续右继续右半区查找；半区查找；若若 kx=tbl.elemmid.keykx=tbl.elemmid.key，查找成功。查找成功。静态查找静态查找有序表的插值查找思想有序表的插值查找思想第14页/共105页15静态查找静态查找有序表的斐波那契查找有序表的斐波那契查找斐波那契查找通过斐波那契数列对有序表进行分斐波那契查找通过斐波那契数列对有序表进行分割割查找区间的两个端点和中点都与斐波那契数有关查找区间的两个端点和中点都与斐波那契数有关斐波那契数列定义如下：斐波那契数列定义如下：第15页/共105页16静态查找静态查找有序表
8、的斐波那契查找有序表的斐波那契查找分割的思想分割的思想对于表长为对于表长为F(i)-1F(i)-1的有序表，以相对的有序表，以相对lowlow偏移量偏移量F(i-F(i-1)-11)-1取中点，即取中点，即mid=low+F(i-1)-1mid=low+F(i-1)-1，对表进行分割，对表进行分割则左子表表长为则左子表表长为F(i-1)-1F(i-1)-1，右子表表长为，右子表表长为F(i)-1-F(i)-1-F(i-1)-1-1=F(i-2)-1F(i-1)-1-1=F(i-2)-1可见，两个子表表长也都是某个斐波那契数可见，两个子表表长也都是某个斐波那契数-1-1，因而，可以对子表继续分割
9、。因而，可以对子表继续分割。第16页/共105页17静态查找静态查找分块查找（索引顺序查找）分块查找（索引顺序查找）查找过程将表分成几块，块内无序，块间有序先确定待查记录所在块，再在块内查找适用条件分块有序表是后一个子表中所有记录的关键字均大于前一个子表中的最大关键字算法实现用数组存放待查记录,每个数据元素至少含有关键字域建立索引表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针第17页/共105页18先用给定值先用给定值kxkx在索引表中检测索引项，以确定在索引表中检测索引项，以确定所要进行的查找在查找表中的查找分块所要进行的查找在查找表中的查找分块(由于索由于索引项按关键字字段有
10、序，可用顺序查找或折半引项按关键字字段有序，可用顺序查找或折半查找查找)然后，再对该分块进行顺序查找。然后，再对该分块进行顺序查找。分块查找算法分块查找算法第18页/共105页1912345678910111213141516171812345678910111213141516171822121389202212138920334244382448334244382448 60587457865360587457865322488622488617131713索引表索引表查查3838分块查找过程分块查找过程第19页/共105页20静态查找静态查找查找方法的比较查找方法的比较顺序查找顺序查找顺
11、序查找顺序查找折半查找折半查找折半查找折半查找分块查找分块查找分块查找分块查找ASLASLASLASL最大最大最大最大最小最小最小最小两者之间两者之间两者之间两者之间表结构表结构表结构表结构有序表有序表有序表有序表无序表无序表无序表无序表有序表有序表有序表有序表分块有序表分块有序表分块有序表分块有序表存储结构存储结构存储结构存储结构顺序存储结顺序存储结顺序存储结顺序存储结线性链表线性链表线性链表线性链表顺序存储顺序存储顺序存储顺序存储结构结构结构结构顺序存储结构顺序存储结构顺序存储结构顺序存储结构线性链表线性链表线性链表线性链表第20页/共105页21动态查找表动态查找表 二叉排序树二叉排序树
12、二叉排序树定义二叉排序树定义二叉排序树二叉排序树（BinarySortTreeBinarySortTree）或者是一棵或者是一棵空树；或者是具有下列性质的二叉树：空树；或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均若左子树不空，则左子树上所有结点的值均小于根结点的值；小于根结点的值；若右子树不空，则右子树上所有结点的值均若右子树不空，则右子树上所有结点的值均大于根结点的值。大于根结点的值。左右子树也都是二叉排序树。左右子树也都是二叉排序树。第21页/共105页22以二叉链表作为二叉排序树的存储结构typedefstructNODEElemTypeelem;/数据元素字段st
13、ructNODE*lc,*rc;/左、右指针字段NodeType;/二叉树结点类型二叉排序树的存储结构二叉排序树的存储结构第22页/共105页23二叉排序树的查找算法二叉排序树的查找算法二叉排序树的查找过程二叉排序树的查找过程 若查找树为空，查找失败。若查找树为空，查找失败。查找树非空，将给定值查找树非空，将给定值kxkx与查找树的根结点与查找树的根结点关键字比较。关键字比较。若相等，查找成功，结束查找过程，否则若相等，查找成功，结束查找过程，否则当给当给kxkx小于根结点关键字，查找将在以左子小于根结点关键字，查找将在以左子女为根的子树上继续进行，转女为根的子树上继续进行，转当给当给kxkx
14、大于根结点关键字，查找将在以右子大于根结点关键字，查找将在以右子女为根的子树上继续进行，转女为根的子树上继续进行，转第23页/共105页24二叉排序树的生成二叉排序树的生成插入原则插入原则若二叉排序树为空，则插入结点应为新的根结若二叉排序树为空，则插入结点应为新的根结点；否则，继续在其左、右子树上查找，直至点；否则，继续在其左、右子树上查找，直至某个结点的左子树或右子树为空为止，则插入某个结点的左子树或右子树为空为止，则插入结点应为该叶子结点的左孩子或右孩子结点应为该叶子结点的左孩子或右孩子二叉排序树生成二叉排序树生成从空树出发，经过一系列的查找、插入操作之从空树出发，经过一系列的查找、插入操
15、作之后，可生成一棵二叉排序树后，可生成一棵二叉排序树第24页/共105页25例例 1010，1818，3 3，8 8，1212，2 2，7 7，33101010101818101018183 3101018183 38 8101018183 38 8 1212101018183 38 8 12122 2101018183 38 8 12122 27 7101018183 38 8 12122 27 73 3中序遍历二叉排序树可得到一个关键字的有序序列中序遍历二叉排序树可得到一个关键字的有序序列二叉排序树的生成二叉排序树的生成第25页/共105页26原则从二叉排序树中删除一个结点之后，使其仍能保
16、持二叉排序树的特性即可。二叉排序树的删除二叉排序树的删除第26页/共105页27p为叶子结点，只需修改p双亲f的指针f-lc=NULL,f-rc=NULLp只有左子树或右子树p只有左子树，用p的左孩子代替p(1)(2)p只有右子树，用p的右孩子代替p(3)(4)p左、右子树均非空沿p左子树的根C的右子树分支找到S，S的右子树为空，将S的左子树成为S的双亲Q的右子树，用S取代p(5)若C无右子树，用C取代p(6)删除二叉排序树中的删除二叉排序树中的p p结点结点的讨论的讨论第27页/共105页28S SQQP PL LP P中序遍历：中序遍历：QSPQSPL LPPS SQQP PL L中序遍历
17、：中序遍历：QSPQSPL L(2)(2)S SP PP PL LQQ中序遍历：中序遍历：P PL LPSQPSQS SP PL LQQ中序遍历：中序遍历：P PL LSQSQ(1)(1)第28页/共105页29中序遍历：中序遍历：PPPPR RSQSQS SP PR RQQ中序遍历：中序遍历：P PR RSQSQ(3)(3)S SP PP PR RQQ中序遍历：中序遍历：QSPPQSPPR RS SQQP PR R中序遍历：中序遍历：QSPQSPR R(4)(4)S SQQP PR RP P第29页/共105页30F FP PC CP PR RC CL LQQQQL LS SS SL L中序
18、遍历：中序遍历：C CL LCQCQL LQSQSL LSPPSPPR RFFF FS SC CP PR RC CL LQQQQL LS SL L中序遍历：中序遍历：C CL LCQCQL LQSQSL LSPSPR RFF(5)(5)F FP PC CP PR RC CL L中序遍历：中序遍历：C CL LCPPCPPR RFFF FC CP PR RC CL L中序遍历：中序遍历：C CL LCPCPR RFF(6)(6)第30页/共105页31例例808050501201206060110110150150555570705353删除删除5050808060601201201101101
19、50150555570705353删除删除6060808055551201201101101501505353707010104 425258 813135 54 4删除删除10108 84 425255 513134 4删除删除5 58 84 425254 41313二叉排序树的删除二叉排序树的删除第31页/共105页32对给定序列建立二叉排序树若左右子树均匀分布，则其查找过程类似于有序表的折半查找。若给定序列原本有序，则建立的二叉排序树就蜕化为单链表，其查找效率同顺序查找一样需对均匀的二叉排序树进行插入或删除结点后，应对其调整，使其依然保持均匀。平衡二叉树的引入平衡二叉树的引入第32页/共
20、105页33平衡二叉树或者是一棵空树，或者是具有下列性质的二叉排序树它的左子树和右子树都是平衡二叉树左子树和右子树高度之差的绝对值(平衡因子)不超过1平衡二叉树平衡二叉树(AVLAVL树树)的定义的定义第33页/共105页34第34页/共105页35非平衡二叉树的调整非平衡二叉树的调整在在平平衡衡二二叉叉树树上上插插入入或或删删除除结结点点后后，可可能能使使树树失失去去平平衡衡，因因此此，需需要要对对失失去去平平衡衡的的树树进进行行平平衡化调整衡化调整调整的原则调整的原则应应该该是是处处理理与与扦扦入入点点最最近近的的、而而平平衡衡因因子子又又比比1 1大或比大或比-1-1小的结点。小的结点。
21、第35页/共105页36左单旋转（LL型的处理）右单旋转（RR型的处理）先左后右双向旋转（LR型的处理）先右后左双向旋转（RL型的处理）非平衡二叉树的调整非平衡二叉树的调整第36页/共105页37非平衡二叉树的调整非平衡二叉树的调整平衡处理平衡处理1ABC02CBA000LLLL型平衡处理型平衡处理 LLLL型的处理型的处理(左左型左左型)在在C C的左孩子的左孩子B B上扦入一个左孩子结点上扦入一个左孩子结点A A，使，使C C的的平衡因子由平衡因子由1 1变成了变成了2 2，成为不平衡的二叉树序树。，成为不平衡的二叉树序树。这时的平衡处理为：将这时的平衡处理为：将C C顺时针旋转，成为顺时
22、针旋转，成为B B的的右子树，而原来右子树，而原来B B的右子树则变成的右子树则变成C C的左子树，的左子树，待扦入结点待扦入结点A A作为作为B B的左子树。的左子树。第37页/共105页38非平衡二叉树的调整非平衡二叉树的调整LRLR型的处理型的处理(左右型左右型)在在C C的左孩子的左孩子A A上扦入一个右孩子上扦入一个右孩子B B，使，使C C的平衡的平衡因子由因子由1 1变成了变成了2 2，成为不平衡的二叉排序树。这，成为不平衡的二叉排序树。这是的平衡处理为：将是的平衡处理为：将B B变到变到A A与与CC之间，使之成之间，使之成为为LLLL型，然后按第型，然后按第(1)(1)种情形
23、种情形LLLL型处理。型处理。0 0-1 1 C C A A B B 2 2 B B 0 0 0 0 C C A A 0 0 平衡处理平衡处理 旋转旋转 0 0 1 1 C C A A B B 2 2 LRLR型平衡处理型平衡处理第38页/共105页39非平衡二叉树的调整非平衡二叉树的调整RRRR型的处理型的处理(右右型右右型)在在A A的右孩子的右孩子B B上扦入一个右孩子上扦入一个右孩子C C，使，使A A的平衡因的平衡因子由子由-1-1变成变成-2-2，成为不平衡的二叉排序树。这时的，成为不平衡的二叉排序树。这时的平衡处理为：将平衡处理为：将A A逆时针旋转，成为逆时针旋转，成为B B的
24、左子树，的左子树，而原来而原来B B的左子树则变成的左子树则变成A A的右子树，待扦入结点的右子树，待扦入结点C C成为成为B B的右子树。的右子树。平衡处理平衡处理C C B B A A 0 0 0 0 0 0 -1 1 C C B B A A 0 0-2 2 RRRR型平衡处理型平衡处理第39页/共105页40非平衡二叉树的调整非平衡二叉树的调整RLRL型的处理型的处理(右左型右左型)在在A A的右孩子的右孩子C C上扦入一个左孩子上扦入一个左孩子B B，使，使A A的平衡因的平衡因子由子由-1-1变成变成-2-2，成为不平衡的二叉排序树。这时的，成为不平衡的二叉排序树。这时的平衡处理为：
25、将平衡处理为：将B B变到变到A A与与C C之间，使之成为之间，使之成为RRRR型，型，然后按第然后按第(3)(3)种情形种情形RRRR型处理。型处理。平衡处理平衡处理C C B B A A 0 0 0 0 0 0 -1 1-2 2 C C B B A A 旋转旋转 B B 0 0 1 1-2 2 A A C C RLRL型平衡处理型平衡处理第40页/共105页41非平衡二叉树的生成举例非平衡二叉树的生成举例给定一个关键字序列给定一个关键字序列4,5,7,2,1,3,64,5,7,2,1,3,6，试生成一棵，试生成一棵平衡二叉树。平衡二叉树。分析分析平衡二叉树实际上也是一棵二叉排序树，故可平
26、衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。最后就可以建成一棵平衡二叉树。第41页/共105页42非平衡二叉树的生成举例非平衡二叉树的生成举例(c)(c)插入插入 7 7 RRRR 型型 (a)(a)插入插入 4 4 4 4 0 0(b)(b)插入插入 5 5 4 4 5 5 0 0-1 1 7 7 4 4 5 5-2 2-1 1 0 0 0 0 0 0 4 4 5 5 7 7 0 0 第42页/共105页43
27、LLLL 型型(e e)插入插入 11 4 4 2 2 5 5 7 7 1 1 0 0 0 0 0 0 0 0 0 0 4 4 2 2 5 5 7 7 1 1 0 0 0 0 1 1 2 2 2 2 (d d)插入插入 2 2 4 4 2 2 5 5 7 7 0 0 0 0 1 1 1 1 非平衡二叉树的生成举例非平衡二叉树的生成举例第43页/共105页44 -1 1 5 5 2 2 1 1 4 4 3 3 7 7 2 2 0 0 1 1 0 0 0 0 5 5 2 2 1 1 4 4 3 3 7 7-1 1 0 0 0 0 0 0 0 0 0 0 LRLR 型型(f f)插入插入 3 3 非
28、平衡二叉树的生成举例非平衡二叉树的生成举例第44页/共105页45非平衡二叉树的生成举例非平衡二叉树的生成举例 5 5 2 2 1 1 4 4 3 3 7 7-2 2-1 1 0 0 1 1 0 0 0 0 6 6 0 0 RLRL型型 0 0 6 6 2 2 1 1 4 4 3 3 7 7 0 0 0 0 0 0 0 0 0 0 5 5 0 0(g g)插入插入6 6 第45页/共105页46平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析平衡二叉树本身就是一棵二叉排序树，故它的查平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同找与二叉排序树完全相同但它的查找但它的查找
29、性能优于二叉排序树，不像二叉排序性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度树一样，会出现最坏的时间复杂度O(n)O(n)它的时间复杂度与二叉排序树的最好时间复杂相它的时间复杂度与二叉排序树的最好时间复杂相同，都为同，都为O(log2n)O(log2n)。第46页/共105页47平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析对给定的关键字序列对给定的关键字序列4,5,7,2,1,3,64,5,7,2,1,3,6，试用二叉排，试用二叉排序树和平衡二叉树两种方法查找，给出查找序树和平衡二叉树两种方法查找，给出查找6 6的的次数及成功的平均查找长度。次数及成功的平均查找长度。
30、第47页/共105页48平衡二叉树的查找性能优于二叉排序树。平衡二叉树的查找性能优于二叉排序树。平衡二叉树的查找及性能分析平衡二叉树的查找及性能分析从上图的二叉排序树可知，查找从上图的二叉排序树可知，查找6 6需需4 4次，平均次，平均查找长度查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57ASL=(1+2+2+3+3+3+4)/7=18/72.57。从上图的平衡二叉树可知，查找从上图的平衡二叉树可知，查找6 6需需2 2次，平均次，平均查找长度查找长度ASL=(1+2+2+3+3+3+3)=17/72.43ASL=(1+2+2+3+3+3+3)=17/72.43。第48页
31、/共105页49动态查找表 B-树 B-树是一种平衡的多路查找树，它在文件系统中很有用。下图为阶B-树第49页/共105页50B-B-树的定义树的定义一一棵棵mm阶阶的的B-B-树树，或或者者为为空空树树，或或为为满满足足下下列列特特性性的的mm叉树叉树树中每个结点至多有树中每个结点至多有mm棵子树棵子树若根结点不是叶子结点，则至少有两棵子树若根结点不是叶子结点，则至少有两棵子树除除根根结结点点之之外外的的所所有有非非终终端端结结点点至至少少有有 m/2m/2 棵棵子树子树第50页/共105页51B-B-树的定义树的定义有的非终端结点中包含以下信息数据：有的非终端结点中包含以下信息数据：(n(
32、n，A0A0，K1K1，A1A1，K2K2，KnKn，An)An)Ki（i=1,2,n）为关键字，且KiKi+1Ai为指向子树根结点的指针(i=0,1,n)，且指针Ai-1所指子树中所有结点的关键字均小于Ki(i=1,2,n)An所指子树中所有结点的关键码均大于Kn，m/21nm1，n为关键字的个数(或n+1为子树的个数)所有的叶子结点都出现在同一层次上，并且不带所有的叶子结点都出现在同一层次上，并且不带信息信息。第51页/共105页52注释：左图为非注释：左图为非B-B-树，右图为树，右图为B-B-树树 B-B-树的定义树的定义第52页/共105页53typedefstructBTNodet
33、ypedefstructBTNodeintkeynum;intkeynum;/结点中关键字个数，结点大小结点中关键字个数，结点大小structBTNode*parent;structBTNode*parent;/指向双亲结点的指针指向双亲结点的指针KeyTypekeym+1;KeyTypekeym+1;/关键字（关键字（0 0号单元不用）号单元不用）structBTNode*ptrm+1;structBTNode*ptrm+1;/子树指针向量子树指针向量Record*recptrm+1;Record*recptrm+1;/记录指针向量记录指针向量 BTNode,*BTree;BTNode,*B
34、Tree;/B/B树结点和树结点和B B树的类型树的类型B-B-树的类型定义树的类型定义第53页/共105页54B-B-树的查找算法树的查找算法有有从根结点出发，沿指针搜索结点和在结点内进从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。行顺序（或折半）查找两个过程交叉进行。若查找成功，则返回指向被查关键字所在结点的若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置指针和关键字在结点中的位置若查找不成功，则返回插入位置。若查找不成功，则返回插入位置。第54页/共105页55B-B-树的插入树的插入关键字插入的位置必定在最下层的非叶结点，有关键字插入
35、的位置必定在最下层的非叶结点，有下列几种情况插入后，该结点的关键字个数下列几种情况插入后，该结点的关键字个数nmnm，不修改指针，不修改指针插入后，该结点的关键字个数插入后，该结点的关键字个数 n=mn=m，则需进行则需进行“结点分裂结点分裂”，令，令 s=s=m/2m/2，在原结点中保留，在原结点中保留A0A0，K1K1，Ks-1Ks-1，As-1As-1）；建新结点）；建新结点AsAs，Ks+1Ks+1，KnKn，AnAn）；）；将（将（KsKs，p p）插入双亲结）插入双亲结点；点；若双亲为空，则建新的根结点。若双亲为空，则建新的根结点。第55页/共105页56例如例如:下列为下列为 3
36、3阶阶B-B-树树50204080插入关键字=60,608090,6080909050806030,4020305080803050第56页/共105页57分两种情况(1)删除最底层结点中关键字(2)删除为非底层结点中关键字若所删除关键字非底层结点中的Ki，则可以指针Ai所指子树中的最小关键字X替代Ki，然后，再删除关键字X，直到这个X在最底层结点上，即转为(1)的情形。B-B-树的删除树的删除第57页/共105页58删除删除5555B-B-树的删除简单删除树的删除简单删除第58页/共105页59删除删除6565B-B-树的删除结点联合调整树的删除结点联合调整第59页/共105页60删除删除7
37、070B-B-树的删除结点联合调整树的删除结点联合调整第60页/共105页61B-B-树的删除结点联合调整树的删除结点联合调整第61页/共105页62B-B-树的删除结点联合调整树的删除结点联合调整第62页/共105页63B-B-树的删除非叶结点删除树的删除非叶结点删除第63页/共105页64B-B-树的删除非叶结点删除树的删除非叶结点删除第64页/共105页65B-B-树的删除非叶结点删除树的删除非叶结点删除第65页/共105页66B-B-树的删除非叶结点删除树的删除非叶结点删除第66页/共105页67B+树是应文件系统所需而产生的一种B-树的变形树m阶的B+树和m阶的B-树的差异在于有n棵
38、子树的结点中含有n个关键字所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。B+B+树树第67页/共105页68哈希表查找引入哈希表查找引入前几节讨论的查找方法特点前几节讨论的查找方法特点记记录录在在表表中中的的位位置置和和它它的的关关键键字字之之间间不不存存在在一一个个确确定定的的关关系系，查查找找的的过过程程为为给给定定值值依依次次和和关关键字集合中各个关键字进行比较。、键字集合中各个关键字进行比较。、查查找找的的效效率率取取决决于于和和给
39、给定定值值进进行行比比较较的的关关键键字字个数个数第68页/共105页69哈希表查找引入哈希表查找引入理理想想的的情情况况是是依依据据关关键键字字直直接接得得到到其其对对应应的的数数据据元元素素位位置置，即即要要求求关关键键字字与与数数据据元元素素间间存存在在一一一一对对应应关关系系，通通过过这这个个关关系系，不不需需要要经经过过比比较便可直接从顺序表中找到待查关键字。较便可直接从顺序表中找到待查关键字。哈希表查找哈希表查找哈希函数哈希函数在在记记录录的的关关键键字字与与记记录录的的存存储储地地址址之之间间建建立立的一种对应关系的一种对应关系第69页/共105页70哈希函数是一个映象，即：将关
40、键字的集合映射到某个地址集合上。由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1key2，而f(key1)=f(key2)。很难找到一个不产生冲突的哈希函数哈希表查找的理解哈希表查找的理解第70页/共105页71哈希表的定义哈希表的定义根据设定的哈希函数根据设定的哈希函数 H(key)H(key)和所选中的处理冲和所选中的处理冲突的方法，将一组关键字映象到一个有限的、突的方法，将一组关键字映象到一个有限的、地址连续的地址集地址连续的地址集(区间区间)上，并以关键字在地上，并以关键字在地址集中的址集中的“象象”作为相应记录在表中的存储位作为相应记录在表中的存储
41、位置置如此构造所得的查找表称之为如此构造所得的查找表称之为“哈希表哈希表”。第71页/共105页72例：例：3030个地区的各民族人口统计表个地区的各民族人口统计表编号编号地区别地区别总人口总人口汉族汉族回族回族.11北京北京22上海上海.以编号作关键字，以编号作关键字，构造构造哈希函数：哈希函数：H(key)=keyH(key)=keyH(1)=1H(1)=1H(2)=2H(2)=2以地区别作关键字，取以地区别作关键字，取地区名称第一个拼音字地区名称第一个拼音字母的序号母的序号作哈希函数：作哈希函数：H(Beijing)=2H(Beijing)=2H(Shanghai)=19H(Shangh
42、ai)=19H(Shenyang)=19H(Shenyang)=19第72页/共105页73哈希方法需要解决以下两个问题构造好的哈希函数所选函数尽可能简单,以便提高转换速度。所选函数对关键字计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。制定解决冲突的方案。哈希方法需要解决的问题哈希方法需要解决的问题第73页/共105页74构造哈希函数的方法构造哈希函数的方法对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法直接定址法直接定址法数字分析法数字分析法平方取中法平方取中法折叠法折叠法除留余数法除留余数法随机数法随机数法若是非数字关键字，则需先对其进行数字化处理若是非数字关键字
43、，则需先对其进行数字化处理第74页/共105页75 构造哈希函数的方法实实际际造造表表时时，采采用用何何种种构构造造哈哈希希函函数数的的方方法法取取决决于于建建表表的的关关键键字字集集合合的的情情况况(包包括括关关键键字字的的范范围围和和形态形态)总的原则是使产生冲突的可能性降到尽可能地小总的原则是使产生冲突的可能性降到尽可能地小第75页/共105页76 常用的哈希函数常用的哈希函数-直接定址法直接定址法哈希函数为关键字的线性函数哈希函数为关键字的线性函数 H(key)=keyH(key)=key或者或者H(key)=aH(key)=a key+bkey+b此法仅适合于此法仅适合于地址集合的大
44、小地址集合的大小=关键字集合的大小关键字集合的大小第76页/共105页77 常用的哈希函数常用的哈希函数-数字分析法数字分析法假设关键字集合中的每个关键字都是由假设关键字集合中的每个关键字都是由 ss位数字位数字组成组成(u1,u2,us)(u1,u2,us)，分析关键字集中的全体，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为并从中提取分布均匀的若干位或它们的组合作为地址。地址。此法仅适合于此法仅适合于能预先估计出全体关键字的每一位上各种数字能预先估计出全体关键字的每一位上各种数字出现的频度。出现的频度。第77页/共105页78 例例：有：有8080个记录，关键字为个记录，
45、关键字为8 8位十进制数，哈希地址位十进制数，哈希地址为为2 2位十进制数位十进制数81346532813465328137224281372242813874228138742281301367813013678132281781322817813389678133896781368537813685378141935581419355.分析：分析：只取只取8 8只取只取1 1只取只取3 3、4 4只取只取2 2、7 7、5 5数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位与另两位的叠加作哈希地与另两位的叠加作哈希地址址常用的哈希函数常用的哈希函数-数字分析法数
46、字分析法第78页/共105页79 常用的哈希函数常用的哈希函数-平方取中法平方取中法假假以关键字的平方值的中间几位作为存储地址。以关键字的平方值的中间几位作为存储地址。求求“关键字的平方值关键字的平方值”的目的是的目的是“扩大差别扩大差别”，同时平方值的中间各位又能受到整个关键字中，同时平方值的中间各位又能受到整个关键字中各位的影响。各位的影响。此法仅适合于此法仅适合于关键字中的每一位都有某些数字重复出现频度关键字中的每一位都有某些数字重复出现频度很高的现象。很高的现象。第79页/共105页80 常用的哈希函数常用的哈希函数-折叠折叠假假将关键字分割成若干部分，然后取它们的叠加将关键字分割成若
47、干部分，然后取它们的叠加和为哈希地址。和为哈希地址。处理的方法处理的方法移位叠加移位叠加间界叠加间界叠加此法仅适合于此法仅适合于关键字的数字位数特别多关键字的数字位数特别多第80页/共105页81 例：关键字为例：关键字为：04422058640442205864，哈希地址位数为，哈希地址位数为4 4586458644220422004041 100880088H(key)=0088H(key)=0088移位叠加移位叠加5864586402240224040460926092H(key)=6092H(key)=6092间界叠加间界叠加常用的哈希函数常用的哈希函数-折叠折叠第81页/共105页8
48、2 常用的哈希函数常用的哈希函数-除留余数法除留余数法假设定哈希函数为假设定哈希函数为H(key)=keyMODpH(key)=keyMODp其中，其中，pm(pm(表长表长)并且并且p p应为不大于应为不大于 mm的素数的素数或是不含或是不含2020以下的质因子以下的质因子此法经常使用此法经常使用第82页/共105页83 常用的哈希函数常用的哈希函数-随机数随机数设定哈希函数为设定哈希函数为:H(key)=Random(key)H(key)=Random(key)其中，其中，RandomRandom为伪随机函数通常为伪随机函数通常此方法用于对长度不等的关键字构造哈希函数。此方法用于对长度不等
49、的关键字构造哈希函数。第83页/共105页84选取哈希函数，考虑以下因素：计算哈希函数所需时间关键字长度哈希表长度（哈希地址范围）关键字分布情况记录的查找频率构造哈希函数的方法构造哈希函数的方法第84页/共105页85“处理冲突处理冲突”的实际含义是的实际含义是为产生冲突的地址寻找下一个哈希地址为产生冲突的地址寻找下一个哈希地址处理冲突方法有处理冲突方法有开放定址法开放定址法 链地址法（拉链法链地址法（拉链法 ）建立一个公共溢出区建立一个公共溢出区处理冲突的方法处理冲突的方法第85页/共105页86由关键字得到的哈希地址一旦产生了冲突，也就由关键字得到的哈希地址一旦产生了冲突，也就是说，该地址
50、已经存放了数据元素，就去寻找下是说，该地址已经存放了数据元素，就去寻找下一个空的哈希地址。一个空的哈希地址。只要哈希表足够大，空的哈希地址总能找到，并只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入将数据元素存入。处理冲突的方法处理冲突的方法-开放定址法开放定址法第86页/共105页87Hi=(Hash(key)+di)modmHi=(Hash(key)+di)modm(1im)(1im)其中：其中：Hash(key)Hash(key)为哈希函数为哈希函数mm为哈希表长度为哈希表长度didi为增量序列为增量序列 1 1，2 2，m-1m-1，且，且di=idi=i开放定址法开放定址法线