数据结构课件110章全第九章查找幻灯片.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2、动态查找表 5、平衡二叉分类树 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况A： A B +1 h-1 0 +2 -1 h-1 LR 改组 BL AR 危机结点 改组前： 高度为 h + 1 中序序列： 注意：改组后 平衡度为 0,0,-1 C B C CL CR h-2 h-2 h-1 0 +1 C B 0 h-1 h-1 BL AR A CR h-2 CL h-1 -1 0 A B BL AR C CL CR 改组后： 高度为 h + 1 中序序列： A B BL AR C CL CR A 2、动态查找表 5、平衡二叉分类树 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况B： A B +1 h-1 0 +2 -1 h-1 LR 改组 BL AR 危机结点 改组前： 高度为 h + 1 中序序列： 注意：改组后 平衡度为 +1,0,0 C B C CR CL h-1 h-2 h-2 0 -1 C B 0 h-1 h-1 BL AR A CL h-1 CR h-2 +1 0 A B BL AR C CR CL 改组后： 高度为 h + 1 中序序列： A A B BL AR C CR CL 2、动态查找表 5、平衡二叉分类树 左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况C： A B +1 0 +2 -1 LR 改组 危机结点 改组前： 高度为 2 中序序列： 注意：改组后 平衡度为 0,0,0 C B C 0 A B C A 新插入结点 A B C 改组后： 高度为 2 中序序列： C B 0 A 0 0 四种情况的区分： 如果 的平衡度为＋1 则为 LL型改组； 否则为 LR型改组：若 的平衡度为＋1、－1 、0 ；则分别为 LRA、LRB、LRC型改组。 B C 2、动态查找表 5、平衡二叉分类树 右改组（新插入结点出现在危机结点的右子树上进行的调整）的情况分析： 1、RR 情况：（RR：表示新插入结点在危机结点的右子树的右子树上） 处理图形和 LL 镜象相似 2、RL 情况：（RL：表示新插入结点在危机结点的右子树的左子树上） A、处理图形和 LRA 镜象相似 B、处理图形和 LRB 镜象相似 C、处理图形和 LRC 镜象相似 删除情况：略 程序实现：略 6、平衡二叉分类树的查找分析： 定理：具有 N 个结点的平衡树，高度 h 满足：log2(N+1) = h = 1.44log2(N+1) - 0.328; 最大高度 为 log2(sgr(N+1)) – 2 查找的时间复杂度为O(Log n） 3、哈希查找表 1、什么是 hashing 表 特点：不用比较的办法，直接根据所求结点的关键字值 KEY 找到这个结点。 追求更快的速度 O(1)，优于任何其它的查找算法。 定义：设 M 存区由 m 个单元构成，它的第一个单元的地址为 0。设表具有 n 个结点 a1, a2, a3, ………... an； 这些结点相应的关键字值分别为： k1, k2, k3, ……… kn。又设 f 函数是一个确定的函数，它能将关键字 值 ki 映射为 M 存区的地址：即， f( ki ) - 0 ~ m-1 （注意：是一个确定的地址） 该地址就是结点 ai 的存放地址。 f 函数通常称之为 hashing 函数，而 M 存区称之为 hashing 表。 负载系数：α ＝ n/m e、g：将 31 个常用的英文单词，映射到 M 存区。设 m = 41 , 映射是等可能性的。 哈希表 0 1 40