《《数据结构[Python语言描述]》教案第16课查找（8.3-8.4）.docx》由会员分享，可在线阅读，更多相关《《数据结构[Python语言描述]》教案第16课查找（8.3-8.4）.docx（8页珍藏版）》请在课桌文档上搜索。
1、课题第16课查找(83-8.4)课时2课时(90min)教学目标知识目标：(1)掌握二叉排序树、平衡二叉树和B树的基本概念和杳找过程(2)了解哈希表的概念,掌握哈希函数的构造方法和处第中突的方法(3)掌握哈希查找算法和哈希性能技能目标：能灵活运用动态查找算法和哈希查找算法解决实际应用中的查找问题素质目标：自觉培养发散思维，积极开拓思路，寻求问题的多种解决方法教学重难点教学重点：动态有找算法、哈希表的查找教学睚点：动态查找算法、哈希表的查找教学方法问答法、讨论法、i并授法、实践法教学用具电脑、投影仪、多媒体课件、教材教学过程主要教学内容及步骤考勤【教师】使用APP进行签到【学生】班干部报请假人员
2、及原因问题导入【教师】提出以下问题：什么是动态查找？【学生】思考、举手回答传授新知【教师】通过学生的回答引入要讲的知识，介绍动态查找算法、哈希表的查找8.3动态查找算法基于动态查找表的查找又称动态查找，其特点是查找表的结构在查找过程中动态生成。8.3.1 二叉排序树二叉排序树又称二叉杳找树、二叉搜索树，是一种结构特殊的二叉树。二叉排序树可以是一棵空树，也可以是具有如下性质的二叉树。(1)若它的左子树非空，则左子树中所有结点的关键字均小于它的根结点的关键字。(2)若它的右子树非空，则右子树中所有结点的关键字均大于它的根结点的关键字。(3)它的左、右子树也分别为二叉排序树。【教师】多媒体展示“二叉
3、排序树”图(详见教材)，并介绍二叉排序树的性质由二叉排序树的定义可以得到二叉排序树的一些重要性质，具体如下.(1)中序遍历一棵二叉排序树可以得到一个关键字递增的有序序列。(2)整棵二叉排序树中关键字最小的结点是根结点的最左下结点(中序遍历序列的开始结点)。(3)整棵二叉排序树中关键字最大的结点是根结点的最右下结点(中序遍历序列的结束结点)若以二叉链表作为二叉排序树的存储结构，其结点定义如下.classBSTNode:#二叉排序树结点类def_init_(self,key,data,Ichild=None,rchild=None):self.key=key#关键字self.data=data#其
4、他数据项self.!child=!child#左子树域self.rchild=rchild#右子树域二叉排序树的定义如下。classBSTree:#二叉排序树类definit_(self,root=None):self.root=root#二叉排序树的根结点1.二叉排序树的插入和创建已知一个关键字为key的结点S,要将其插入二叉排序树中，且使插入后的树仍符合二叉排序树的定义，其基本步骤如下。(1)若二叉排序树为空,则S成为二叉排序树的根结点。(2)若二叉排序树非空，则将key与根结点的关键字进行如下比较.当key等于根结点的关键字时，停止插入。当key小于根结点的关键字时，将结点S插入根结点的
5、左子树。当key大于根结点的关键字时，将结点S插入根结点的右子树。(3)重复上述过程，直到将结点S插入二叉排序树中。【算法描述】【提示】创建二叉排序树的过程其实就是从一棵空二叉排序树开始，通过多次插入操作依次将新结点插入当前已生成的二叉排序树中。对于同样的数据元素序列，如果输入顺序不同，所创建的二叉排序树的形态也不同。2.二叉排序树的查找根据二叉排序树的特点，其直找的基本步骤如下。(1)若二叉排序树为空，则杳找失败.(2)若二叉排序树非空，则将给定值key与根结点的关键字进行如下I：匕较。当key等于根结点的关键字时，查找成功。当key小于根结点的关键字时，在根结点的左子树中继续查找。当hy大
6、于根结点的关键字时，在根结点的右子树中继续查找。(3)重复上述过程，直到查找成功或查找的子树为空(即查找失败)。【算法描述】详见教材在二叉排序树的查找中，若查找成功，则整个过程恰好是从根结点到待直找结点的一条路径；若查找失败，则整个过程是从根结点到某个叶子结点的一条路径。因此，二叉排序树的查找过程与折半查找类似，关键字比较次数不超过树的深度。但是，与折半直找不同的是，对于长度为的JI顺序表，其折半查找的判定树是唯一的，而对于含有个关键字的结点，其构造的二叉排序树却是不唯一的。(详见教材)3.二叉排序树的删除从二叉排序树中删除某个结点时，不能简单地将以该结点为根结点的子树全部删除，而应只删除该结
7、点，并且保证删除后的树仍然具备二叉排序树的性质。二叉排序树删除的基本步骤如下。(1)查找待删除结点是否在二叉排序树中，若不在，则不执行出可操作。(2)若待删除结点在二叉排序树中，假设待删除结点为p,其双亲结点为f,当结点p是f的左孩子结点(P是f的右孩子结点的情况与之羽以，不再赘述)时，有如下3种情况。当待删除结点p为叶子结点时，直接删除该结点即可。当待删除结点p艮有左子树或只有右子树时，可以将待删除结点P的左子树或右子树作为其双亲结点f的左子树。当待删除结点P既有左子树又有右子树时,在中序遍历整棵二叉排序树得到的按关键字有序排列的序列中，用待删除结点P的前驱结点或后继结点代替待删除结点P,并
8、将该前驱结点或后继结点从相应子树中删除。【算法描述】详见教材8.3.2平衡二叉树为了提高二叉排序树的查找效率，当二师E序树出现其左、右子树分布不均匀的情况时，通常会先对其进行调整，从而保证二叉排序树的深度尽可能小，这类特殊类型的二叉排序树称为平衡二叉树。平衡二叉树又称为AVL树。一棵非空的平衡二叉树应具有如下性质。（1）左子树与右子树深度之差的绝对值小于等于U（2）左子树与右子树都是平衡二叉树。其中，结点的左子树与右子树深度之差称为结点的平衡因子。显然，一棵平衡二叉树中所有结点的平衡因子只能是-1、O或1。【教师】随机邀请学生回答以下问题简述二叉排序树与平衡二叉树的区别.【学生】聆听、思考、回
9、答假设最氐层失衡结点为A,根据新插入结点S的位置的不同，将非平衡二叉树调整为平衡二叉树的方法有4种，分别是LL型调整（单向右旋）、RR型调整（单向左旋）、LR型调整（先左旋后右旋）、RL型调整（先右旋后左旋）。*【教师】多媒体展示“LL型调整示例、“RR型的调整方法”、“LR型的调整方法“、RL型的调整方法”图（详见教材），并介绍方法特点1 LL型调整（单向右旋）当在结点A的左子树根结点的左子树中插入新结点S时，结点A的平衡因子由1变为2,导致以结点A为根结点的子树失去平衡.调整方法为将结点A的左孩子结点B代替结点A作为新子树的根结点，将结点A作为结点B右子树的根结点，将结点B原来的右子树BR
10、作为结点A的左子树.2 .RR型调整（单向左旋）当在结点A的右子树根结点的右子树中插入新结点S时，结点A的平衡因子由变为-2,导致以结点A为根结点的子树失去平衡。调整方法为将结点A的右孩子结点B代替结点A作为新子树的根结点，将结点A作为结点B的左子树的根结点，将结点B原来的左子树BL作为结点A的右子树。3 .LR型调整（先左旋后右旋）当在结点A的左子树根结点的右子树中插入新结点S时，结点A的平衡因子由1变为2,导致以结点A为根结点的子树失去平衡。调整方法为首先将结点A的左孩子结点B的右孩子结点C作为新子树的根结点，将结点B作为结点C的左子树的根结点，将结点C原来的左子树Cl（如果存在）作为结点
11、B的右子树；然后将结点A作为结点C的右子树的根结点，将结点C原来的右子树Cr（如果存在）作为结点A的左子树.4 RL型调整（先右旋后左旋）当在结点A的右子树根结点的左子树中插入新结点S时，结点A的平衡因子由T变为-2,导致以结点A为根结点的子树失去平衡。调整方法为首先将结点A的右孩子结点B的左孩子结点C作为新子树的根结点，将结点A作为结点C的左子树的根结点，将结点C原来的左子树Cl（如果存在）作为结点A的右子树；然后将结点B作为结点C的右子树的根结点，将结点C原来的右子树Cr（如果存在）作为结点B的左子树。【高手点拨】虽然平衡二叉树可以提高查找效率，但是插入和删除操作却变得非常复杂。因此，平衡
12、二叉树适用于二叉排序树很少进行插入和删除操作，而经常进行查找操作的场景。8.3.3B树B树是一种多路直找树，树中所有结点的最大子树个数称为B树的阶，通常用m表示.一棵m阶B树，可以是一棵空树，也可以是具有如下性质的m叉树。(1)树中每个结点至多有m棵子树。(2)若根结点不是叶子结点，则根结点至少有两棵子树。(3)除根结点外的所有非叶子结点至少有2棵子树。(4)所有叶子结点在同一层，且不包含任何信息。(5)所有三限结点最多有m-1个关键字。【教师】多媒体展示“结点的结构”图，并介绍B树的结构特点IPoI加）JPiIhy1p2keynP”其中，为结点中关键字的个数，每个厢结点中关键字的个数满足2-
13、lnm-l；keyi(1in)为关键字，且满足keyiSM(UT)；p0n)为指向子树根结点的指针，且指针PC所指子树中所有结点的关键字均小于履Wli)加所指子树中所有结点的关键字均大于Aey(Ii).【教师】随机邀请学生回答以下问题B树有何特点？【学生】聆听、思考、回答B树具有如下特点。(I)Wie(2)有序.(3)多路。1.B树的插入和创建【教师】多媒体展示“结点的分裂”图(详见教材)，并介绍B树的插入和创建过程B树的创建过程是从一棵空树开始，通过逐个插入关键字而得到的。由于B树中除根结点外的所有非叶子结点中的关键字个数大于等于?/21,因此，每次插入关键字时首先在B树的最下层非叶子结点中
14、插入一个关键字，若插入后该结点中的关键字个数小于等于厂1,则插入成功；否则说明该结点没有空闲位置，需要进行结点的“分裂，即将一个结点在同一层分为两个结点。结点的分裂方法是以中间关键字为界，将该结点分为两个结点，并将中间关键字向上插入双亲结点中。若双亲结点也没有空闲位置，则按照该方法继续进行结点的分裂。如果在根结点进行分裂，则B树的深度加1.【教师】讲解实例8-5(详见教材)2.B树的查找在一棵B树中直找关键字的方法是将给定值key与根结点的关键字key进行比较,可分为如下4种情况。(1)若key=keyi,则查找成功。(2)若keykey1,则顺着指针p所指的子树继续查找.(3)若keyike
15、ykeyn,则顺着指针pn所指的子树继续查找。3.B树的删除B树的删除操作是指在B树的某个结点中删除指定关键字及其邻近的一个指针，且保证删除关键字后的树仍然满足B树的定义。若待删除关键字所在结点是最下层非叶子结点，由于其指针均为空，删除后不会影响其峥点，故可直接删除；若待删除关键字所在结点不是最下层非叶子结点，则将待删除关键字用其右（左）侧邻近指针指向的子树中最小（最大）的关键字（该关键字一定在最下层的非叶子结点中）替换，这样处理后，就可以将其作为在最下层非叶子结点中删除的情况。根据结点中关键字个数的不同，可分为如下3种情况。（1）若待删除关键字所在结点中的关键字个数大于,则只需从该结点中删除
16、该关键字和相应指针即可。（2）若待删除关键字所在结点中的关键字个数等于”2,而其左兄弟（或右兄弟）结点中的关键字个数大于/21,则需将双亲结点中分隔它们的关键字下移到待删除关键字所在结点中，同时将待删除关键字所在结点的左兄弟（或右兄弟）结点中最大（或最小）的关键字上移到双亲结点中。（3）若待删除关键字所在结点与其兄弟结点中的关键字个数均等于,则需将删除后剩余的关键字、双亲结点中分隔它们的关键字一起合并到待删除关键字所在结点的左兄弟（或右兄弟）结点中.如果因此使双亲结点中的关键字个数小于2/,则按照同样的方法进行处理。【教师】讲解实例8-6（详见教材），并介绍B树的删除操作【知识库】B+树是B树
17、的一种变形，常用于文件索引系统。与m阶B树相比，m阶B+树与其不同之处包括如下几点。（1）有n棵子树的结点中含有n个关键字。（2）所有叶子结点中包含全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身按关键字自小而大顺序链接.（3）所有的非叶子结点可以看作索引部分，其中仅包含其子树中的最大（或最小）关键字。8.4哈希表的查找【教师】随机邀请学生回答以下问题什么是哈希表？【学生】聆听、思考、回答哈希表又称散列表，是利用关键字与其存储地址的直接映射关系生成的列表。8.4.1 哈希表的基本概念哈希表存储是在数据元素的关键字与数据元素的存储位置之间建立某种对应关系，使得每个关键字对应一个存
18、储位置，从而可以根据这种对应关系计算出关键字对应的存储位置的值。通常，将关键字与存储位置之间的这种对应关系称为哈希（Hash）函数。把关键字为key的数据元素直接存入地址为H（key）的存储单元，当查找关键字为key的数据元素时，利用哈希函数计算出该数据元素的存储位置H（key）,从而达到按关键字直接存取数据元素的目的。按照这个思想建立的查找表称为哈希表，所得到的存储位置称为哈希地址,利用哈希表进行查找的方法称为哈希查找.理想状态下，每个关键字唯一对应哈希表的一个存储位置。但在实际情况下，多个关键字可能映射到哈希表的同一存储位置，这种现象称为哈希冲突，具有相同函数值的关键字称为同义词。8.4.
19、2 哈希函数的构造方法建立哈希表的目标是使n个数据元素的哈希地址尽可能均匀地分布在某个连续的地址空间上。根据关键字的结构和分布的不同，可构造出不同的哈希函数。1 .直接定址法直接定址法是指取关键字或关键字的某个线性函数值作为哈希地址，其哈希函数为H(key)=key或H(key)=key+b其中，a和b为常数。【教师】随机邀请学生回答以下问题直接定址法适用于什么情况？【学生】聆听、思考、回答直接定址法计算简单，且不会发生冲突，适用于关键字分布基本连续的情况。2 .数字分析法数字分析法是指在所有关键字已知且关键字位数较多的前提下，将关键字中取值较分散的数字位作为哈希地址。3 .平方取中法平方取中
20、法是指取关键字平方后的中间几位作为哈希地址。平方取中法的取值位数视表长而定，它适用于关键字中的每一位取值都不够分散或取值分散的位数小于哈希地址所需要的位数的情况。4 .除留余数法除留余数法是指取关键字被某个小于等于哈希表表长m的数p除后所得余数作为哈希地址，其哈希函数为(key)=key%p(PWm)5 .折叠法折叠法是指首先将关键字自左向右或自右向左分成位数相等的几部分(最后一部分位数不足时用O填充)，然后将这几部分叠加求和，将舍弃最高位进位后的结果作为哈希地址。折叠法适用于关键字位数较多且关键字中每T立数字分布大致均匀的情况。6 .4.3处理冲突的方法所谓处幽中突,就是指当由关键字计算出的
21、哈希地址出现冲突时，为该关键字对应的数据元素找到另一个空的哈希地址。常用的处理冲突方法包括开放定址法和链地址法。1.开放定址法开放定址法是指当由关键字key得到的哈希地址P=H(key)出现冲突时，以P为基础，产生另一个哈希地址Pl；如果Pl仍然冲突,再以Pl为基础，产生另一个哈希地址P2；以此类推，直到找到一个不发生中突的空闲哈希地址Pi,并将相应健元素存储到该地址。开放定址法的函数形式如下。Hj(key)=(H(key)+d)%m(lm-l)其中，H(何为哈希函数，m为哈希表的表长，&为增量序列。根据增量序列的取值方式的不同，开放定b去又分为如下两种。(1)线性探测法。(2)二次探测法。(
22、详见教材)【教师】讲解实例8-7（详见教材）2.链地址法链地址法是指将所有哈希地址相同的数据元素链接到同一个单链表中,并将单链表的头指针存储在哈希表中。*【教师】讲解实例8-8（详见教材）8.4.4哈希查找及性能分析1 .哈希查找哈希查找的基本思想是根据选定的哈希函数计算给定值的哈希地址，如果该地址为空，则直找失败；如果该地址中数据元素的关键字与给定值相等，则查找成功；否则存在）中突，须按处理冲突的方法计算下一个哈希地址，重复上述过程，直到所得哈希地址为空（查找失败）或找到关键字与给定值相等的数据元素（查找成功）。（详见教材）2 .哈希杳找性能分析影响哈希表中关键字比较次数的因素主要有哈希函数
23、和处理冲突的方法。1 ）采用开放定址法处理）中突的哈希查找对于实例8-7,假设每个关键字的查找概率相等，如果使用线性探测法处理冲突，则其中7个关键字（59、31、3、41、10、95、67）查找成功时均需要比较1次，1个关键字（27）查找成功时需要比较2次，1个关键字（14）直找成功时需要比较3次，所以在查找成功情况下的平均查找长度如下。ASLi=如7+2xl+3xl）n1.33杳找失败时有如下两种情况.（1）存储单元为空。（2）按处理中突的方法探测一遍后仍未找到。假设哈希函数的取值个数为r,则0口相当于r个查找失败的入口。从每个入口进入，直到查找失败，此时，关键字的比较次数就是与该入口对应的
24、直找失败的直找长度.（详见教材）2）采用链地址法处圉中突的哈希查找对于实例8-7,假设每个关键字的直找概率相等，如果使用链地址法处理冲突,其中8个关键字（除14外）查找成功时均需要比较1次，1个关键字（14）查找成功时需要比较2次，所以在查找成功情况下的平均直找长度如下.ASLsutxess=1（1812）1.11对于直找失败的情况，假设待查找关键字不在哈希表中，则关键字的比较次数等于单链表中的数据元素的个数（含头指针）.（详见教材）【学生】聆听、思考、理解、记录任务1利用二叉排序树查找学生成绩【教师】描述问题，分析问题，要求学生完成任务任务实施【问题描述】输入一组学生成绩信息（包括学生的学号
25、和分数），根据这些信息创建二叉排序树，并杳找指定学生的成绩信息。【问题分析】首先输入学生人数，并依次录入每个学生的成绩信息，然后根据这些成绩信息创建二叉排序树，最后使用二叉排序树查找指定学生的成绩信息，若找到，输出学生的成绩信息；否则输出未找到学生的成绩信息。【学生】按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题任务2利用哈希表查找员工信息【教师】描述问题，分析问题，安排学生扫描微课二维码观看视频”利用哈希表查找员工信息”(详见教材)，要求学生完成任务【问题描述】在员工信息表中存储了员工的ID、姓名和薪资，且每个员工的ID是唯一的，如表8-8所示.以员工的ID为主
26、关键字建立哈希表，设计算法根据员工ID利用哈希表快速有找该员工的信息.【问题分析】(1)构造合适的哈希函数。(2)根据哈希函数计算各个关键字的哈希地址，然后根据处理冲突的方法(此处使用链地址法处理冲突)建立哈希表，并将其输出。(3)在哈希表中进行查找，若查找成功，输出查找结果，否则输出“未找到该员工的信息！。【学生】自行扫码观看配套微课，按照要求完成任务，如遇问题可询问老师【教师】巡堂辅导，及时解决学生遇到的问题课堂小结【教师】简要总结本节课的要点动态直找算法：二叉树排序、平衡二叉树、B树哈希表杳找：哈希表的基本概念、哈希函数的构造方法、处理冲突的方法、哈希杳找及性能分析【学生】总结回顾知识点作业布置【教师】布置课后作业完成课后习题中的剩余练习。【学生】完成课后任务教学反思
