数据结构-从概念到C++实现（第4版）课件 第六章 查找技术

6-1查找概述v第六章查找技术关键码数据元素、结点、顶点关键码：可以标识一个记录的某个数据项键值：关键码的值56女李爽000535女齐梅000457女刘楠000335男张亮000248男王刚0001年龄性别姓名职工号1982.92003.71979.92003.71990.4工作时间主关键码：可以唯一标识一个记录的关键码次关键码：不能唯一标识一个记录的关键码什么是查找查找：在相同类型的记录构成的集合中找出满足给定条件的记录50女李爽000525女齐梅000447女刘楠000325男张亮000238男王刚0001年龄性别姓名职工号1972.92003.71979.92003.71990.4工作时间查找的结果：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败给定的查找条件可能是多种多样的把查找条件限制为“匹配”，即查找关键码等于给定值的记录

静态查找：不涉及插入和删除操作的查找动态查找要求插入、删除、查找均有较好的效率，适用于：查找与插入和删除操作在同一个阶段进行例如：当查找成功时，要删除查找到的记录当查找不成功时，要插入被查找的记录动态查找：涉及插入和删除操作的查找静态查找只注重查找效率，适用于：（1）查找集合一经生成，便只对其进行查找，而不进行插入和删除操作（2）经过一段时间的查找之后，集中地进行插入和删除等修改操作查找的分类查找结构查找结构：面向查找操作的数据结构，即查找基于的数据结构查找结构

查找方法

已经有了数据结构的概念，为什么要强调查找结构？（1）几乎所有的数据结构都提供了查找作为基本操作，但对于数据结构整体来说，查找并不是最重要的操作（3）数据结构+算法=程序：不同的查找结构，会获得不同的查找效率（2）对于查找结构来说，查找是最重要的基本操作，重要的是查找效率线性表：适用于静态查找，顺序查找、折半查找等技术树表：适用于动态查找，二叉搜索树的查找技术散列表：静态查找和动态查找均适用，采用散列技术查找基于的数据模型是什么？集合集合注意到，都是把集合组织成XXX表，为什么？理解起来，集合最常用的表示法是列举法，习惯上，也称为表查找结构平均查找长度如何评价查找算法的效率呢？和关键码的比较次数关键码的比较次数与哪些因素有关呢？其中：n：问题规模，查找集合中的记录个数

pi：查找第i个记录的概率ci：查找第i个记录所需的关键码的比较次数ASLå==niiicp1平均查找长度：查找算法进行的关键码比较次数的数学期望值pi与算法无关，取决于具体应用ci取决于算法如果pi是已知的，则平均查找长度只是问题规模的函数6-2线性表的查找技术v第六章查找技术线性表查找结构的类定义学什么？顺序查找折半查找类定义constintMaxSize=100;classLineSearch{public:LineSearch(inta[],intn);//构造函数~LineSearch(){}//析构函数为空intSeqSearch(intk);//顺序查找intBinSearch(intk);//折半非递归查找intBinSearchRecursion(intlow,inthigh,intk);//折半递归查找private:intdata[MaxSize];//查找集合为整型intlength;//查找集合的元素个数};LineSearch::LineSearch(inta[],intn){for(inti=0;i<n;i++)data[i]=a[i];length=n;}不失一般性，假定待查找集合的记录为int型6-2-2顺序查找v第六章查找技术基本思想顺序查找（线性查找）：从线性表的一端向另一端逐个将记录与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的记录，则查找失败，给出失败信息i10152461235409855012345678例1查找35，查找25intLineSearch::SeqSearch(intk){inti=0;

while(i<length&&data[i]!=k)i++;if(i<length)returni+1;elsereturn0;}改进的顺序查找顺序查找的改进：设置“哨兵”，就是待查值，放在查找方向的尽头处，免去了每一次比较后都要判断查找位置是否越界intLineSearch::SeqSearch(intk){inti=0;

while(i<length&&data[i]!=k)i++;if(i<length)returni+1;elsereturn0;}例2查找35，查找25intLineSearch::SeqSearch(intk){inti=length;

data[length]=k;while(data[i]!=k)i++;if(i<length)returni+1;elsereturn0;}查找方向10152461235409855k0123456789顺序查找的性能查找成功：查找不成功：特别是当待查找集合中元素较多时，不推荐使用顺序查找顺序查找的缺点：查找效率较低（1）对表中记录的存储没有任何要求，顺序存储和链接存储均可（2）对表中记录的有序性也没有要求，无论记录是否按关键码有序均可顺序查找的优点：算法简单而且使用面广6-2-3折半查找v第六章查找技术基本思想折半查找（对半查找、二分查找）：在有序表（假设为递增）中，取中间记录作为比较对象：（1）若给定值与中间记录相等，则查找成功；（2）若给定值小于中间记录，则在有序表的左半区继续查找；（3）若给定值大于中间记录，则在有序表的右半区继续查找。不断重复上述过程，直到查找成功，或查找区域无记录，查找失败

[r1………rmid-1]rmid[rmid+1………rn]k（mid=(1+n)/2）如果k<rmid查找左半区如果k>rmid查找右半区

71418212329313538012345678lowhigh例3

对于线性表(7,14,18,21,23,29,31,35,38)，元素18的查找过程：查找区间[0,8]midhigh查找区间[0,3]midlow查找区间[2,3]mid查找成功运行实例lowhigh查找区间[0,8]midhigh查找区间[0,3]midlow查找区间[2,3]mid查找区间[2,1]highlow>high，查找失败

71418212329313538012345678运行实例例4

对于线性表(7,14,18,21,23,29,31,35,38)，元素15的查找过程：intLineSearch::BinSearch(intk){}非递归算法

return0;/*查找失败，返回0*/intmid,low=0,high=n-1;/*初始查找区间是[0,n-1]*/while(low<=high)/*当区间存在时*/{}mid=(low+high)/2;if(k<data[mid])high=mid-1;elseif(k>data[mid])low=mid+1;elsereturnmid+1;/*查找成功，返回元素序号*/递归算法lowhighmidintLineSearch::BinSearchRecursion(intlow,inthigh,intk){}if(k<r[mid])returnBinSearchRecursion(low,mid-1,k);elseif(k>r[mid])returnBinSearchRecursion(mid+1,high,k);elsereturnmid+1;/*查找成功，返回序号*/

71418212329313538012345678if(low>high)return0;/*递归的边界条件*/mid=(low+high)/2;判定树判定树（折半查找判定树）：描述折半查找判定过程的二叉树（1）当low＞high时，判定树为空；（2）当low≤high时，判定树的根结点是有序表中序号为mid=(low+high)/2的记录，根结点的左子树是与有序表r[low]~r[mid-1]相对应的判定树，根结点的右子树是与有序表r[mid+1]~r[high]相对应的判定树。设查找区间是[low,high]，判定树的构造方法：Page02显然，构造过程是递归定义的例5

设结点个数（查找集合的记录个数）为11，请画出对应的判定树。3构造6的左子树，区间[1,5]查找区间[1,11]，中间记录的序号是6645构造3的左子树，区间[1,2]12构造3的右子树区间[4,5]判定树3611845129构造6的右子树，区间[7,11]7构造9的左子树区间[7,8]10构造9的右子树区间[10,11]例5

设结点个数（查找集合的记录个数）为11，请画出对应的判定树。判定树折半查找性能分析3691011784512查找记录的过程是从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。查找第4个元素比较多少次？查找长度是4的元素有多少个？查找成功情况下，与判定树的深度有关，判定树的深度是多少呢？判定树深度为时间复杂度为O(log2n)比较次数至多为33~4~11~22~34~510~1111~9~108~97~85~66~7691011784512如何确定查找失败呢？例如查找的元素比第3个元素大比第4个元素小？查找不成功的过程是从根结点到外部结点的路径，和给定值进行的比较次数等于该路径上内部结点的个数。折半查找性能分析33~4~11~22~34~510~1111~9~108~97~85~66~7691011784512查找成功的平均比较次数=(1×1+2×2+3×4+4×4)/11=3查找不成功的平均比较次数=(3×4+4×8)/12=11/3折半查找性能分析6-3树表的查找技术v第六章查找技术树表的提出如何在一个大型的数据集合上进行动态查找？顺序查找：不要求元素的有序性，插入、删除的性能是O(1)

查找性能是O(n)折半查找：查找性能是O(log2n)

为保证元素的有序性，插入、删除要移动元素，性能是O(n)有没有一种查找结构，使得插入、删除、查找均具有较好效率？树表：将查找集合组织成树的结构二叉搜索树二叉搜索树学什么？平衡二叉树B树6-3-1二叉搜索树v第六章查找技术二叉搜索树的定义二叉搜索树（二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值（3）它的左右子树也都是二叉搜索树6360554258254565857063905542582545658570二叉搜索树是记录之间满足某种大小关系的二叉树写出二叉搜索树的中序遍历序列？中序遍历序列：25424555586365708590升序序列二叉排序树63905542582545658570二叉搜索树的定义二叉搜索树的存储如何存储二叉搜索树？二叉链表45635590425870256585∧∧∧∧∧∧∧∧∧∧∧63905542582545658570二叉搜索树的类定义classBiSortTree

{public:BiSortTree(inta[],intn);~BiSortTree(){Release(root);}BiNode<int>*InsertBST(intx){returnInsertBST(root,x);}voidDeleteBST(BiNode<int>*p,BiNode<int>*f);BiNode<int>*SearchBST(intk){returnSearchBST(root,k);}private:

BiNode<int>*InsertBST(BiNode<int>*bt,intx);

BiNode<int>*SearchBST(BiNode<int>*bt,intk);

voidRelease(BiNode<DataType>*bt);

BiNode<int>*root;};不失一般性，假定待查找集合的记录为int型二叉搜索树的查找在二叉搜索树中查找给定值k

的过程是（1）若bt是空树，则查找失败；（2）若k＝bt->data，则查找成功；（3）若k＜bt->data，则在bt的左子树上查找；（4）若k>

bt->data，在bt的右子树上查找。二叉搜索树的查找效率在于只需查找二个子树之一63554265854525907058554245BiNode<int>*BiSortTree::SearchBST(BiNode<int>*bt,intk){if(bt==nullptr)returnnullptr;if(bt->data==k)returnbt;elseif(bt->data>k)returnSearchBST(bt->lchild,k);elsereturnSearchBST(bt->rchild,k);}如何在二叉搜索树中插入一个元素？例如，插入986355905870∧∧∧6390557058∧∧∧9898∧∧若二叉搜索树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。二叉搜索树的插入BiNode<int>*BiSortTree::InsertBST(BiNode<int>*bt,intx){if(bt==nullptr){BiNode<int>*s=newBiNode<int>;s->data=x;s->lchild=s->rchild=nullptr;bt=s;returnbt;}elseif(bt->data>x)bt->lchild=InsertBST(bt->lchild,x);elsebt->rchild=InsertBST(bt->rchild,x);}63root∧∧55∧∧90∧∧二叉搜索树的插入插入元素63插入元素90插入元素55BiSortTree::BiSortTree(inta[],intn){root=nullptr;for(inti=0;i<n;i++)root=InsertBST(root,a[i]);}63554265854525907058例1给定查找集合{63,55,42,45,58,90,70,25,85,65}，构造二叉搜索树（1）每次插入的新结点都是二叉搜索树上新的叶子结点;（2）找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；（3）在左子树/右子树的查找过程与在整棵树上查找过程相同；（4）新插入的结点没有破坏原有结点之间的关系。二叉搜索树的构造如何在二叉搜索树中删除一个元素？（1）从二叉搜索树中删除一个结点之后，要仍然保持二叉搜索树的特性；63554265854525907058（2）当删除分支结点时破坏了二叉搜索树中原有结点之间的链接关系，需要重新修改指针，使得删除结点后仍为一棵二叉搜索树。二叉搜索树的删除63554265854525907058情况1——被删除的结点是叶子结点不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子pf操作：将双亲结点中相应指针域的值改为空。f->lchild=nullptr;6355428545259070f58二叉搜索树的删除635542854525907058情况2——被删除的结点只有左子树或者只有右子树pf操作：将双亲结点中相应指针域指向被删除结点的左子树（或右子树）f->lchild=p->rchild;63554245259085pf二叉搜索树的删除不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子635542854525907058情况3——被删除的结点既有左子树也有右子树p操作：以其左子树中的最大值结点替换之，然后再删除该结点sparBiNode*par=p,*s=p->lchild;while(s->rchild!=nullptr){par=s;s=s->rchild;}585542854525907056ppar56p->data=s->data;par->rchild=s->lchild;二叉搜索树的删除不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子6355428545259070pspar特殊情况：左子树中的最大值结点是被删结点的孩子55428545259070psif(p==par)par->lchild=s->lchild;情况3——被删除的结点既有左子树也有右子树二叉搜索树的删除操作：以其左子树中的最大值结点替换之，然后再删除该结点不失一般性，设待删除结点为p，其双亲结点为f，且p是f的左孩子二叉搜索树的性能分析在二叉搜索树中执行插入和删除操作查找插入和删除的位置修改相应指针插入、删除、查找的时间复杂度相同二叉搜索树的查找性能取决于什么？63554265854525907058554245比较次数不超过树的深度二叉搜索树的深度是多少？取决于什么？对于查找集合{40,35,30,25,20,15}，构造的二叉搜索树深度为n403530152520平均比较次数=(1+2+3+4+5+6)/6=21/6对于查找集合{15,20,25,30,35,40}，构造的二叉搜索树深度为403530152520平均比较次数=(1×1+2×2+3×3)/6=14/6最坏情况：退化为线性查找最好情况：相当于折半查找平均情况：O(n)~O(log2n)查找集合的初始排列二叉搜索树的性能分析6-3-2平衡二叉树v第六章查找技术平衡二叉树的提出完全二叉树的深度：1234568910712345689107左右子树的深度相同二叉搜索树的深度取决于给定查找集合的排列，即结点的插入顺序具有n

个结点的二叉搜索树，最小深度是多少？有什么特征？对于查找集合的任意排列，如何得到一棵深度尽可能小的二叉搜索树？二叉搜索树的深度取决于给定查找集合的排列，即结点的插入顺序具有n

个结点的二叉搜索树，最小深度是多少？有什么特征？左右子树的深度相同维护最小深度的二叉搜索树的代价太大左右子树的深度相差1完全二叉树的深度：平衡二叉树的深度：平衡二叉树的提出平衡因子：该结点的左子树的深度减去右子树的深度5482548210110-12200平衡二叉树：是一棵空的二叉搜索树，或者具有下列性质的二叉搜索树：（1）根结点的左子树和右子树的深度最多相差1;（2）根结点的左子树和右子树也都是平衡二叉树在平衡二叉树中，结点的平衡因子是1、0或-1平衡二叉树非平衡二叉树平衡二叉树的定义最小不平衡子树最小不平衡子树：以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树3-1210如何调整最小不平衡子树呢？插入一个结点会影响哪些结点的平衡因子？548269010000且入且判断，一旦失衡立即调整只调整最小不平衡子树，并且不影响其他结点4平衡调整算法算法：平衡调整输入：平衡二叉树，新插入结点A输出：新的平衡二叉树1.找到最小不平衡子树的根结点D2.根据结点A和结点D之间的关系，判断调整类型3.根据类型、遵循扁担原理和旋转优先原则进行相应调整

（1）LL型、RR型：调整一次

（2）LR型、RL型：调整两次LL型的平衡调整403520012例1设序列{40,35,20}，构造平衡二叉树40352040新插入结点20和最小不平衡子树根结点40之间的关系——LL型扁担原理：将根结点看成是扁担中肩膀的位置hBLhBRhARABX插入结点X失去平衡调整后重新平衡h+1BLhARBRhBAX例2设序列{40,35,20,15,25,10}，构造平衡二叉树40352001240352040新插入结点10和最小不平衡子树根结点35之间的关系——LL型扁担原理：将根结点看成是扁担中肩膀的位置152510101235旋转优先：旋转下来的结点作为新根结点的孩子402015103525LL型的平衡调整2035400-1-2例3设序列{20,35,40}，构造平衡二叉树20203540新插入结点40和最小不平衡子树根结点20之间的关系——RR型扁担原理：将根结点看成是扁担中肩膀的位置RR型的平衡调整例4设序列{20,35,40,38,45,50}，构造平衡二叉树2035400-1-220352040新插入结点50和最小不平衡子树根结点35之间的关系——RR型扁担原理：将根结点看成是扁担中肩膀的位置38455035旋转优先：旋转下来的结点作为新根结点的孩子204045503538RR型的平衡调整例5设序列{35,40,20,15,30,25}，构造平衡二叉树352040新插入结点25和最小不平衡子树根结点35之间的关系——LR型扁担原理：将根结点看成是扁担中肩膀的位置15302535旋转优先：旋转下来的结点作为新根结点的孩子20152530354035第1次调整LR型的平衡调整第2次调整252015304035例6设序列{35,20,30}，构造平衡二叉树3520新插入结点30和最小不平衡子树根结点35之间的关系——LR型扁担原理：将根结点看成是扁担中肩膀的位置3035203035第1次调整第2次调整203035LR型的平衡调整例7设序列{35,45,20,50,40,38}，构造平衡二叉树352045新插入结点38和最小不平衡子树根结点35之间的关系——RL型扁担原理：将根结点看成是扁担中肩膀的位置4050383538402035第1次调整4550RL型的平衡调整第2次调整404550203538旋转优先：旋转下来的结点作为新根结点的孩子6-3-3B树v第六章查找技术B树的定义B树：一棵m阶的B树或者为空树，或者为满足下列特性的m叉树：（1）每个结点至多有

m棵子树；（2）根结点至少有两棵子树；（3）除根结点和叶子结点外，所有结点至少有

m/2

棵子树；1181112

213013924753199342

58701351654阶B树子树个数2~4（4）所有结点都包含以下数据：

（n，A0，K1，A1，K2，…，Kn，An）其中，n（

m/2

1≤n≤m

1）为关键码的个数，Ki（1≤i≤n）为关键码，且Ki＜Ki+1（1≤i≤n-1），Ai（0≤i≤n）为指向子树根结点的指针，且指针Ai所指子树中所有结点的关键码均小于Ki+1大于Ki。1181112

21301392

4753199342

58

701351654阶B树关键码个数1~3B树：一棵m阶的B树或者为空树，或者为满足下列特性的m叉树：B树的定义（5）叶子结点都在同一层；叶子结点都在同一层树高平衡具有较高的查找效率失败结点叶子结点1181112

213013924753199342

5870135165FFFFFFFFFFFFFFB树的定义B树：一棵m阶的B树或者为空树，或者为满足下列特性的m叉树：假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：（1）定位：确定关键码key应该插入哪个叶子结点并返回该结点的指针p。

若

p中的关键码个数小于n，则直接插入关键码key；

否则，结点

p的关键码个数溢出，执行“分裂——提升”过程。B树是多少阶？m=3,

n=2656020408010222850759096新关键码插入到相应的叶子结点B树的插入（1）定位：确定关键码key应该插入哪个终端结点并返回该结点的指针p。

若

p中的关键码个数小于n，则直接插入关键码key；

否则，结点

p的关键码个数溢出，执行“分裂——提升”过程。60204080102228509096657570发生溢出假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入B树是多少阶？m=3,n=26020401022285090966575分裂—提升（2）分裂——提升：将结点

p“分裂”成两个结点，分别是p1和p2，把中间的关键码k“提升”到父结点，并且k的左指针指向p1，右指针指向p2。7080B树是多少阶？m=3,n=2假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入60204010222850909665757080（2）分裂——提升：如果父结点的关键码个数也溢出，则继续执行“分裂——提升”过程。显然，这种分裂可能一直上传，如果根结点也分裂了，则树的高度增加了一层。30B树是多少阶？m=3,n=2发生溢出假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入602028401050909665757080（2）分裂——提升：如果父结点的关键码个数也溢出，则继续执行“分裂——提升”过程。显然，这种分裂可能一直上传，如果根结点也分裂了，则树的高度增加了一层。分裂——提升，再次溢出2230假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入B树是多少阶？m=3,n=21050909665757080（2）分裂——提升：如果父结点的关键码个数也溢出，则继续执行“分裂——提升”过程。显然，这种分裂可能一直上传，如果根结点也分裂了，则树的高度增加了一层。再次分裂——提升22302040假定在

m阶B树中插入关键码key，设n=m-1，插入过程如下：B树的插入B树是多少阶？m=3,n=22860如果在B树中插入一个元素时导致根结点发生溢出，则B树产生一个新的根结点并且树高增加了一层，此时，新根只有一个关键码和两棵子树。为什么B树的根结点最少有两棵子树？105090966575708022302860204095105065752230204090967095288060B树的插入如何删除二叉搜索中的一个结点？情况1——被删除的结点是叶子结点65635542854525907058情况3——被删除的结点既有左子树也有右子树585542854525907055428545259070586363B树的删除假定在

m阶B树中删除关键码key，删除过程如下：（1）定位：确定关键码key在哪个结点并返回该结点的指针q。

假定key是结点

q中的第

i个关键码Ki，有以下两种情况：1.1若结点

q

是叶子结点，则删除key；

1.2若结点

q

不是叶子结点，则用

Ai所指子树中的最小值

x

替换Ki；删除x；

602040801022285090966575删除操作归结为在叶子结点中删除关键码B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；602040801022285090966575关键码个数是多少？

-1=1假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；60204080105090962.2否则，删除操作涉及到兄弟结点2.2.1兄弟结点的关键码个数大于，则向兄弟结点借一个关键码；222875假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；2.2否则，删除操作涉及到兄弟结点2.2.1兄弟结点的关键码个数大于，则向兄弟结点借一个关键码，并且借来的关键码“上移”到双亲结点，双亲结点相应关键码“下移”；6020

2880104090967522假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；2.2否则，删除操作涉及到兄弟结点2.2.2兄弟结点的关键码个数不大于，则执行“合并”兄弟操作；6020

2880104090967522假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；2.2否则，删除操作涉及到兄弟结点2.2.2兄弟结点的关键码个数不大于，则执行“合并”兄弟操作；删除空结点，并将双亲结点中的相应关键码“下移”到合并结点中；60801090967522

2820假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；2.2否则，删除操作涉及到兄弟结点2.2.2兄弟结点的关键码个数不大于，则执行“合并”兄弟操作；如果双亲结点的关键码个数发生下溢，则双亲结点也要进行借关键码或合并操作608010909675202210206080909675如果根结点的两个孩子结点进行合并，则B树就会减少一层假定在

m阶B树中删除关键码key，删除过程如下：B树的删除（1）定位：确定关键码key在哪个结点并返回该结点的指针q。

假定key是结点

q中的第

i个关键码Ki，有以下两种情况：1.1若结点

q

是叶子结点，则删除key；

1.2否则用

Ai所指子树中的最小值

x

替换Ki；删除x；

（2）判断是否下溢2.1如果叶子结点中关键码的个数大于

-1，则直接删除；

2.2否则，删除操作涉及到兄弟结点2.2.1兄弟结点的关键码个数大于，则向兄弟结点借一个关键码，

并且借来的关键码“上移”到双亲结点，双亲结点相应关键码“下移”；

2.2.2否则执行“合并”兄弟操作；删除空结点，并将双亲结点中的相应关键码“下移”到合并结点中；假定在

m阶B树中删除关键码key，删除过程如下：B树的删除6-4散列表的查找技术v第六章查找技术回顾查找技术查找操作要完成什么任务？待查值k确定k在存储结构中的位置前面学过哪些查找技术？这些查找技术有什么共性呢？10152461235409855012345678（1）顺序查找（2）折半查找101520253035404550012345678==、!=<、==、>O(n)O(log2n)O(n)~(log2n)635542907058（3）二叉搜索树查找通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数Ω(log2n)查找技术的分类能否不用比较，通过关键码能够直接确定存储位置？在存储位置和关键码之间建立一个确定的对应关系查找技术比较式查找计算式查找设关键码key在存储结构中的位置是addr，则有addr=H(key)。

学什么？散列查找的基本思想散列函数的设计处理冲突的方法散列查找的性能分析开散列表与闭散列表的比较6-4-1散列查找的基本思想v第六章查找技术散列的基本思想关键码集合ri…………H(ki)Hki散列的基本思想：在记录的关键码和存储地址之间建立一个确定的对应关系，通过计算得到待查记录的地址。散列技术能进行范围查找吗？适合于哪种类型的查找？散列技术最适合回答的问题是：如果有的话，哪个记录的关键码等于待查值？散列的基本概念关键码集合ri…………H(ki)Hki散列表：采用散列技术存储查找集合的连续存储空间。散列表数组散列函数：将关键码映射为散列表中适当存储位置的函数。散列函数散列地址：由散列函数所得的存储地址。散列地址下标散列的关键问题关键码集合ri…………H(ki)Hki如何设计散列函数？如何解决冲突？冲突：对于两个不同关键码ki≠kj，有H(ki)＝H(kj)。同义词：ki和kj相对于H称做同义词。

kj散列是一种完整的存储结构吗？散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是面向查找的存储结构。6-4-2散列函数的设计v第六章查找技术设计原则关键码集合ri…………H(ki)Hki如何设计散列函数？（1）计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。（2）地址均匀。函数值要尽量均匀散布在地址空间，保证存储空间的有效利用并减少冲突。Hash哈希杂凑散列散列技术名称的演变过程：常见的散列函数散列函数是关键码的线性函数，即：H(key)=a

key+b（a，b为常数）例1关键码集合为{10,30,50,70,80,90}，选取的散列函数为H(key)=key/10，散列表构造过程如下：0123456789103050708090直接定址法适用于：事先知道关键码，关键码集合不是很大且连续性较好平方取中法对关键码平方后，按散列表大小，取中间的若干位作为散列地址。适用于：事先不知道关键码的分布且关键码的位数不是很大例2散列地址为2位，设计平方取中法的散列函数。(1234)2＝1522756(1235)2＝1525225平方扩大了相近数之间的差别常见的散列函数除留余数法H(key)=keymodp

如何选取p，才能产生较少的同义词？1470147014散列地址56494235282114关键码例如：p=21=3×777常见的散列函数例3散列表长为15，设计除留余数法的散列函数。

H(key)=keymod13适用于：最简单、最常用，不要求事先知道关键码的分布小于等于表长（最好接近表长）的最小素数或不包含小于20质因子6-4-3处理冲突的方法v第六章查找技术开放定址法开放定址法如何处理冲突？对于给定的关键码key执行下述操作：（1）计算散列地址：j=H(key)如何寻找一个空的散列地址呢？（3）如果在地址j发生冲突，则寻找一个空的散列地址，存储key对应的记录；（2）如果地址j

的存储单元没有存储记录，则存储key对应的记录；（1）线性探测法；（2）二次探测法；（3）随机探测法……闭散列表：用开放定址法处理冲突得到的散列表闭散列表的类定义constintMaxSize=100;classClosedHashTable{public:ClosedHashTable();~ClosedHashTable();intInsert(intk);intDelete(intk);intSearch(intk);private:intH();intht[MaxSize];};ClosedHashTable::ClosedHashTable(){for(inti=0;i<MaxSize;i++)ht[i]=0;}ClosedHashTable::~ClosedHashTable(){}线性探测法Hi=(H(key)＋di)%m

（di=1，2，…，m-1）

线性探测法：从冲突位置的下一个位置起，依次寻找空的散列地址。设散列表的长度为m，对于键值key，发生冲突时，寻找空散列地址的公式为：例1设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法处理冲突，散列表的构造过程如下：47729111692292222883333012345678910堆积：非同义词对同一个散列地址争夺的现象伪代码算法：Search输入：闭散列表ht[]，待查值k输出：如果查找成功，则返回记录的存储位置，否则返回查找失败的标志-11.计算散列地址j；2.探测下标i初始化：i=j；3.执行下述操作，直到ht[i]为空：3.1若ht[i]等于k，则查找成功，返回记录在散列表中的下标；3.2否则，i指向下一单元；4.查找失败，返回失败标志-1；算法实现intClosedHashTable::Search(intk){inti,j=H(k);//计算散列地址i=j;//设置比较的起始位置while(ht[i]!=0){if(ht[i]==k)returni;//查找成功elsei=(i+1)%m;//向后探测一个位置}return-1;//查找失败}二次探测法Hi=(H(key)＋di)%m

（di=12,-12,22,-22,…,q2,-q2(q≤m/2)）二次探测法：以冲突位置为中心，跳跃式寻找空的散列地址。设散列表的长度为m，对于键值key，发生冲突时，寻找空散列地址的公式为：例2设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用二次探测法处理冲突，散列表的构造过程如下：4772911169229222288333012345678910相对于线性探测法，二次探测法能够在一定程度上减少堆积设H(ki)=6，H(kj)=5，对于线性探测法：ki的探测序列：6,7,8,9,…kj的探测序列：5,6,7,8,…重合之后再不分开设H(ki)=6，H(kj)=5，对于二次探测法：ki的探测序列：6,7,5,10,2,…kj的探测序列：5,6,4,9,1,…重合之后很快分开二次探测法拉链法拉链法如何处理冲突？对于给定的关键码key执行下述操作：（1）计算散列地址：j=H(key)（2）将key对应的记录插入到同义词子表j中；开散列表：用拉链法处理冲突得到的散列表。开散列表中存储同义词子表的头指针，开散列表不会出现堆积现象同义词子表：所有散列地址相同的记录构成的单链表。开散列表会出现堆积现象吗？开散列表的类定义constintMaxSize=100;classOpenHashTable{public:OpenHashTable();

~OpenHashTable();

intInsert(intk);

intDelete(intk);

Node<int>*Search(intk);private:

intH();

Node<int>*ht[MaxSize];};OpenHashTable::OpenHashTable(){

for(inti=0;i<MaxSize;i++){

ht[i]=nullptr;

}

}012345678910

∧∧∧∧∧∧∧∧∧∧∧析构函数OpenHashTable::~OpenHashTable(){

Node<int>*p=nullptr,*q=nullptr;

for(inti=0;i<MaxSize;i++)

{

p=q=ht[i];

while(p!=nullptr)

{

p=p->next;

deleteq;

q=p;

}

}}012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧插入算法例3设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用拉链法处理冲突，在散列表中插入元素33。012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧

p33

qNode<int>*OpenHashTable::Insert(intk){j=H(k);Node<int>*p=ht[j];while(p!=nullptr){if(p->data==k)break;elsep=p->next;}if(p==nullptr){q=newNode<int>;q->data=k;q->next=ht[j];ht[j]=q;}}查找算法012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧Node<int>*OpenHashTable::Search(intk){intj=H(k);Node<int>*p=ht[j];while(p!=nullptr){if(p->data==k)returnp;elsep=p->next;}returnnullptr;}

p例4设散列函数为H(key)=keymod11，在如下开散列表中，分别给出元素47和14的查找过程。6-4-4散列查找的性能分析v第六章查找技术衡量方法散列技术的查找性能取决于什么？产生冲突后，仍然是给定值与关键码进行比较（1）散列函数是否均匀影响冲突产生的因素有什么？（2）处理冲突的方法例1设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法和拉链法处理冲突，分析查找性能。477291116922922228833012345678910查找成功的平均查找长度是：(1×5+2×3+4×1)/9=15/9例3设关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法和拉链法处理冲突，分析查找性能。012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧查找成功的平均查找长度是：(1×6+2×3)/9=12/9衡量方法产生冲突后，仍然是给定值与关键码进行比较（1）散列函数是否均匀影响冲突产生的因素有什么？（2）处理冲突的方法散列技术的查找性能取决于什么？表中填入的记录数散列表的长度

=（3）散列表的装填因子α查找性能散列表的平均查找长度是装填因子α的函数，而不是查找集合中记录个数n的函数——O(1)！6-4-5闭散列表和开散列表的比较v第六章查找技术空间比较闭散列表：开散列表：受数组空间限制，需要考虑存储容量没有记录个数的限制，但子表过长会降低查找效率存储效率较高指针的结构性开销有堆积现象，降低查找效率不会产生堆积现象，效率较高仅适用于静态查找适用于静态查找和动态查找时间比较闭散列表：开散列表：开散列表的删除操作例4设关键码集合{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用拉链法处理冲突构造开散列表，删除元素47。012345678910

∧∧∧∧∧11∧

22

47∧

3

92∧

16∧

7∧

29

8∧intOpenHashTable::Delete(intk){intj=H(k);

Node<int>*p=ht[j],*pre=nullptr;while((p!=nullptr)&&(p->data!=k){pre=p;p=p->next;}

if(p!=nullptr){if(pre==nullptr)ht[j]=p->next;elsepre->next=p->next;return1;}elsereturn0;}

p例5设关键码集合{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法处理冲突构造闭散列表，删除元素47。47729111692292222883333012345678910删除47、92、16断开探测序列查找元素3时会得到失败信息做删除标记，表示该位置有元素被删除，查找时遇到标记要继续进行修改查找、插入算法，删除算法比较复杂闭散列表的删除操作6-5模式匹配v第六章查找技术模式匹配模式匹配的应用场景1：模式匹配模式匹配的应用场景2：模式匹配问题有什么特点？（2）改进取得的积累效益：模式匹配操作被频繁调用，执行频率高。（1）算法的一次执行时间：问题规模通常很大，常常在大量信息中进行匹