第9章 查找2解析.ppt

（4）掌握哈希表查找技术以及哈希表与其他表的本质区别。 （5）灵活运用各种查找算法解决一些综合应用问题。 练习9 教材中p271习题1、2、3和5。 上机实习题 教材中p172题3和5。 * * ③ 假如被删节点的关键字个数等于Min，并且该节点的左和右兄弟节点（如果存在的话）中关键字个数均等于Min。 　　这时需把要删除关键字的节点与其左（或右）兄弟节点以及双亲节点中分割二者的关键字合并成一个节点。如果因此使双亲节点中关键字个数小于Min，则对此双亲节点做同样处理，以致于可能直到对根节点做这样的处理而使整个树减少一层。 例如,对于上例生成的B-树，给出删除8,16,15,4等4个关键字的过程。 （a） 初始5阶B-树 10 14 15 13 16 3 6 1 2 7 8 9 17 18 19 20 4 5 11 12 7 9 删8 删16 17 13 13 17 18 19 20 删15 14 17 18 14 17 19 20 删4 5 1 2 3 5 6 6 10 13 18 13 18 对于前例生成的B-树，给出删除8,16,15,4等四个关键字的过程。 9.3.4 B+树 在索引文件组织中,经常使用B-树的一些变形，其中B+树是一种应用广泛的变形。一棵m阶B+树满足下列条件： 一棵m阶B+树满足下列条件： 　　（1）每个分支节点至多有m棵子树。 　　（2）根节点或者没有子树，或者至少有两棵子树。 　　（3）除根节点外，其他每个分支节点至少有?m/2?棵子树。 　　（4）有n棵子树的节点有n个关键字。 　　 （5）所有叶子节点包含全部关键字及指向相应记录的指针，而且叶子节点按关键字大小顺序链接（可以把每个叶子节点看成是一个基本索引块，它的指针不再指向另一级索引块，而是直接指向数据文件中的记录）。 　　（6）所有分支节点（可看成是索引的索引）中仅包含它的各个子节点（即下级索引的索引块）中最大关键字及指向子节点的指针。 一棵4阶的B+树 某关键字指向的记录。 索引部分 m阶的B+树和m阶的B-树,定义中的前三点是相同的，主要的差异是： （1）在B+树中，具有n个关键字的节点含有n棵子树，即每个关键字对应一棵子树，而在B-树中，具有n个关键字的节点含有(n+1)棵子树。 （2）在B+树中，每个节点（除根节点外）中的关键字个数n的取值范围是?m/2?≤n≤m，根节点n的取值范围是1≤n≤m；而在B-树中，它们的取值范围分别是?m/2?-1≤n≤m-1和1≤n≤m-1。 （3）B+树中的所有叶子节点包含了全部关键字，即其他非叶子节点中的关键字包含在叶子节点中，而在B-树中，叶子节点包含的关键字与其他节点包含的关键字是不重复的。 （4）B+树中所有非叶子节点仅起到索引的作用，即节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。而在B-树中,每个关键字对应一个记录的存储地址。 （5）通常在B+树上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，所有叶子节点链接成一个不定长的线性链表。 9.4 哈希表查找 9.4.1 哈希表的基本概念 哈希表（Hash Table）又称散列表，是除顺序表存储结构、链接表存储结构和索引表存储结构之外的又一种存储线性表的存储结构。 　　哈希表存储的基本思路是：设要存储的对象个数为n，设置一个长度为m（m≥n）的连续内存单元，以线性表中每个对象的关键字ki（0≤i≤n-1）为自变量，通过一个称为哈希函数的函数h(ki)，把ki映射为内存单元的地址（或称下标）h(ki)，并把该对象存储在这个内存单元中。h(ki)也称为哈希地址（又称散列地址）。把如此构造的线性表存储结构称为哈希表。 某种函数关系 存储地址 存储地址=h(key) 但是存在这样的问题，对于两个关键字ki和kj（i≠j），有ki≠kj（i≠j），但h(ki)=h(kj)。把这种现象叫做哈希冲突。 通常把这种具有不同关键字而具有相同哈希地址的对象称做“同义词”，由同义词引起的冲突称作同义词冲突。 　　在哈希表存储结构的存储中，同义词冲突是很难避免的,除非关键字的变化区间小于等于哈希地址的变化区间，而这种情况当关键字取值不连续时是非常浪费存储空间的。通常的实际情况是