《数据结构[Python语言描述]》教案第16课查找（8.3-8.4）.docx

《《数据结构[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）若待删除关键字所在结点中的关键字个数大于,则只需从该结点中删除该关键字和相应指针即可。（2）若待删除关键字所在结点中的关键字个数等于”2,而其左兄弟（或右兄弟）结点中的关键字个数大于/21,则需将双亲结点